Algorithm Study #3 (Dynamic Programming (DP) - 1.1)

다이나믹 프로그래밍 1

• 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
• Dynamic Programming의 다이나믹은 아무 의미가 없다.
  - 동적 계획법으로 번역하여 이해하면 오히려 방해가 될 수 있다.
• 이 용어를 처음 사용한 140년 Richard Bellman은 멋있어 보여서 사용했다고 한다.
  - https://en.wikipedia.org/wiki/Dynamic_programming#History
• 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.
  1. Overlapping Subproblem
  - 겹치는 부분 문제가 있어야 한다.
  2. Optimal Substructure
     • 문제의 정답을 작은 문제의 정답에서 구할 수 있어야 한다

Overlapping Subproblem

• 피보나치 수의 예
  - F0 = 0
  - F1 = 1
  • Fn = Fn-1 + Fn-2 (N>=2)
    - 작은 문제로 큰 문제의 정답을 구할 수 있다.
    • 큰 문제 : N번째 피보나치 수를 구하는 문제
      - 작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제
      • 큰 문제 : N-1번째 피보나치 수를 구하는 문제
        - 작은 문제 : N-2번째 피보나치 수를 구하는 문제, N-3번째 피보나치 수를 구하는 문제
      • ....
        - 작은 문제들이 겹치고 있다. -> 'N-2번째 피보나치 수를 구하는 문제'
  • 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.
• 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
• 문제를 작은 문제로 쪼갤 수 있다.
• Optimal Substructure를 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.

Optimal Substructure

• 문제의 정답을 작은 문제의 정답에서 구할 수 있다.
• 예시
  - 서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면
  - 서울 > 대전 > 대구 > 부산
  • 대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야 한다.
    • 대전 > 대구 > 부산

다이나믹 프로그래밍

• 다이나믹 프로그래밍에서 각 문제는 한번만 풀어야 한다.
• Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다.
• 따라서 정답을 한 번 구했으면, 정답을 어딘가 메모해놓는다.
• 이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다.
• 메모를 한다고 해서 영어로 Memoization이라고 한다.
  - 메모지에 적혀있는 것은 또 물어볼 필요가 없다...
  - 컴퓨터에서는 배열이 이런 역할을 한다.

피보나치 수 (in Dynamic Programming)

• 재귀를 이용한 간단한 구현

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

• 피보나치 5를 구할 경우 피보나치 트리의 이미지
  - https://upload.wikimedia.org/wikipedia/commons/e/ea/Fibonacci_Tree_5.svg
• DP로 풀기
  - memo[n]에 n번째 피보나치 수를 저장한다.

  	```java
  	int memo[100];
  	int fibonacci(int n) {
  if (n <= 1) {
  	return n; 
  } else {
    if (memo[n] > 0) { // 이미 계산되어 Memoization 된 상태라면 그대로 이용 !
      return memo[n]; 
    }
    memo[n] = fibonacci (n-1) + fibonacci (n-2);
    return memo[n];
  }

  }

  	```

다이나믹 프로그래밍 문제풀이 방법론

1. Top-down
   • 문제 풀이 순서
     1. 문제를 풀어야 한다.
     - fibonacci(n)
     2. 문제를 작은 문제로 나눈다.
        • fibonacci(n-1)과 fibonacci(n-2)로 문제를 나눈다.
     3. 작은 문제를 푼다.
        • fibonacci(n-1)과 fibonacci(n-2)를 호출해 문제를 푼다.
          4. 작은 문제를 풀었으니, 이제 문제를 푼다.
          - fibonacci(n-1)의 값과 fibonacci(n-2)의 값을 더해 문제를 푼다.
   • 주로 재귀의 형식으로 구현된다.
   • 큰 계산을 작은 계산으로 위에서부터 나눠간다.
   • 시간복잡도를 계산하는 방법이 조금 까다롭다.
     - 채워야 하는 칸의 수
     - memo의 배열에 총 몇 개의 수를 채울 것인가?
     - 한 칸을 채우는 데 필요한 복잡도를 계산하면 된다.
     
2. Bottom-up
   • 문제 풀이 순서
     1. 문제를 크기가 작은 문제부터 차례대로 푼다.
     2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
     3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
     4. 그러다보면, 언젠간 풀어야 하는 문제를 풀 수 있다.
   • 일반적으로 for문을 이용하여 구현한다.

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

문제 풀이 전략

• memoization이 되는 memo 배열에 어떤 것을 어떻게 넣어줘야 할 지가 중요하다.
• 문제에서 구하려고 하는 답을 문장으로 나타낸다.
  - 피보나치 수에서는 N번째 피보나치 수
• 이제 그 문장에 나와있는 변수의 개수만큼 메모하는 배열을 만든다.
• Top-down인 경우에는 재귀 호출 인자의 개수
• 문제를 작은 문제로 나누고 수식을 이용해서 문제를 표현해야 한다.