DP 알고리즘 정리

DP란 무엇일까?

Dynamic Programming, 동적 계획법 하나의 문제는 단 한 번만 풀도록 하는 알고리즘

피보나치 수열의 예시

특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞의 숫자의 합을 구해야 함

D[i] = D[i-1] + D[i-2]

• 색칠된 부분은 동일한 문제를 다시 계산해야 하는 문제 발생 ➡️ DP로 풀이해야 함

DP는 언제 사용할 수 있을까?

다음의 가정 하에 DP를 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

➡️ 크고 어려운 문제가 있으면 잘게 나누어 해결한 뒤에 전체의 답을 구한다.

Memoization

계산한 결과는 배열에 저장하여, 동일한 계산이 필요할 경우 저장된 값을 반환하기만 한다

def DF(x):
    if x == 1: return 1
    if x == 2: return 1
    return DF(x-1)+DF(x-2);

DF(5) # 5
DF(50) # 총 연산 횟수 2**50 -> 계산하는 시간이 오래 걸림

# 메모이제이션을 활요한다면?
# 연산 횟수는 O(n)번 -> 일직선으로 타고 내려가면 되기 때문!

memo = [0]*100

def DF(x):
    if x == 1: return 1
    if x == 2: return 1
    if memo[x] != 0: return memo[x]
    memo[x] = DF(x-1) + DF(x-2)
    return memo[x]

Without Memoization (O(2**n))

With Memoization (O(n))

 

참고 🔗 https://www.youtube.com/watch?v=FmXZG7D8nS4