초급 6회차 완전탐색과 백트래킹

완전탐색

Brute Force 방식을 가리킨다.
존재하는 모든 경우의 수를 다 탐색하는 풀이법이다.

완전탐색으로 풀 만한 문제는 어떤 문제?

• 가능한 모든 경우의 수가, 다 살펴볼 수 있을 정도로 적은 문제
• 하나의 경우마다 따져야 할 것이 분명한 문제
• 어떤 상태를 구성한 후에 그 상태가 특정 조건을 만족하는지 검토해야 하는 문제

사실 모든 알고리즘 문제는 완전탐색(노가다)으로 풀 수 있다. 시간복잡도와 공간복잡도가 문제일 뿐이다.
따라서, 알고리즘 문제를 풀 때 일단 완전탐색 식의 풀이법을 구상해본 뒤에
비벼볼 만 하다면 그대로 제출해보고
그렇지 않다면 완전탐색 식의 풀이법을 최적화함으로써 풀이법을 강구해볼 수 있다.

백트래킹

완전탐색처럼 해를 구하기 위한 경우들을 각각 다 탐색을 하는데, 그 과정에서
해당 경로를 끝까지 다 탐색했거나
이 경로로 가서는 필요한 해가 나올 가능성이 없다는 것이 확실한 시점이 오면
이전 분기로 되돌아가는 방식이다.
이전 분기로 "되돌아가야" 하므로, 재귀함수로 구현하는 경우가 많다.

미연시 게임이 적절한 예시이다.
A, B, C의 선택지 중에서 A를 선택했는데 마음에 들지 않는 결과가 나왔다면
세이브 파일을 열어 다시 선택 이전의 상황으로 돌아갈 수 있다.
그 후에 B나 C를 선택하여 다른 결과를 볼 수가 있다.
백트래킹이 딱 이렇게 작동한다.

백트래킹에서는 각각의 경우를 인수로 가지면서 특정 '상태'를 만들어주는 함수를 이용한다.
만들어진 상태가 문제에서 요구하는 조건에 부합하는지를 체크해가며 브루트포스를 수행하는 것이다.

백트래킹에서의 가지치기

어떠한 경로를 끝까지 다 탐색하지는 않았지만 이 경로로 가서는 필요한 해가 나오지 않겠다는 확신이 들 때
그 경로의 탐색을 종료함으로써 허비되는 시간을 줄일 수 있는데,
이를 가지치기라고 부른다.