다이나믹 프로그래밍

다이나믹 프로그램이란?

큰 문제를 작은 문제로 나누어 푸는 방법은 크게 두 가지가 존재하는데 하나는 분할정복(Divid & Conqer)이고, 나머지 하나가 다이나믹 프로그램이다. 이 둘의 차이점은 다이나믹 프로그래밍은 큰 문제가 작은 문제로 나누어서 졌을 때 작은 문제들의 중복이 허용되지만 분할정복은 중복이 허용되지 않는 점을 차이점으로 꼽을 수 있다.

다이나믹 프로그래밍의 속성

1. Overlapping Subproblem.

한국말로 하면 겹치는 부분문제인데 큰 문제를 작은 문제로 나누었을 때에 겹치는 부분, 즉 작은 문제에서 중복이 발생 된다는 의미를 지닌다.

EX) 피보나치 수열
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 (n >= 2)
문제 : N번째 피보나치 수를 구하는 문제
작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제

문제 : N-1번째 피보나치 수를 구하는 문제
작은 문제 : N-2번째 피보나치 수를 구하는 문제, N-3번째 피보나치 수를 구하는 문제

문제 : N-2번째 피보나치 수를 구하는 문제
작은 문제 : N-3번째 피보나치 수를 구하는 문제, N-4번째 피보나치 수를 구하는 문제

-> 겹치는 부분이 발생한다.

2. Optimal Subproblem.

한국말로 하면 최적부분구조인데 문제의 정답이 작은 문제들을 통해 풀 수 있다는 의미를 지닌다.

EX) 서울에서 부산을 가장 빠른 길이 대전과 대구를 순서대로 거쳐야한다. 서울 -> 대전 -> 대구 -> 부산
그렇다면 대전에서 부산을 가큰 가장 빠른 길은 대구를 거쳐야한다. 대전 -> 대구 -> 부산

정리

1. 다이나믹 프로그래밍은 모든 문제를 한번만 푼다.
2. Optimal Subproblem을 만족하기 때문에 같은 문제는 구할 때마다 같아야한다.
3. 정답을 한 번 구했으면 정답을 저장해야한다.
4. 코드에서 정답을 저장하기 위해서는 배열을 사용할 수 있다.
5. 메모를 한다해서 영어로 Memoization이라고 한다.

피보나치 수열

중복이 생기는 피보나치 수열
시간복잡도 : O(2^N)

int fibonacci(int n){
	if(n <= 1)
    	return n;
    else
    	return fibonacci(n-1) + fibonacci(n-2);
}

중복이 생기 않는 피보나치 수열
시간복잡도 : 문제의 개수 x 문제 1개를 푸는 시간(함수의 시간복잡도)= N x 1 = O(N)

// Top - down
int memo[100];
int fibonacci(int n){
	if(n <= 1)
    	return n;
    else{
    	if(memo[n] > 0)
        	return memo[n];
    	memo[n] = fibonacci(n-1) + fibonacci(n-2);
    	return memo[n];
    }
}

// Bottom - up
int memo[100];
int fibonacci(int n){
	memo[0] = 0;
    memo[1] = 1;
    for(int i=2; i<=n; i++)
    	memo[i] = memo[i-1] + memo[i-2];
    return memo[n];
}

다이나믹 구현 방법

Top - down

큰 문제를 작게 쪼개 가면서 작은 문제를 만들어 정답을 구해 다시 합쳐 큰 문제를 푸는 것이다. - 재귀

Bottom - up

작은 문제들을 모아 큰 문제를 만드는 방법. - 반복문

문제풀이 전략

문제에서 구하려고 하는 답을 문장으로 나타낸다. 즉, 문제를 점화식으로 표현한다.