[알고리즘] 다이나믹 프로그래밍

in Devlog on Algorithm


  • 다이나믹 프로그래밍이란?

    큰 문제를 작은 문제로 나눠서 푸는 알고리즘

    Dynamic Programming의 Dynamic은 아무의미가 없음

    즉, 동적계획법의 동적이란 의미가 아님!

    (1940년 Richard Bellman은 멋있어보여서 사용함)

    ​

  • 다이나믹 프로그래밍의 조건

    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번째 피보나치 수를 구하는 문제

      작은 문제 : N-3번째 피보나치 수를 구하는 문제, N-4번째 피보나치 수를 구하는 문제

    • 결론

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

  • Optimal Substructure

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

    • 예시

      서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면

      대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야 한다

    • 피보나치

      문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다

    • 결론

      Optimal Substructure를 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정함

      10번 째 피보나치 수를 구하면서 구한 4번째 피보나치 수

      9번 째 피보나치 수를 구하면서 구한 4번째 피보나치 수

      …

      5번 째 피보나치 수를 구하면서 구한 4번째 피보나치 수

      4번 째 피보나치 수를 구하면서 구한 4번째 피보나치 수

      즉, 4번째 피보나치 수는 항상 같다

  • 다이나믹 프로그래밍

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

  • 피보나치 수

    int fibonacci (int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}
    • fibonacci(5) 를 수행했을 경우

    • 초록색으로 칠해진 f(3)이 왼쪽과 오른쪽에서 중복되므로
    • 오른쪽의 f(3)을 중복적으로 처리할 필요가 없음
    int fibonacci (int n) {
    if (n <= 1) {
        return n;
    } else {
    	if (memo[n] > 0) {
            return memo[n]; // 다시 계산하지 않고 return
    	}
    	memo[n] = fibonacci(n-1) + fibonacci(n-2);
    	return memo[n];
    }
}

  • 다이나믹 프로그래밍

    1. Top-down : 큰 문제를 점점 작게 풀어나가는 방법
    2. Bottom-up : 작은 문제부터 풀어가는 방법
    • 구현을 어떻게 하냐의 차이일 뿐, 둘 중 하나만 먼저 잘하는 것도 좋다

  • Top-down

    1. 문제를 작은 문제로 나눈다.
    2. 작은 문제를 푼다.
    3. 작은 문제를 풀었으니, 이제 문제를 푼다.

  • Top-down

    1. 문제를 풀어야 한다
      • fibonacci(n)
    2. 문제를 작은 문제로 나눈다
      • fibonacci(n-1) 과 fibonacci(n-2) 로 문제를 나눈다.
    3. 작은 문제를 푼다.
      • fibonacci(n-1)과 fibnoacci(n-2)를 호출해 문제를 푼다.
    4. 작은 문제를 풀었으니, 이제 문제를 푼다.
      • fibonacci(n-1)의 값과 fibonacci(n-2)의 값을 더해 문제를 푼다.
    • 보통 재귀함수를 이용해서 풀음
    • 시간복잡도 계산 (피보나치의 경우 O(N))
      • 채워야 하는 칸의 수 x 1칸을 채우는 복잡도
        • 채워야 하는 칸의 수 : memo 배열에 몇개의 수가 채워질 것인가
        • 피보나치의 경우 n개가 채워짐
        • 1칸을 채우는 복잡도
          • fibonacci 의 경우 더하는 것 하나밖에 없기 때문에 O(1) 이라는 시간복잡도가 표현됨

  • Bottom-up

    1. 문제를 크기가 작은 문제부터 차례대로 푼다.
    2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
    3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
    4. 그러다보면, 언젠간 풀어야 하는 문제를 풀 수 있다.
    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];
}
    • 제일 작은문제 (i=2) 부터 제일 큰문제 (i<=n) 까지 푼다

  • Top-down 은 재귀를 이용, Bottom-up 은 for문을 이용

  • 피보나치에서 변수 표현

    • memo[i] = i 번째 피보나치 수
    • d[i] , dp[i] 정도로 표현함
    • i-1번째 피보나치 수 = d[i-1]
    • i-2 번째 피보나치 수 = d[i-2]
    • d[i] = d[i-1] + d[i-2]

  • 다이나믹 문제풀이 전략

    • 문제에서 구하려고 하는 답을 문장으로 나타낸다
    • 예: 피보나치 수를 구하는 문제
    • N번째 피보나치 수
    • 이제 그 문장에 나와있는 변수의 개수만큼 메모하는 배열을 만든다
    • Top-down 인 경우에는 재귀 호출의 인자의 갯수
    • 문제를 작은 문제로 나누고, 수식을 이용해서 문제를 표현해야 한다

  • 다이나믹 프로그래밍 문제

    1. 1로 만들기
    2. 2xn 타일링
    3. 2xn 타일링 2
    4. 1, 2, 3 더하기
    5. 붕어빵 판매하기



© 2018. by HYEON

Powered by HYEON