백트래킹 (BackTracking)

백트래킹 vs 브루트포스

1. 브루트포스 알고리즘이란?

부르트포스 알고리즘은 완전 탐색 알고리즘이다.

완전 탐색 알고리즘 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과를 탐색한다.

시간이 오래 걸린다는 단점이 있다.

2. 백트래킹 알고리즘이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾는 기법이다.

백트래킹은 해를 찾아가면서 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 가지 않고 되돌아 간다.

해가 될 것 같지 않은 부분을 가지 않는 것을 나뭇 가지의 가지를 치는 행위와 비슷하다고 하여 가지치기(pruning) 이라고도 한다.

브루트 포스 알고리즘과 다르게 끝까지 탐색하지 않기 때문에 시간을 단축시킬 수 있다.

2-1 DFS (깊이 우선 탐색)

트리 순회의 한 형태이다.

백트래킹에 사용하는 대표적인 탐색 알고리즘이다.