반응형 BackTracking1 백트래킹(Backtracking) 알고리즘 설명 DFS를 기반으로 생성된 알고리즘으로, 기존 DFS는 모든 경우의 수를 찾아가기 때문에 불필요한 탐색이 존재하여 이 부분이 문제가 되는 경우가 있었다. 때문에 이를 보완하기 위해서 나온 알고리즘으로, 현재 탐색을 진행하고있는 루트가 이미 실패가 예정된 루트라면 해당 루트를 종료하고 더 이상 그 루트를 통하여 탐색을 진행하지 않고 이전으로 돌아가는 것을 백트래킹이라고 칭한다. 때문에 현재 루트의 가능성을 판단하는 조건이 잘 짜여질수록 효율이 올라가게 된다. 보통 DFS를 사용하는 문제에서, 완전탐색 시 경우의 수가 너무 많아지는 문제에 대하여 조건을 걸어서 루트를 줄이는 역할을 한다. 대표적인 백트래킹 문제인 N-Queen에서의 예시 문제를 요약하자면 퀸이 서로 겹치지 않게 NxN크기의 판에 N개의 .. 2021. 7. 30. 이전 1 다음 반응형
