[알고리즘] 백트래킹

<백트래킹 알고리즘의 특징>

• 모든 경우의 수를 전부 고려하는 알고리즘
• 상태 공간을 트리로 나타낼 수 있을 때 적합한 방식
• 깊이우선탐색
• 너비우선탐색
• 최선우선탐색

• 재귀함수로 구현하는 경우가 많음
• 깊이우선탐색: 스택을 이용
• 너비우선탐색: 큐를 이용

* 백트래킹은 모든 경우의 수를 다 확인하기 때문에, 확인해야 하는 대상이 많아지면 시간이 크게 늘어난다. 

  따라서 가지치기가 중요해 진다.