알고리즘 설계 기법

알고리즘 설계 기법이란

알고리즘 설계 기법은 문제를 풀이하는 전략을 고르는 기초다.

백트래킹, 분할정복, 탐욕법, 동적계획법이 대표적인 네 기법이다.

네 기법은 소문제를 다루는 방식이 서로 달라 구분해 두어야 한다.

분할정복

분할정복은 문제를 서로 독립된 소문제로 나눈다.

각 소문제를 같은 방법으로 풀고, 얻은 결과를 병합한다.

시간 복잡도는 분할 횟수와 병합 비용으로 정해진다.

병합정렬은 a=2, b=2, f(n)=O(n)이므로 O(n log n)이다.

소문제가 독립이라 재귀 구현이 자연스럽다.

네 기법 비교

네 기법은 문제 분할 방식, 중복 계산 처리, 최적해 보장 여부로 비교한다.

백트래킹은 가지치기, 분할정복은 독립 분할과 병합이 핵심이다.

탐욕법은 지역 최적 선택이고, 동적계획법은 중복 해를 저장해 재사용한다.

탐욕법은 탐욕 선택 조건과 최적 부분구조가 모두 성립할 때만 최적해를 보장한다.

문제 구조를 보고 기법을 고르는 것이 이 표의 핵심이다.

동적계획법 계산 예

앞 문제의 정답은 동적계획법이다.

0/1 배낭문제는 물건 3개와 용량 5kg으로 계산한다. 가정한 값이다.

점화식은 물건 i개까지 고려했을 때 용량 w의 최대 가치를 구한다.

물건 2를 고려하면 D(2,5)는 max(3, 7)이므로 7이다.

물건 3을 고려한 D(3,5)를 직접 구해 보자.

따라서 최대 가치는 7이며 용량 조건을 지킨다.

헷갈리는 점

첫 번째 실수는 탐욕법을 모든 최적화 문제에 적용하는 것이다.

탐욕법은 탐욕 선택 조건과 최적 부분구조가 모두 있을 때만 최적해를 보장한다.

두 번째 실수는 분할정복과 동적계획법을 혼동하는 것이다. 병합정렬은 분할정복, 피보나치 수열은 동적계획법의 대표 예다.

정리

마지막으로 네 기법을 한눈에 정리한다.

백트래킹은 가지치기로 해가 될 수 없는 경로를 잘라낸다.

분할정복은 독립 분할과 병합, 동적계획법은 중복 소문제의 저장이다.

탐욕법은 조건이 맞을 때만 최적해를 보장한다. 문제 구조로 기법을 고르자.