mondegreen

백트래킹의 개념 해를 찾는 도중 해가 아니면, 되돌아가서 다시 해를 찾아가는 방법 => 모든 가능한 경우의 수 중 특정한 조건을 만족하는 경우만 살펴보는 방법 => 만족하지 않는 것이 확인되면 부모 노드로 돌아가 다음 자식 노드를 확인한다. => 가지치기라고 말하는데 불필요한 부분을 굳이 연산하지 않아 효율적이다. => 최악의 경우에는 여전히 지수함수 시간을 요할 수 있어 반드시 답을 얻는 것은 아님 깊이우선탐색(DFS) + 가지치기(Pruning) DFS만으로는 답이 될 수 없는 경우도 모두 리프까지 탐색하므로 이 때 특정 조건문을 작성하여 조건에 해당하지 않으면 해당 경로를 가지는 않는 가지치기 방식을 적용해 백트래킹을 구현할 수 있다. 백준 9663 import java.util.Scanner; p..