Machineboy空
분할정복(Divide and Conquer)과 백트래킹 본문
분할정복(Divide and Conquer)
- Divide : 큰 문제를 작은 문제로 분할한다.
- 기저사례(base case)를 잘 설정하여 일정 기준 이상 분할되지 않도록 해야한다.
- Conquer: 작은 문제의 답을 모아 큰 문제의 답을 구한다.
일반적으로 재귀로 구현한다.
백트래킹(backtracking)
- 답이 될 수 없는 경우는 탐색 대상에서 제외하여 효율적으로 답을 구하는 알고리즘
- 가지치기(pruning)를 통해 연산량의 유의미하게 줄여줌
- 가지치기를 사용하기 위해서는 현재 상태에서 도달할 수 있는 상태가 모두 답이 될 수 없음을 보여야함.
- 정확한 시간 복잡도를 구하기 어려움
분할 정복 | 백트래킹 |
주로 재귀적인 방식으로 해결 | |
하위 문제를 해결하고 결과를 결합하여 문제를 해결 | 문제 해결을 위해 모든 가능한 선택을 시도한 후, 가능성이 없다고 판단되면 이전 단계로 되돌아가거나 이전 결정을 변경 |
'Computer > 알고리즘' 카테고리의 다른 글
문자열 빈출 문제들 (0) | 2024.07.10 |
---|---|
시간복잡도 (0) | 2024.07.08 |
애드혹(ad-hoc) 알고리즘 (0) | 2024.07.02 |
모듈러 연산과 유클리드 호제법 (0) | 2024.06.17 |
비트연산자 활용법 - 비트 bool 배열 확인 (0) | 2024.04.05 |