백트래킹 vs DFS vs 브루트포스 - joi0104/BOJ GitHub Wiki

알고리즘을 공부하면서 이 세가지 개념에 대해 혼란이 오기 시작했다. 위 포스팅을 3가지 개념을 비교하여 차이를 설명하고자 한다.

백트래킹 vs DFS

• DFS는 여러지점을 한 단계씩 거쳐가면서 탐색하고 스택의 개념을 이용해서 이전 단계로 돌아가는 기법이다.
• 백트래킹은 이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법으로, 반드시 DFS만으로 가능하지 않고 BFS등으로도 가능한 기법이다.
• 즉, 정리를 하자면 백트레킹은 하나의 문제 해결 방법론이고 이러한 백트레킹을 구현하는 방법론 중 하나가 DFS이다.

백트래킹 vs 브루트포스

• 브루드 포스는 모든 경우의 수를 탐색하는 문제 해결 방법론이다.
• 이와 달리, 백트래킹은 단계마다 조건을 충족하는지 검사하여 조건을 충족하는 경우에만 계속해서 탐색한다.
• 즉, 정리를 하자면 브루트포스 모든 가지를 탐색하는 방법론이고 백트레킹을 조건을 보고 가지치기를 해나가면서 탐색하는 방법론이다.