backtracking1 백트래킹(Backtracking) [Algorithm #2] DFS(깊이 우선 탐색)의 경우 모든 경우의 수를 하나씩 다 따지기 때문에 매우 비효율적이다. 그래서 탐색 도중 조건에 맞지 않으면 이전 단계로 되돌아가는 백트래킹을 많이 이용한다. 중간중간 조건에 맞지 않는 케이스는 "가지치기"하여 탐색 시간을 줄인다. 이전 단계로 돌아가는 설계를 잘 해야 한다. 어떤 조건에 되돌아가게 할 건지, 어떤 시점으로 되돌아가게 할 건지를 잘 생각해야 한다. 코드 구현은 DFS처럼 재귀(Recursion)를 이용하되, 코드 도입부에 조건을 추가하여 조건에 맞지 않을 경우 return하여 이전 노드로 다시 되돌아가도록 구현하는 것이 일반적이다. def backtracking(...): if ...: # 되돌아가는 조건 return for i in range(...): list... 2022. 7. 22. 이전 1 다음 728x90
