Dynamic_Programming.md

동적 계획법 (Dynamic Programming)

동적 계획법 (Dynamic Programming)

• DP는 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하고 다시 큰 문제를 해결할 때 사용하는 것으로 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있음
• 일반적인 재귀 방식과 매우 유사한데 가장 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산될 수 있는데 이를 방지
• 분할 정복과 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결하는 부분은 동일하나 분할 정복은 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰고, 동일한 중복이 일어나면 동적프로그래밍을 쓴다

DP 사용 조건

• DP가 적용되기 위해서는 Overlapping Subproblems, Optimal Substructure 두가지 조건을 만족해야함
• Overlapping Subproblems(겹치는 부분 문제)
  • DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구함. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능
  • 즉 DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없음
  • ex) 피보나치 수열의 경우 f(x) = f(x-1) + f(x-2)인데 해당 계산들을 반복하다보면
• Optimal Substructure(최적 부분 구조)
  • 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일
  • 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 경우 DP 사용 가능
  • 즉, Optimal Substructure를 만족하면, 문제의 크기에 관계없이 특정 문제에 대한 정답은 항상 일치함

DP 사용하기

• DP는 특정한 경우에 사용하는 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰일 수 있음
• 일반적으로는 아래의 DP 과정을 거쳐 진행할 수 있음
  1. DP로 풀 수 있는 문제인지 확인
     • 현재 직면한 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지 판단해야함
     • 위에서 쓴 조건들이 충족되는 문제인지를 한번 체크해보는 것이 좋음
  2. 문제의 변수 파악
     • DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 것을 거침. 즉 문제 내 변수의 개수를 알아내야 한다는 것. 이것을 영어로 "state"를 결정한다고 함
     • 예를 들어 피보나치 수열에 경우 n번째 숫자를 구하는 것이므로 n이 변수가 되고 변수가 얼마이냐에 따라 결과값이 다르지만 그 결과를 재사용하고 있음
  3. 변수 간 관계식 만들기(점화식)
     • 변수들에 의해 결과 값이 달라지지만 동일한 변수값인 경우 결과는 동일
     • 또한 우리는 그 결과값을 그대로 이용할 것이므로 그 관계식을 만들어낼 수 있어야함. 그러한 식을 점화식이라고 함
     • 점화식을 통해 짧은 코드 내에서 반복/재귀를 통해 문제가 자동으로 해결되도록 구축할 수 있게 됨
  4. 메모하기 (memoization or tabulation)
     • 변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장해야 함
     • 변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고, 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나감
  5. 기저 상태 파악하기
     • 여기까지 진행했다면 가장 작은 문제의 상태를 알아야 함
     • 피보나치 수열을 예시로 들면 f(0) = 0, f(1) = 1
     • 해당 기저 문제에 대해 파악 후 미리 배열 등에 저장해두면 됨. 문제에 따라 복잡할 수 있음
  6. 구현하기
     • DP는 Bottom-Up, Top-Down으로 2가지 방식으로 구현 가능
     • Bottom-Up (Tabulation 방식) -> 반복문 사용
     • Top-Down(Memoization 방식) -> 재귀 사용

점화식
- 어떤 수열의 각각의 항들의 관계를 나타낸 식

DP 구현방법

1. Bottom-UP (반복)

• 작은 문제로부터 큰 문제로 올라가는 반복문을 이용한 방식
• Bottom-UP의 핵심은 크기가 작은 문제부터 차례로 풀고 문제를 크게 만들어나가며 풀이하고 이 과정을 계속 반복하면 원하는 큰 문제를 풀 수 있음

public static int bottomUp(int n){
    // 기저 상태의 경우 사전에 미리 저장
    bottomup_table[0] = 0; 
    bottomup_table[1] = 1;
    
    // 반복문을 사용하고 있음!
    for(int i=2; i<=n; i++){
        // Table을 채워나감!
        bottomup_table[i] = bottomup_table[i-1] + bottomup_table[i-2];
    }
    return bottomup_table[n];
}

2. Top-Down (재귀)

• 큰 문제에서 작은 문제로 내려가는 재귀를 이용한 방식
• Top-Down의 핵심은 문제를 작은 문제로 나누고 작은 문제를 풀고 풀이한 작은 문제를 바탕으로 큰 문제를 푸는 사고로 이루어짐
• 어떠한 정답을 구하면 그 정답을 메모해두고 메모를 이용하는 방식을 메모리제이션(Memorization)이라고 부름

public static int topDown(int n){
    // 기저 상태 도달 시, 0, 1로 초기화
    if(n < 2) return topDown_memo[n] = n;
    
    // 메모에 계산된 값이 있으면 바로 반환!
    if(topDown_memo[n] > 0) return topDown_memo[n];
    
    // 재귀를 사용하고 있음!
    topDown_memo[n] = topDown(n-1) + topDown(n-2);
    
    return topDown_memo[n];
}

단순재귀와 비교

public static int naiveRecursion(int n){
    if(n <= 1){
        return n;
    }
    return naiveRecursion(n-1) + naiveRecursion(n-2);
}

22-08-27

---

Reference

• https://hongjw1938.tistory.com/47
• https://novlog.tistory.com/93