[알고리즘 -3] 완전탐색, 백트래킹

 

 

완전탐색 (Brute Force)

모든 경우의 수를 탐색하는 알고리즘

 

'노가다'라고 흔히 비유되는 이 방법은, 주어진 문제의 모든 가능성을 탐색하여 정답을 찾아내는 알고리즘 접근방식이다

흔히 사용하는 DFS, BFS도 완전탐색에 해당한다

 

⚠️ 고려사항

완전탐색을 사용할 때 주의할 점은, 처리해야 할 데이터의 양이 너무 많지 않아야 한다. 보통 시간 복잡도 1억 미만으로 볼 수 있다.

 

📌 구현 방법

1) for / while를 이용

2) 재귀함수 이용

재귀함수를 활용하면 복잡하고 비용이 들기 때문에 반복문으로 해결이 가능하다면 가능한, 반복문으로 구현하는 것이 좋다

단, 매개변수의 수정만 필요한 반복적인 행위가 요구된다면, 재귀함수를 이용하는 것이 더 적합하다

 

- 조합이나 순열 

- DFS, BFS 알고리즘

- 경우의 수 마다 생각해야 하는 로직

 

 

백트래킹 (Backtracking)

재귀를 활용한 완전탐색 방법으로, 불필요하거나 목표에 이르지 못하는 경우에는 해당 경로의 탐색을 즉시 중단하고, 이전 단계로 돌아가 다른 가능성을 탐색하는 방법

완전탐색의 시간복잡도의 문제를 가지치기를 통해 최대한 불필요한 탐색을 피하는 방식이라고 볼 수 있다

다음과 같이 2번 노드가 답이 될 수 없기 때문에 4번과 5번 노드는 더 이상 탐색하지 않고 전 단계로 돌아가서 3번노드를 탐색하게 된다 그러면 모든 경우의 수를 탐색할 때 보다 시간복잡도를 줄일 수 있다

 

원복

완전탐색 과정에서 다양한 상태의 경우의 수를 탐색할 때, 각 경우의 수가 서로 영향을 미치지 않도록 관리하는 방법 중 하나는 '원복'이라는 기술을 사용한다

 

주로 방문 배열을 사용하여 구현되며, 특정 상태를 탐색한 후에는 해당 상태를 이전 상태로 되돌려 놓아야 하는 상황에 유용하다 이렇게 함으로써, 각각의 경우의 수를 독립적으로 처리할 수 있다

다음과 같이 A노드에서 출발하여 C,D노드로 갈 수 있는 경우의 수를 구한다고 하면

A → B → C 를 방문 후 경로의 출력하고 C의 방문 상태를 원복해야 다음 경우의 수에 영향을 미치지 않을 수 있다. 따라서 A → B → D 를 출력할 수 있고, 2가지 경우의 수는 독립적인 상태로 남을 수 있다