[알고리즘] 6. 동적계획법

1. 동적계획법 Dynamic Programming

하나도 다이나믹하지 않다. 그냥 멋있어 보인다고 붙인 이름이다.
1. 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 하는 것을 반복
2. 분할정복과 비슷한 느낌

DP 구현

1. Top-down : 재귀, 메모이제이션 Memoization
2. Bottom-up : 반복, 타뷸레이션 Tabulation
   → 둘 다 DP 테이블에 답을 저장을 하고 재사용한다.

2. Memoization : 한 번 구한 답은 저장 (캐싱)

1. 부분 문제들의 답을 한 번 구했으면 또 구하지 않도록 (중복연산 방지) cache에 저장해두고 다음부턴 갖다 쓴다.
2. 필요한 부분 문제들만 구한다. Lazy-Evaluation
3. Top-down 방식에서 사용

3. Tabulation : 미리 다 구해두자

1. 부분 문제들의 답을 미리 다 구해두면 편하다!
2. 테이블을 채워나간다는 의미
3. 필요 없는 부분 문제들까지 전부 구한다. Eager-Evaluation
4. Bottom-up 방식에서 사용

피보나치 수열 Fibonacci

f(0) = 0
f(1) = 1
f(i + 2) = f(i + 1) + f(i)

※ 메모이제이션 적용 X

N = int(input())

def fibonacci(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    else:
        return fibonacci(num - 1) + fibonacci(num - 2)
    
print(fibonacci(N))

※ 메모이제이션 적용 O : 재귀

N = int(input())

cache = [-1] * 91
cache[0] = 0
cache[1] = 1

def fibonacci(num):
    if cache[num] == -1:
        cache[num] = fibonacci(num - 1) + fibonacci(num - 2)
    return cache[num]

print(fibonacci(N))

• 작은 문제의 순서는 중요하지 않다.
• 제일 처음 풀어야 하는 문제를 고민이 덜하다.
• 필요한 정의만 고민하면 된다.

※ Tabulation 적용 O : 반복문

N = int(input())

cache = [-1] * 91
cache[0] = 0
cache[1] = 1

for i in range(2, N + 1):
	cache[num] = cache(num - 1) + cache(num - 2)

print(cache(N))

• 작은 문제 답을 구할 때 순서가 중요, 연계가 필요
• 제일 처음 풀어야 하는 문제를 고민해야한다.

이항계수 nCr

1. bino(n, 0) = 1
2. bino(n, n) = 1
3. bino(n, r) = bino(n - 1, r - 1) + bino(n - 1, r) : 점화식, 삼각수(파스칼의 삼각형)과 연관있다.
   
   
   
   ※ 출처: https://blog.naver.com/lty2242/221091097459

※ 메모이제이션 적용 X

import sys

sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())

def bino(n, k):
    if k == 0 or k == n:
        return 1
    return bino(n - 1, k - 1) + bino(n - 1, k)

print(bino(N, K))

※ 메모이제이션 적용 O : 재귀

import sys

sys.setrecursionlimit(10 ** 7)

cache = [[0] * 1001 for _ in range(1001)]
N, K = map(int, input().split())

def bino(n, k):
    if cache[n][k]:
        return cache[n][k]
    if k == 0 or k == n:
        cache[n][k] = 1
    else:
        cache[n][k] = bino(n - 1, k - 1) + bino(n - 1, k)

    return cache[n][k]

print(bino(N, K))

※ Tabulation 적용 O : 반복문

cache = [[0] * 1001 for _ in range(1001)]
N, K = map(int, input().split())

for i in range(1001):
    cache[i][0] = cache[i][i] = 1
    for j in range(1, i):
        cache[i][j] = cache[i - 1][j - 1] + cache[i - 1][j]

print(cache[N][K])

DP 구현 2가지 정리

1. Top-down : 재귀, 메모이제이션 Memoization
   → 직관적이라 코드 가독성이 좋다.
   → 재귀함수 호출을 많이 해서 느릴 수 있다.
2. Bottom-up : 반복, 타뷸레이션 Tabulation
   → 시간과 메모리를 좀 더 아낄 수도 있다.
   → DP테이블 채워 나가는 순서를 알아야 한다.

정리

1. 동적계획법은 문제를 쪼개서 작은 문제부터 구해가며 원래 문제의 답을 구하는 방식
2. 메모이제이션
3. 점화식 찾고 테이블만 잘 정의하면 풀리는 문제들이 많다.