다이나믹 프로그래밍(Dynamic Programming, DP)은 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 기법입니다. 이 때, 작은 부분 문제의 해결 결과를 저장하고 활용하여 중복 계산을 피하며 문제를 효율적으로 해결합니다. DP는 최적 부분 구조와 중복 부분 문제의 성질을 가지는 문제에서 효과적으로 사용됩니다.

DP의 주요 특징:

1. 작은 부분 문제: 큰 문제를 작은 부분 문제로 나누어 해결합니다.
2. 중복 부분 문제: 같은 부분 문제가 여러 번 반복되는 경우, 그 결과를 저장하여 중복 계산을 피합니다.
3. 메모이제이션(Memoization): 부분 문제의 해결 결과를 저장하고 필요할 때마다 빠르게 가져와 사용합니다.
4. 상향식(Bottom-up) 또는 하향식(Top-down): DP는 상향식 접근과 하향식 접근 중 하나를 선택하여 문제를 해결합니다.

DP의 활용 예시:

• 피보나치 수열 계산: 피보나치 수열을 계산할 때, 작은 수열의 값들을 저장하고 활용하여 빠르게 계산할 수 있습니다.
• 배낭 문제: 다양한 물건들의 가치와 무게가 주어졌을 때, 배낭에 담을 수 있는 최대 가치를 계산할 때 DP를 사용할 수 있습니다.
• 최단 경로 문제: 그래프에서 두 정점 사이의 최단 경로를 계산할 때 DP를 사용할 수 있습니다.

파이썬 코드를 통해 DP를 예시로 살펴보겠습니다. 다음은 피보나치 수열을 메모이제이션을 활용하여 계산하는 DP 코드입니다.

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n

    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

n = 10
result = fibonacci(n)
print(f"{n}번째 피보나치 수:", result)

이 코드는 메모이제이션을 활용하여 피보나치 수열을 계산하는 예시입니다. 작은 부분 문제의 해결 결과를 저장하고 필요할 때마다 사용하여 중복 계산을 피합니다.