[Algorithm] 백트래킹(BackTracking) 백트래킹이란?백트래킹은 모든 경우의 수를 고려하는 알고리즘이다. 하지만 완전 탐색과는 다르게 조건이 있어, 무작정 경우의 수를 파악하기 보다는 가능성 있는 경우를 탐색하고 가능성이 아예 없는 경우 제외를 하게 된다. 따라서 단순하게 다중 for 문을 이용하는 전체 탐색보다는 효율적이고 빠르게 탐색이 가능하다. 위와 같은 트리가 존재할 때, D 노드가 조건에 부합하지 않는다고 가정해보자. 완전 탐색을 진행하게 된다면 노드가 조건에 부합하지 않더라도 안쪽까지 파고 들어 F, G 까지 확인을 하게 될 것이다. 하지만 백트래킹의 경우에는 D 노드가 조건에 부합하지 않는다면 굳이 F, G 까지 내려가지 않고 다시 B로 돌아와 유망한 노드를 탐색하게 되기 때문에 불필요한 과정을 줄여 더 효율적이라고 볼 수 있다.구.. 이전 1 다음
