[Algorithm] 다이나믹 프로그래밍

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5/lecture/12350

알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지

 

인프런 알고리즘 강의 20강에 대한 리뷰이다.

 

 

dp, 동적계획법 

 

하나의 문제를 단 한 번만 풀게 하는 알고리즘

 

참고로 상당 수의 분할정복기법은 하나의 문제를 여러 번 풀게 하는 알고리즘임 (그러나 정렬의 경우 동일한 문제를 다시 푸는 단점이 없음)

 

 

dp 의 경우

 

1. 큰 문제를 작은 문제로 나눌 수 있다

2. 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일하게 작용

 

(작은 문제에서 나온 답을 기록하는 과정을 Memoization 이라고 함)

 

 

피보나치 수열을 예시로 코드를 작성하고자 함 (c++)

 

 

- 동일 문제를 여러 번 수행하는 경우

 

#include <stdio.h>

int dp(int x) {
	if (x == 1) return 1;
	if (x == 2) return 1;
	return dp(x - 1) + dp(x - 2);
}

int main(void) {
	printf("%d", dp(10));
}

 

function dp(x) {
	if (x == 1) return 1;
	if (x == 2) return 1;
	return dp(x - 1) + dp(x - 2);
}

function main() {
    console.log(dp(10));
}

main();

def dp(x):
    if x == 1: return 1
    if x == 2: return 1
    return dp(x - 1) + dp(x - 2)


if __name__ == "__main__":
    print(dp(10))

 

 

다만 조건 없는 재귀를 사용하였기 때문에 x 에 매우 큰 수를 대입하게 되면 작업수행이 오래 걸림

시간복잡도가 O(2**N) 이 됨

 

 

 

- 동일 문제를 한 번만 수행하는 경우 (memoization 이용)

시간복잡도는 O(N)

 

 

#include <stdio.h>

int d[100]; 

int dp(int x) {
	if (x == 1) return 1;
	if (x == 2) return 1;
	if (d[x] != 0) return d[x]; // memoization 이용 
	return d[x] = dp(x - 1) + dp(x - 2);
}

int main(void) {
	printf("%d", dp(30));
//	printf("%d", dp(50)); // overflow 일어나서 음수 값 return 
}

 

 

javascript의 경우 수가 커도 overflow 생기지 않고 온전히 나온다.

let d = new Array(100).fill(0); 

function dp(x) {
	if (x == 1) return 1;
	if (x == 2) return 1;
	if (d[x] !== 0) return d[x]; // memoization 이용 
	return d[x] = dp(x - 1) + dp(x - 2);
}

function main() {
    console.log(dp(30));
    console.log(dp(50));
}

main();

 

python 도 값이 온전히 나온다.

 

def dp(x):
    if x == 1: return 1
    if x == 2: return 1
    if d[x] != 0: return d[x]
    d[x] = dp(x - 1) + dp(x - 2)
    return d[x]


if __name__ == "__main__":
    d = [0] * 100
    print(dp(30))
    print(dp(50))