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

다이나믹 프로그래밍 (Dynamic Programming, DP)란?

• 다이나믹 프로그래밍 (이하 DP)란 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘이다.
• 분할정복과 비슷하다고 생각할 수 있지만 분할정복은 작은 문제가 중복이 일어나지 않고, DP는 반복(작은 문제의 결과가 같다)된다. 그래서 DP에서는 작은 문제들이 반복되는 것을 이용해 문제를 풀어나간다.
• 포인트는 모든 작은 문제들은 중복을 제거하고 한번만 풀어야 한다는 점이다. 따라서 정답을 구한 작은 문제들을 어딘가에 메모(Memoization)해둔다. 다시 그보다 큰 문제를 풀 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다.

 

많이 언급하는 피보나치 수열 문제를 예시로 들어보자.

// 재귀로 문제를 풀 경우
// O(1.618^n)의 시간이 걸림

function fibo(n) {
	if (n <= 1) return 1;
    	return fibo(n-1) + fibo(n-2);
}

// DP로 문제를 풀 경우
// O(N)

function fibo(n) {
	arr 선언;
    	arr[0] = arr[1] = 1;
    	for (int i=2; i <= n; i++)
    		arr[i] = f[i-1] + f[i-2];
    	return arr[n];
}

---

DP로 푸는 문제인가? 생각해야할 경우

• 작은 문제가 반복이 일어나는 경우
• 반복이 일어나는데 반복될 때마다 정답이 같아야 함

---

DP를 푸는 방법

1. 테이블 정의하기
2. 점화식 찾기 (작은 문제들을 해결해본다. 규칙 찾기 -> 점화식 도출)
3. 초기값 정하기

-> 문제를 많이 풀어보자!

-> 대표적인 문제: 막대기 자르기 문제, 최장 공통 부분 수열 문제, 0/1 배낭 문제

---

DP 구현 방법의 종류

Bottom-up

작은 문제부터 차근차근 구해나아가는 방법. 위에서 언급한 피보나치를 예시로 들어보자.

// Bottom-up으로 푸는 경우

function fibonacci_bottom_up(n) {
    if (n <= 1):
        return n;
    first = 0;
    second = 1
    for (int i=0; i < n-1; i++) {
        next = first + second
        first = second
        second = next
    }
    return next
}

 

Top-down

큰 문제를 풀 때 작은 문제가 아직 풀리지 않았다면 그때 작은 문제를 해결함. 이때 작은 문제를 푼 기록을 해두는게 중요하다. 재귀함수로 구현하는 경우 대부분 이 경우인 방법이 많다.

// Top-down 으로 푸는 경우

function fibonacci_top_down(n) {
    if (memo[n] > 0) return memo[n];
    if (n <= 1) {
        memo[n] = n;
        return memo[n]
    } else {
        memo[n] = fibonacci_top_down(n-1) + fibonacci_top_down(n-2)
        return memo[n]
    }
}

 

 

References

https://galid1.tistory.com/507

https://blog.encrypted.gg/974?category=773649