[알고리즘 종류] 동적 계획법(Dynamic Programming)

- 동적 계획법

• 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것
• 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있음. ( Memoization: 메모이제이션 )
• 완전 검색을 좀 더 효율적으로 하는 방법
• 분할 정복은 하향식인 반면 동적 계획법은 상향식으로 접근해야 함

🔍 동적 계획법 적용 문제 조건

1. 중복 부분문제 구조

: 동적 계획법은 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해(Optimal Solution)를 이용하여 순환적으로 큰 문제 해결

2. 최적 부분문제 구조

: 주어진 문제가 최적화의 원칙(Principle of Optimality)을 만족해야만 동적 계획법을 효율적으로 적용 가능

 

💡 최적화의 원칙
 - 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 함

 

📄 활용 예제

- 피보나치수열

 

# dp 이용
def fibo_memo(n):
    f = [0, 1]

    for i in range(2, n+1):
        f.append(f[i-1] + f[i-2])

    return f[n]

print(fibo_memo(50))

# 분할 정복 이용 (n이 50만 되도 컴터 터짐..!)
def fibo(n):
    if n < 2:
        return n
    return fibo(n-1) + fibo(n-2)

print(fibo(7))