[ALGORITHM] 동적 계획법 (Dynamic Programming)

개념

---

동적 프로그래밍(DP)은 복잡한 문제를 단순한 하위 문제로 나누어 푸는 방법으로 같은 입력값에 대한 반복되는 호출을 하는 솔루션을 만났을 때 사용합니다.

주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산 후 결과값을 이용하면 원래 문제의 답을 효율적으로 구할 수 있습니다. 

 

💡 다이나믹 프로그래밍은 하나의 문제를 단 한 번만 풀도록 하는 알고리즘으로 구체적인 알고리즘이라긴 보단, 문제 해결 패러다임에 가깝습니다.

 

[ 🤔 탐욕 알고리즘과 다른점 ]

둘 다 최적의 값을 찾는다는 점에서 비슷하지만, 다른 방법으로 찾습니다.

탐욕 알고리즘	전체의 값을 찾기 위해 지역적으로 탐욕적인 선택을 찾음 → 비용이 많이 들며, 전역적으로는 최적의 알고리즘을 보장하지 않을 수 있음
동적 프로그래밍	전체의 값을 찾기 위해 하위 문제에 대한 최적의 값을 찾은 다음 결과를 결합함

알고리즘 과정

---

[ 동적 프로그래밍의 선행 조건 2가지]

1. 겹치는 부분 문제 (Overlapping Subproblem) 찾기

먼저, 복잡한 문제를 하위 문제로 나누어 풀기 위해선, 같은 부분 문제가 여러번 재사용되거나 재귀 알고리즘을 통해 해결되는 문제를 찾아야 합니다.

피보나치 수를 예를 들면 fib(4)를 다음 하위 문제로 나누었을 때, fib(2)와 fib(1)이 반복되는 재귀알고리즘을 통해 해결할 수 있다는 것을 찾을 수 있습니다.

 

2. 최적의 하위 구조 (Optimal Substructure) 찾기

겹치는 부분 문제를 찾았다면, 이제 최적의 하위 구조 속성을 찾아 수식을 정리합니다.

💡 최적의 하위 구조란 문제의 최적의 해결책이 해당 문제의 하위 문제의 해결책으로부터 설계될 수 있는 경우로, 문제의 정답을 작은 문제의 정답에서부터 구할 수 있음을 나타냅니다.

Fib(n) = Fib(n-1) + Fib(n-2)

위와 같이 'n' 크기의 문제가 'n-1' 및 'n-2' 크기의 하위 문제로 축소되었음을 분명히 보여줍니다. 따라서 피보나치 수는 최적의 하위 구조 속성을 갖습니다.

[ 알고리즘 동작 과정 ]

🙌 동적 프로그래밍은 문제를 해결하는 두 가지 방법이 있습니다.

1. 메모리제이션을 이용한 하향식 (Top-down)

큰 문제를 작은 문제로 쪼개면서 푸는 기법으로 재귀로 구현합니다.

- 문제를 작은 문제로 나눕니다.

- 작은 문제를 풀고 결과를 메모리제이션합니다.

- 작은 문제를 가지고, 원래 문제의 결과를 구합니다.

public int Recursive(int[] memoize, int n) {
	if(n < 2)
		return n;

	if(memoize[n] != 0)
		return memoize[n];
	
	memoize[n] = Recursive(memoize, n-1) + Recursive(memoize, n-2);
	return memoize[n];
}

위의 코드를 보면, memoize[n]에 작은 문제의 결과를 메모리제이션 한 후, 문제의 결과를 구합니다.

💡 메모리제이션이란 이미 해결된 문제의 결과를 캐싱(저장)해 같은 문제가 여러번 해결되지 않도록 결과를 저장하는 기술입니다. 최상위 문제를 먼저 해결한다는 의미에서 하향식으로 수행합니다.

2. 표를 이용한 상향식(Bottom-up)

작은 문제부터 차례대로 풀는 기법으로 반복문으로 구현합니다.

- 문제를 작은 문제부터 풉니다.

- 문제의 크기를 크게 만들면서 순서대로 값을 구합니다.

- 반복해 배열의 결과를 기반으로 원래 문제의 결과를 구합니다.

int dp[] = new int[n+1];

dp[0] = 0;
dp[1] = 1;

for(int i=2; i<=n; i++){
  dp[i] = dp[i-1] + dp[i-2];
}

위의 코드를 보면, dp[9]를 구하기 위해 dp[0], dp[1], dp[2] ... dp[9]의 순서대로 값을 구한 후, 해당 값을 가지고 다음 값을 구합니다.

구현 with JAVA

---

1. 메모리제이션을 이용한 하향식 (Top-down)

class Fibonacci {

  public int Calc(int n) {
    int memoize[] = new int[n+1];
    //문제를 작은 문제로 나눕니다.
    return Recursive(memoize, n);
  }

  public int Recursive(int[] memoize, int n) {
    if(n < 2)
      return n;

    if(memoize[n] != 0)
      return memoize[n];
	
    //작은 문제를 풀고 결과를 메모리제이션합니다.
    memoize[n] = Recursive(memoize, n-1) + Recursive(memoize, n-2);
    return memoize[n];
  }

  public static void main(String[] args) {
    Fibonacci fib = new Fibonacci();
    fib.Calc(5);
    fib.Calc(6);
    fib.Calc(7);
  }
}

2. 표를 이용한 상향식(Bottom-up)

class Fibonacci {

  public int Calc(int n) {
    if (n==0) return 0;
    int dp[] = new int[n+1];

    dp[0] = 0;
    dp[1] = 1;

	//문제의 크기를 크게 만들면서 순서대로 값을 구합니다.
    for(int i=2; i<=n; i++)
      dp[i] = dp[i-1] + dp[i-2];

	//반복해 배열의 결과를 기반으로 원래 문제의 결과를 구합니다.
    return dp[n];
  }

  public static void main(String[] args) {
    Fibonacci fib = new Fibonacci();
    fib.Calc(5);
    fib.Calc(6);
    fib.Calc(7);
  }
}

참고자료

---

- https://www.programiz.com/dsa/dynamic-programming
- https://en.wikipedia.org/wiki/Dynamic_programming
- https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews/m2G1pAq0OO0
- https://blog.naver.com/ndb796/221233570962
- https://velog.io/@polynomeer/동적-계획법Dynamic-Programming
- https://velog.io/@nninnnin7/Dynamic-programming-1