백트래킹2 c++) 백준 14888 백트래킹, 연산자 끼워넣기 14888번: 연산자 끼워넣기 (acmicpc.net) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 1. 접근 수열과 수열의 각 수 사이에 들어갈 연산자가 주어진다. 수열은 순서에 맞게 계산해야하므로 사실 고려할게 없다. 우리가 고려해야할 것은 주어진 연산자들의 모든 순서와, 그로 인해 계산된 결과들을 출력하는 것 뿐. 사실상 연산자들을 선택하는 순열로 생각하면 된다. 2. 풀이 operands 배열엔 수열을 이루는 수들을 입력받는다. operato.. 2024. 3. 25. 백트래킹(Backtracking) 알고리즘 1.백트래킹이란? 해를 찾을 때 모든 경우의 수를 전부 고려하는 알고리즘이다. 다만 이름처럼 되추적 과정을 거쳐, 사실 모든 경우의 수를 다 돌진 않고 유망성을 판단해 버릴건 버리고 가는 방법이다. 쉽게 말하면 모든 경로를 돌긴하는데, 개중에 특정 조건만 만족하는 경우만 탐색하는 방법이다. 경우의 수 탐색에 트리가 사용되므로, 일종의 트리 검색 알고리즘이라고 봐도 무방하다. Backtracking(되추적) 해를 찾아가는 도중 그 경로가 해가 되지 않을 것 같다고 판단되면, 이전 단계로 돌아가 다시 찾아가는 기법 2. DFS 깊이우선검색(Depth First Search), 트리에서 깊이를 우선 기준으로 두고 탐색하는 방법으로, 백트래킹에서는 DFS를 이용해 트리를 탐색한다. (너비우선 BFS도 사용해 구.. 2024. 3. 24. 이전 1 다음
