cchanmi

최근에 알고리즘 문제를 풀다가 백트래킹이라는 개념을 사용해야 하는 문제를 접하게 되었는데, 어떤 개념인지 잘 짚고 넘어가면 좋을 것 같아서 정리해 보려고 합니다! 백트래킹이란? 제약 조건 만족 문제에서 해를 찾기 위한 전략입니다. 보통 DFS랑 같이 사용되곤 하는데요. 문제에서 요구하는 해를 찾기 위해 제약 조건에 따라 점진적으로 방문하다가, 해당 노드가 제약 조건에 만족할 수 없다고 판단하였을 때, 즉시 이 노드는 더이상 방문할 필요가 없음을 판단하고, 뒤로 돌아가 다른 노드를 탐색하며, 최적의 해를 찾는 방법이라고 설명할 수 있습니다. 조건에 맞지 않을 경우 더이상의 탐색을 포기하는 것을 가지치기라고 얘기하며, 주어진 해를 찾는 탐색의 시간을 절약하는 기법입니다. 결론적으로 백트래킹은 DFS로 트리 ..