[알고리즘] DP(Dynamic Programming)란?

DP란?

다이나믹 프로그래밍은 동적 계획법이라고도 불리는 알고리즘으로 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘입니다.

 

DP는 아래와 같은 조건이 충족되면 적용할 수 있습니다.

• problem이 더 작은 sub-problem들로 쪼개질 수 있을때
• sub-problem들의 솔루션으로 더 큰 규모의 problem의 솔루션을 구할 수 있을 때
• 쪼개진 sub-problem들이 겹칠 때

즉, 큰 문제를 작은 문제로 나누어 풀어 저장(Memoization) 함으로써, 한 번 계산한 문제는 다시 계산하지 않도록 합니다.

---

Top-Down vs Bottom-up

DP로 풀이하는 방법은 크게 2가지, Top-Down 방식과 Bottom-up방식으로 나뉩니다.

 

Top-Down 방식

우리말로 '하향식'이라고도 하며 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식입니다.

• 보통 재귀 호출을 통해 답을 구함
• 함수 호출의 횟수를 줄이기 위해 *메모이제이션 기법이 사용됨

 

*메모제이션 기법

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프래그램 실행 속도를 빠르게 하는 기술

 

예를 들어 dp[n]에 피보나치 수열의 값을 저장함으로써 메모제이션 기법을 사용하는 방법은 다음과 같습니다.

const N = 10;
const dp = Array.from({length: N+1}, () => -1);
const fibonacci = (n) => {
    if (n == 0) return 0;
    if (n == 1) return 1;

    if (dp[n] != -1) return dp[n];

    dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return dp[n];
}

console.log(fibonacci(10)); // 55

 

Bottom-Up 방식

우리말로 '상향식'이라고도 하며 가장 작은 문제들부터 답을 찾아 가면서 마지막에는 전체 문제의 답을 구하는 방식입니다.

• 보통 반복문을 이용해 구현
• 재귀 호출을 하지 않으므로 시간과 메모리의 사용량이 상대적으로 적다는 이점이 있음

예를 들어 피보나치 수열의 값을 구하면 다음과 같습니다.

 

const N = 10;
const dp = Array.from({length: N+1}, () => -1);
const fibonacci = (n) => {
    dp[0] = 0, dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
}
fibonacci(10);
console.log(dp);
// [ 0, 1,  1,  2,  3, 5, 8, 13, 21, 34, 55 ]

 

두 방식의 구현 난이도가 문제마다 굉장히 다르기 때문에 DP문제 상황에 따라 방법을 선택하게 됩니다.

---

[참고]

https://velog.io/@kimdukbae/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

https://www.youtube.com/watch?v=eJC2oetXaNk 

https://velog.io/@chnh506/Top-down-%EB%B0%A9%EC%8B%9D%EA%B3%BC-Bottom-up-%EB%B0%A9%EC%8B%9D

Top-down 방식과 Bottom-up 방식