티스토리 뷰

다이나믹 프로그래밍은 줄여서 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)의 시간복잡도를 가지게 된다.

 

 

공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
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
글 보관함