Brute-Force, 백트래킹, DFS

간혹가다 브루트포스와 백트래킹, 그리고 DFS(깊이우선탐색)를 혼동하는 경우가 있어 이에 대해 정리를 한 번 하고 가는게 좋다.

 

"a + b + c + d = 20을 만족하는 두 수를 모두 찾아내시오 (0 <= a, b, c, d < 100)"

 

브루트포스는 말 그대로 '모든 경우의 수'를 찾아보는 것이다. 

즉 a = 1, b = 1, c = 1, d = 1부터 시작하여 a = 100, b = 100, c = 100, d = 100 까지 총 1억개의 경우의 수를 모두 찾아보면서

a + b + c + d = 20을 만족하는 값을 탐색하는 것이다.

브루트포스가 강력한 점은 모든 경우의 수를 탐색하다보니 만족하는 값을 100% 찾아낸다는 점이다.

반대로 단점이라면 모든 경우의 수를 판단하는 만큼 조합 가능한 경우의 수가 많으면 많을 수록 자원을 매우 많이 필요로 한다는 점이다.

 

백트래킹은 해당 범위 내에서 조건을 추가하여 값의 유망성을 판단하여 유망하지 않은 값들을 제외시키는 방법.

하나라도 a = 21 또는 b = 21 또는 c = 21 또는 d = 21 일 경우 20일 가능성이 1 ~ 100 범위 내에서는 절대 불가능하다.

그렇기 때문에 a > 20 이거나 b > 20, c > 20, d > 20 일 경우는 탐색하지 않는다.

그렇게 된다면 탐색하는데 필요한 자원을 많이 줄일 수 있다.

 

DFS(깊이우선탐색)은 트리순회의 한 형태다. 하나의 순회 알고리즘으로 백트래킹에 사용하는 대표적인 탐색 알고리즘이다. 

즉, 백트래킹 = DFS가 아니라 백트래킹의 방법 중 하나가 DFS인 것.

그 외에도 BFS(너비우선탐색) 등 다양한 방법으로 백트래킹을 구현할 수 있다. 

말 그대로 깊이를 우선으로 먼저 탐색하는 방법이다.

 

 

 

https://st-lab.tistory.com/114

[백준] 15649번 : N과 M (1) - JAVA [자바]