분할정복(Divide and Conquer)과 백트래킹

분할정복(Divide and Conquer)

• Divide : 큰 문제를 작은 문제로 분할한다.
  • 기저사례(base case)를 잘 설정하여 일정 기준 이상 분할되지 않도록 해야한다.
• Conquer: 작은 문제의 답을 모아 큰 문제의 답을 구한다.

일반적으로 재귀로 구현한다.

 

 

백트래킹(backtracking)

• 답이 될 수 없는 경우는 탐색 대상에서 제외하여 효율적으로 답을 구하는 알고리즘
  • 가지치기(pruning)를 통해 연산량의 유의미하게 줄여줌
• 가지치기를 사용하기 위해서는 현재 상태에서 도달할 수 있는 상태가 모두 답이 될 수 없음을 보여야함.
• 정확한 시간 복잡도를 구하기 어려움

 

분할 정복	백트래킹
주로 재귀적인 방식으로 해결
하위 문제를 해결하고 결과를 결합하여 문제를 해결	문제 해결을 위해 모든 가능한 선택을 시도한 후, 가능성이 없다고 판단되면 이전 단계로 되돌아가거나 이전 결정을 변경