백트래킹

백트래킹이란?

반에 놓고 온 물건이 있다고 가정을 하였을 때, 학교로 돌아가야 합니다. 이후 반에 들어가야하는데 자기 반이 아니라 옆반인 것을 확인하면 자기 반으로 다시 돌아가는 것처럼 올바른 접근이 아닐 경우 되돌아가는 것을 백트래킹이라고 합니다.

백트래킹 알고리즘이란

가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘을 백트래킹 알고리즘이라고 합니다.

위와 같이 가능성이 없다면 아예 돌아가는 것을 백트래킹이라고 합니다. 백트래킹 알고리즘은 문제마다 효율이 달라지므로 시간 복잡도를 특정하기는 어렵습니다. 하지만 불필요한 탐색을 줄이므로 일반적인 탐색하는 방법보다 효율적이라는 것을 알 수 있습니다.

유망 함수란?

백트래킹 알고리즘의 핵심은 '해가 될 가능성을 판단하는 것'입니다. 때문에 유망 함수라는 것을 정의하여 판단합니다.

다음과 같은 과정으로 진행합니다.

1. 유효한 해의 집합을 정의합니다.

2. 정의한 집합을 그래프로 표현합니다.

3. 유망 함수를 정의합니다.

4. 백트래킹 알고리즘을 활용, 답을 구합니다.