3. 완전검색, 분할정복

최적해 문제를 푸는 방법

1. 완전 검색 → 중복 제거 → 개선된 알고리즘
2. 완전 검색 알고리즘 → 분할정복, 그리디기법, 동적 계획법

---

완전 검색

• 문제의 해를 얻기 위해 가능한 모든 경우들을 나열해보고 확인하는 기법
• 문제에 포함된 자료의 크기가 작을 경우 유용
• 해답을 찾지 못할 확률이 적음

단점

• 문제의 크기가 커지면 시간 복잡도가 매우 크게 증가
• 속도 문제로 인해 그리디기법, 동적계획법 등을 이용해서 효율적인 알고리즘을 찾아나가야 함

 

분할 정복

"분할 + 정복 + 통합"의 Top-Down 방식

• 분할 : 해결할 문제를 여러 개의 작은 부분 문제들로 분할
• 정복 : 나눈 작은 문제들을 각각 해결
• 통합 : 해결된 답들을 모음

 

예시 : 퀵 정렬, 병합 정렬, 이진검색, 거듭제곱