완전탐색(Brute Force)과 백트래킹(Backtracking)의 차이

완전탐색(Brute Force)

 

1) 탐색 순서

 

브루트포스는 가능한 모든 해를 순차적으로 검사하는 방식이다.

모든 경우의 수를 하나씩 시도하여 정답을 찾을 때까지 모든 경우를 확인한다.

즉, 문제 공간의 모든 가능성을 전부 조사하는 방식이다.

 

2) 제약 조건

 

브루트포스는 문제의 제약 조건을 고려하지 않고 모든 가능한 해를 탐색한다.

제약 조건에 따라 해의 개수가 많아질 수 있다.

 

3) 탐색 중단

 

브루트포스는 모든 가능한 해를 탐색해야 하므로, 정답을 찾지 못하더라도 모든 경우를 검사한다.

따라서 실행 시간이 길어질 수 있다.

 

백트래킹(Backtracking)

 

백트래킹의 원리

 

1) 탐색 순서

백트래킹은 탐색 도중 불필요한 부분을 가지치기하여 탐색 공간을 줄인다.

유망한 후보 해를 따라가다가 더 이상 진행할 수 없는 상황에 도달하면 되돌아가서 다른 후보 해를 탐색한다.

백트래킹은 유망성을 판단하여 불필요한 탐색을 줄이는 방식으로 실행 시간을 단축시킨다.

2) 제약 조건

백트래킹은 문제의 제약 조건을 고려하여 탐색을 진행한다. 

유망한 경로만 따라가면서 불필요한 탐색을 제외하고, 제약 조건에 맞는 해를 찾는다.

3) 탐색 중단

백트래킹은 불필요한 탐색을 줄여나가므로, 정답을 찾으면 탐색을 중단하고 해당 정답을 반환한다.

조기 종료를 통해 실행 시간을 단축시킬 수 있다.

 

 

요약

브루트포스는 가능한 모든 경우의 수를 순차적으로 탐색하는 방법으로 불필요한 탐색을 하지만,

백트래킹은 유망성을 판단하여 탐색 공간을 줄이는 방식.