[코딩테스트/알고리즘] 다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍

 큰 문제를 작은 문제로 나눠서 푸는 알고리즘을 말한다. 1940년 Richard Bellman이 처음으로 Dynamic Programming이란 단어를 사용했는데 멋있어 보여서 이름 붙였다고 한다. (궁금해서 찾아보니까 벨만-포드 알고리즘의 그 벨만이 맞았다.)

다이나믹 프로그래밍으로 문제를 풀기 위한 조건

 1. Overlapping Subproblem

• 문제를 작은 문제로 쪼갤 수 있다.
• 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.

2. Optimal Substructure

• 문제의 정답을 작은 문제의 정답에서 구할 수 있다.

 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. 각 문제들은 Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다. 따라서, 정답을 한 번 구했으면 어딘가에 메모해 두어야 한다. 이렇게 메모하는 것을 코드에서는 배열에 저장하는 것으로 구현한다.

 

 

 

 

예제) 피보나치 수 구하기

 N번째 피보나치 수를 구하는 문제는 N-1번째 피보나치 수를 구하는 문제와 N-2번쨰 피보나치수를 구하는 문제의 합으로 해결할 수 있다.

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

 위 코드는 피보나치 수를 구하는 함수를 재귀적으로 구현한 것이다. 답을 구한 수를 메모하지 않았을 때, 아래 그림과 같이 동일한 함수가 중복 호출되어 비효율적인 것을 볼 수 있다. 한 문제를 풀 때마다 두개의 작은 문제가 생성되기 때문에 O(2ⁿ)의 시간 복잡도를 가지며, n에 큰 수가 들어가면 메모리 초과가 나타나게 된다.

 

 

개선된 피보나치 함수(DP)

public static int fibonacci(int n) {
    int[] memo = new int[100];	//memo[n]의 값은 fibonacci(n)의 값
    if( n <= 1) {
    	return n;
    }
    else {
        if(memo[n] > 0) {
            return memo[n];
        }
        else {
            memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
            return memo[n];
        }
    }
}

위 코드는 답이 구해진 피보나치 수를 메모해 두고, 중복 호출 대신 메모해놓은 값을 반환하도록 하였다. 모든 문제를 한번씩만 풀기 때문에 O(N)의 시간복잡도를 가진다.

 

 

 

다이나믹 프로그래밍의 구현 방식

 

1. Top-down 방식

재귀 호출을 이용해서 문제를 해결한다.

 

1.큰 문제를 작은 문제로 나눈다.

- fibonacci(n)을 fibonacci(n-1)과 fibonacci(n-2)로 나눈다.

 

2. 작은 문제를 푼다.

- fibonacci(n-1)과 fibonacci(n-2)을 푼다.

 

3. 작은 문제를 풀었으면 큰 문제를 푼다.

- fibonacci(n-1)의 값과 fibonacci(n-2)의 값의 합으로 fibonacci(n)을 구한다.

2. Bottom-up 방식

1. 문제를 크기가 작은 문제부터 차례대로 푼다.

 

2. 문제의 크기를 조금씩 크게 만들면서 문제를 풀어나간다.

- i를 증가시킨다.

 

3. 작은 문제를 풀었던 것으로 큰 문제를 해결한다.

- memo[i] = memo[i-1] + memo[i-2]

 

Bottom-up 방식 코드

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

---

다이나믹 프로그래밍 문제

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기