Dynamic_programming

Table of contents

동적 계획법 (Dynamic Programming)

정의

  • 복잡한 문제를 여러 개의 간단한 하위 문제로 나누어 풀고, 그것을 결합하여 최종적인 문제를 해결하는 것

특징

  • 각 하위 문제들의 답을 저장해놓고 같은 하위 문제가 나타난다면 미리 구한 답을 이용하면 됨
  • 중복되는 부분 문제(overlapping subproblem)
    • 중복되는 부분 문제가 반복적으로 등장한다.
  • 최적 부분 구조(optimal substructure)
    • 부분 문제의 최적의 답을 이용하여 전체 문제에 대한 최적의 답을 표현할 수 있다.

원리

  • Top-down 방식
    • 메모를 한다는 뜻의 메모이제이션(memoization)은 각 단계마다 부분 문제의 해답을 찾으면 배열 구조의 캐시에 저장한다. 캐시에 값이 저장되어 있는지 여부를 확인하여 저장되어 있다면 저장된 값을 반환한다.
      1. 큰 문제를 작은 문제(하위 문제)로 나눈다.
      2. 작은 문제(하위 문제)를 푼다.
      3. 작은 문제(하위 문제)의 답을 결합해 최종 문제를 해결한다.
  • Bottom-up 방식
    • 테이블에 정리한다는 의미의 타뷸레이션(tabulation)은 모든 부분 문제에 대한 해답을 표에 저장한 후 재사용하는 방식이다. 반복문을 통해 부분 문제에 대한 해답을 저장해나가는 방식이다.
      1. 작은 문제들부터 푼다.
      2. 작은 문제들의 답을 이용해 큰 문제를 푼다.
      3. 이를 반복해 최종 문제를 푼다.

장점

  • Top-down 방식
    • 연산 수가 줄어들어 기존의 방식보다는 효율적
  • Bottom-up 방식
    • 재귀 함수 호출로 인한 overhead가 없음
    • 연산 수가 줄어들어 효율적

단점

  • Top-down 방식
    • 메모이제이션의 장점을 제대로 활용할 수 없음
    • 재귀적인 함수 호출로 인한 Overhead가 여전히 존재하므로 비효율적

피보나치 수열 (Fibonacci)

정의

image

  • 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열
  • F(n) = F(n-1) + F(n-2)

원리

  • Top-down 방식
    1. 큰 문제를 작은 문제(하위 문제)로 나눈다.
      • F(n-1)과 F(n-2)로 문제를 나눈다.
    2. 작은 문제(하위 문제)를 푼다.
      • F(n-1)과 F(n-2)를 구한다. 이 때 이미 구한 값이라면 저장한 값을 이용하고, 구해놓지 않은 값이라면 이를 메모이제이션 배열에 저장해 놓는다.
    3. 작은 문제(하위 문제)의 답을 결합해 최종 문제를 해결한다.
      • F(n-1)과 F(n-2)값을 더해 F(n)을 구한다.
  • Bottom-up 방식
    1. 작은 문제들부터 푼다.
      • F(i-1) , F(i-2) 값을 나타낼 M[i-1] , M[i-2]를 구한다.
    2. 작은 문제들의 답을 이용해 큰 문제를 푼다.
      • M[i-1] + M[i-2] 를 이용해 M[i]를 구한다.
    3. 이를 반복해 최종 문제를 푼다.
      • 이를 반복해 M[n]을 구한다.

코드

  • Top-down 방식 ```python

    memoization (하향식)

dp = [0]*100 # 소문제 결과를 저장할 리스트 dp[0] = 1 dp[1] = 1

def fib(n):

# 만약 계산한 적이 없다면 재귀로 계산 
if dp[n] == 0:
    dp[n] = fib(n-1) + fib(n-2)

# 있다면 그대로 반환 
return dp[n]

fib(10)

- Bottom-up 방식
```python
# 타뷸레이션 (상향식)

def fib(n):

    dp = [0]*(n+1)
    dp[0] = 1
    dp[1] = 1
    
    # 작은 값(소문제)부터 직접 계산하며 진행 
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

fib(10)

최장 공통 부분 수열(LCS)

정의

  • 두 문자열을 비교할 때 공통적으로 나타나는 부분 순서들 중 가장 긴 것

특징

  • 연속적이지 않아도 되는 부분 문자열이다.
  • 최적화를 해야 하는 문제이기 때문에 동적계획법(DP)를 사용하여야 가장 효율적으로 구할 수 있다.

원리

image image

  • if (i == 0 or j == 0) 이라면 겹치는 문자가 존재하지 않기 때문에 0
  • i, j > 0이고, x(i) = y(i)라면 하나의 문자가 겹치는 것이기 때문에 c[i][j]는 c[i - 1][j - 1]에서 +1
  • 비교문자가 다를 경우 c[i-1][j], c[i][j-1]중에 더 큰 값을 c[i][j]에 넣는다.

  • 위 표에서 LCS의 길이는 가장 오른쪽에 가장 아래에 있는 c[3][4] = 2인 부분이다.

  • LCS가 무엇인지를 찾고 싶을 때는 역추적(backtrack)을 이용하면 된다.
    • X의 문자와 Y의 문자가 같다면 c[i][j] = c[i - 1][j - 1] + 1이므로 1이 증가하는 부분의 문자를 연결해 문자열을 만들면 LCS가 된다.

시간복잡도

  • O(mn)