티스토리 뷰
다이나믹 프로그래밍은 줄여서 DP라고도 하고, 동적 계획법이라고도 불린다.
다이나믹 프로그래밍이란 '하나의 문제는 단 한번만 풀도록 하는 알고리즘'이다.
일반적으로 상당수 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다. (다만 분할 정복 기법은 '정렬'과 같은 몇몇 요소에 대해서는 동일한 문제를 다시 풀게 되는 단점이 없습니다. 그 예시로 퀵 정렬이나 병합 정렬은 매우 빠릅니다.)
단순 분할 정복으로 풀게 되면 심각한 비효율성을 낳는 대표적인 예시로는 피보나치 수열이 있다.
피보나치 수열의 점화식: D[i] = D[i - 1] + D[i - 2]
다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있다.
1번 가정. 큰 문제를 작은 문제를 나눌 수 있다.
2번 가정. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
즉, 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것이다. 다만 이 과정에서 '메모이제이션'이 사용된다는 점에 분할 정복과 다르다. 이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환하기만 하면 되는 것이다.
피보나치 수열을 예로 들어 확인해보자.
#include <stdio.h>
// 2^n의 시간복잡도를 가진다.
int dp(int x) {
if(x == 1)
return 1;
if(x == 2)
return 1;
return dp(x- 1) + dp(x - 2);
}
int main() {
printf("%d", dp(10));
}
#include <stdio.h>
int d[100];
// O(n)의 시간복잡도를 가진다.
int dp(int x) {
if(x == 1)
return 1;
if(x == 2)
return 1;
if(d[x] != 0)
return d[x];
return d[x] = dp(x- 1) + dp(x - 2);
}
int main() {
printf("%d", dp(10));
}
메모이제이션 기법을 사용할 경우 트리구조가 아닌 일직선으로 내려가게 되면서 O(n)의 시간복잡도를 가지게 된다.
'Algorithm > Algorithm' 카테고리의 다른 글
플로이드 와샬 알고리즘(Floyd Warshall Algorithm) (0) | 2020.07.25 |
---|---|
다익스트라 알고리즘(Dijkstra Algorithm) (0) | 2020.07.25 |
크루스칼 알고리즘(Kruskal Algorithm) (0) | 2020.07.21 |
★ Union-Find 합집합 찾기 (0) | 2020.07.19 |
C++ / 힙 정렬(Heap Sort) (0) | 2020.07.15 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 공용체
- 자료구조
- 1차원 배열
- 배열
- 파이썬
- 직접 지정
- 프로그래밍
- inflearn
- codeit
- 회전리스트
- 구조체
- 3차원 배열
- call by reference
- 재귀함수
- 비트필드
- 공간복잡도
- call by value
- 강의
- Algorithm
- 시간복잡도
- 간접 지정
- C
- 형승격
- 다차원 배열
- 포인터
- 공부
- 2차원 배열
- timecomplexity
- 알고리즘
- 종류
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함