| 알고리즘 | 풀이 가능한 문제들의 특징 | 풀이 가능한 문제 및 알고리즘 |
|---|---|---|
| 다이나믹 프로그래밍 | 최적 부분 구조(Optimal Substructure) 중복된 하위 문제들(Overlapping Subproblems) | 0-1 배낭문제 피보나치 수열 다익스트라 알고리즘 |
| 그리디 알고리즘 | 최적 부분 구조(Optimal Substructure) 탐욕 선택 속성(Greedy Choice Property) | 분할 가능 배낭 문제 다익스트라 알고리즘 |
| 분할 정복 | 최적 부분 구조(Optimal Substructure) | 병합 정렬 퀵 정렬 |
다이나믹 프로그래밍
다이나믹 프로그래밍(Dynamic Programming, DP) 알고리즘은 리차드 벨만 1953년에 고안한 알고리즘으로
(최단거리를 구하는 벨만-포드 알고리즘과 머신러닝 분야 '차원의 저주'라는 이론을 만든 수학자이다.)
중복된 하위 문제들의 결과를 저장(메모제이션)했다가 큰 문제의 결과와 합하여 풀이하여 최적 부분 구조 문제를 풀이 하는데 쓰인다.
최적 부분 구조
-최단 경로를 찾는 최적 부분 구조 문제
위 그림을 보면 [서울 -> 대구] 경로, [대구 ->부산] 경로 각각 3가지가 있다.
여기서 [서울 -> 부산] 경로의 최단 거리는 [서울 -> 대구] 가는 최단 경로 와 [대구 -> 부산] 가는 최단 경로 의 합이다.
따라서 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성되며 이러한 구조를 최적 부분 구조라고 한다.
이러한 최적 부분 구조 문제들은 다이나믹 프로그래밍, 그리디 알고리즘, 분할 정복으로 풀 수 있다.
중복된 하위 문제들
다이나믹 프로그래밍으로 풀 수 있는 문제들과 다른 문제들의 차이는 중복된 하위 문제들을 갖는다는 점이다.
그 예로는 피보나치 수열이 있다.
피보나치 수열
f(5) = f(4) + f(3) = 5
| |
| f(3) = f(2) + f(1) = 2
| | |
| | f(1) = 1
| |
| f(2) = 1
|
f(4) = f(3) + f(2) = 3
| |
| f(2) = 1
|
f(3) = f(2) + f(1) = 2
| |
| f(1) = 1
|
f(2) = 1f(3) = f(2) + f(1)이고, f(4) = f(3) + f(2)이다. 이처럼 피보나치 수열을 재귀적으로 반복해서 풀면 동일한 하위 문제들이 발생하는데, 이 부분이 중복된 하위 문제들 이다.
다이나믹 프로그래밍, 그리디 알고리즘, 분할 정복의 공통점, 차이점
위의 언급했듯이 그리디 알고리즘, 분할 정복 모두 다이나믹 프로그래밍의 공통점은 모두 최적 부분 구조 문제를 풀이하는데 쓰는 알고리즘이라는 점이다.
그러나 그리디 알고리즘은 항상 그 순간에 최적이라고 생각되는 것을 선택해서 풀이하는 방법이며,
다이나믹 프로그래밍은 위에서 설명했듯이 중복된 하위 문제들의 결과를 저장했다가 합하여 풀이하는 방법이고,
분할 정복은 중복되지 않는 문제를 나눌 수 있는 가장 작은 단위로 문제를 나누어 해를 구하고 그 해를 합하여 문제를 해결하는 방법이다.
이렇듯 최적 부분 구조라는 공통점이 있지만 위와 같은 차이점이 있으니, 문제의 요점을 정확히 파악하여 적절한 알고리즘으로 풀이하는 것이 중요하다.
다익스트라 알고리즘
위에 표를 있듯이
다익스트라 알고리즘은 다이나믹 프로그래밍 과 그리디 알고리즘 둘 다 해당하는 알고리즘으로, BFS(Breath First Search) 시 항상 최단 경로를 찾는 탐욕 선택 속성을 갖는 그리디 알고리즘이면서, 이미 계산한 경로를 저장 헀다가, 중복된 하위 문제들을 푸는 다이나믹 알고리즘 이다.
('최적 부분 구조', '중복된 하위 문제들', '탐욕 선택 속성'을 모두 갖는 알고리즘이다.)
다이나믹 프로그래밍 방법론
다이나믹 프로그래밍의 방법론은 크게 2가지로 나뉜다.
더 작은 문제의 정답을 이용해 더 큰 문제를 풀어나가는 상향식(타뷸레이션) 방법과,
하위 문제에 대한 정답을 계산했는지 확인(메모제이션)하는 하향식 방법이다.
상향식(타뷸레이션, 반복)
상향식 방법론은 '타뷸레이션'이라 하며 반복을 통해 아래와 같이 구현한다.
(데이터를 테이블 형태로 만들면서(Tablulate) 푼다하여 타뷸레이션 이라 부른다.)
def fin(n):
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]하향식(메모제이션, 재귀)
하향식 방법론은 하위 문제에 대한 정답을 계산했는지 확인해가며, 재귀 형태로 풀어가며,
이미 푼 하위 문제를 재활용하는 메모제이션 방식을 사용한다.
def fin(n):
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]정리
대부분의 다이나믹 프로그래밍은 어렵기 때문에, 인터뷰 시 다양한 문제를 출제하기 쉽지 않다.
따라서 가장 기본인 피보나치 수열 문제가 주로 나오며, 해당 문제는 재귀와 다이나믹 프로그래밍을 한번에 평가 할 수 있는 매우 좋은 문제이기도 하다.
따라서 해당하는 문제들을 중점으로 준비해 나가는 것이 좋지 않나 싶다.
Reference)
- 파이썬 알고리즘 인터뷰
