[개념정리]백 트래킹_nabi

기록용

3줄 TMI

알고리즘 스터디 날짜가 조금씩 밀렸다. 이는 내가 나태해지고 있다는 걸 의미하는 것 같아 반성을 하고 있다. 이번주 활동부터는 정말 절대로 미루지 않을 것이다. 나는 약속을 정말 중요하게 생각하는데 활동이 밀리는 걸 보며 회의감이 든다.

---

 백 트래킹이란?
모든 경우의 수를 전부 고려하는 알고리즘.
상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. -나무위키-

라고 정의되어있긴 하지만 내가 생각하는 정의와는 좀 다르다.

저 정의를 보자마자 가장 먼저 든 생각은 '브루트 포스와의 차이점이 있는 가' 였다.

브루트 포스도 위 백 트래킹 개념과 마찬가지로 모든 경우의 수를 비교하여 답을 찾아내는 알고리즘이다.

하지만 이 둘은 서로 다른 알고리즘 개념이다.

 

백 트래킹(Backtracing)
백 트래킹을 번역하면 역추적을 의미한다.
이를 프로그래밍에 적용하면 모든 경우의 수를 고려하는 것은 맞지만 가능성이 있는 것에 한해 찾아가는 '가지치기' 기법을 사용하는 알고리즘이다. 즉, 이미 지나쳐 온 노드더라도 다시 돌아가 다른 가능성을 시도해보는 기법이다. 주로 재귀함수로 구현된다.
- 가지치기 : 조건에 맞지 않는 노드는 찾아가지 않음.

이제 위에서 생긴 의문을 해결하겠다.

 

백 트래킹, 브루트 포스, DFS 의 차이점

백 트래킹 : 가지치기를 통해 불필요한 루트를 제거할 수 있으므로 DFS 알고리즘에 비해 시간을 단출할 수 있다.

브루트 포스 : '깊이'와 '탐색'에 국한된 개념이 아닌 모든 경우의 수를 다 대입해보는 것을 통틀어 브루트 포스라고 부른다.

DFS : 트리의 깊은 곳으로 탐색해가는 완전 탐색 기법 중 하나