용어 정리
백트래킹과 관련된 세 가지 개념에 대해 살펴보자.
-
브루트 포스 알고리즘
문제를 풀기 위해 가장 단순한 방법으로 접근하는 알고리즘. 최적화나 가지치기를 고려하지 않으면서 직관적으로 떠오르는 문제 해결 알고리즘이다. 문제 이면에 숨겨진 구조나 규칙을 고려하지 않기에, 종종 필요 이상의 시공간 비용을 요구한다.
-
완전탐색
완전탐색(Exhaustive search)은 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 말한다.
-
백트래킹
백트래킹은 말 그대로 막다른 길(구체적으로는, 문제의 조건에 위배되는 상황)에 다다르면 뒤로 돌아가는 알고리즘이다. 조건에 위배되는 상황에서 더 나아가지 않는 것을 가지치기(pruning)라고 부르기도 한다.
세 개념은 칼로 자른 듯이 정확한 구분은 어렵고, 모두들 이 용어를 혼용하는 것처럼 보인다.
레시피
레시피문제를 완전탐색으로 해결하는 과정
- 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 답의 수에 정확히 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들 모두가 제한 시간 안에 생성될 수 있을지 가늠해본다. 이때, 컴퓨터가 대략 1초에 1억번 연산을 수행한다는 사실을 참고한다.
- 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.
- 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
- 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리한다.
적용
백준 15649번 : N과 M (1)
- 답의 개수는
이고, 이때 최악의 경우 답의 개수는 이 되므로, 충분히 가능해보인다. - 첫번째 수를 결정하는 것이 문제의 한 조각이고, 나머지
개의 수의 결정 또한 이런 식으로 쪼갠다.
참고 문헌
- 구종만, 『프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략』 1판, 인사이트, 2012.