동적계획법(Dynamic Programming)이란? 문제편

🔷 동적계획법(Dynamic Programming)이란? 문제편

✅ 정의

동적계획법(Dynamic Programming)은 하나의 문제를 더 작은 하위 문제로 나누고, 그 하위 문제의 결과를 저장해 중복 계산을 피함으로써 전체 문제를 효율적으로 해결하는 알고리즘 설계 기법입니다.

동적계획법은 동일한 계산을 반복하지 않기 위해 계산 결과를 저장하고 재활용합니다. 이 방식은 특히 하위 문제가 반복적으로 등장하는 문제에서 시간 효율성을 극적으로 높입니다.

✅ 등장 배경

프로그래밍에서 많은 문제들은 겉보기에 복잡하지만, 내부적으로는 같은 계산이 반복되는 구조를 가지고 있습니다. 이러한 문제를 단순 재귀(recursion)로 해결할 경우, 같은 하위 문제를 여러 번 다시 계산하는 비효율적인 구조가 생깁니다. 예를 들어, 피보나치 수열을 재귀로 구현한 코드는 다음과 같습니다:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

✅ 재귀의 진짜 문제는 중복 계산입니다

단순 재귀의 가장 큰 문제는 하위 문제를 반복해서 다시 계산한다는 점입니다. 이 중복 계산은 문제의 크기가 커질수록 기하급수적으로 늘어납니다.

🔹 예: fib(5)의 호출 구조

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

• fib(2)는 총 3번 호출되고,
• fib(3)도 중복됩니다.

🔹 호출 횟수 증가 예시

n	호출 횟수 (대략)
10	177회
20	21,891회
30	2,692,537회
40	331,160,281회

이러한 수치는 시간 복잡도가 지수형(O(2ⁿ))에 가까움을 보여줍니다.

🔹 핵심 문제 요약

• 재귀가 느린 이유는 단순히 "재귀라서"가 아니라, 구조적으로 동일한 계산을 반복해서 수행하기 때문입니다.
• 이로 인해 불필요한 연산이 폭증하고, 실행 시간이 입력 크기에 따라 기하급수적으로 증가합니다.

✅ 아이디어

동적계획법은 위 문제를 해결하기 위해 고안된 방법입니다. 그 핵심 아이디어는 중복 계산을 제거하고, 계산한 값을 저장해서 재활용하는 것입니다.

동작 방식:

• 작은 하위 문제로 분해 복잡한 문제를 더 단순한 하위 문제들로 나눕니다.
• 하위 문제의 해를 저장 계산한 결과를 배열, 딕셔너리 등에 저장합니다.
• 저장된 결과 재활용 동일한 계산이 다시 필요할 때는, 저장된 값을 그대로 불러옵니다.
• 전체 문제 해결 이렇게 계산된 부분 해들을 조합해 최종 답을 구합니다.

예를 들어, fib(40)을 동적계획법으로 계산할 경우, 모든 하위 문제는 단 1번씩만 계산됩니다. 결과적으로 시간 복잡도는 O(n) 수준으로 내려갑니다.

✅ 요약 및 마무리

• 단순 재귀는 하위 문제를 반복 계산하여 지수적인 시간 복잡도를 초래합니다.
• 이로 인해 실행 시간이 급격히 증가하며, 큰 입력에 대해 실질적으로 동작할 수 없습니다.
• 동적계획법은 중복 계산을 제거함으로써 이 구조적 문제를 해결합니다.
• 대표적인 적용 사례로는 피보나치 수열, 배낭 문제, 최장 공통 부분 수열(LCS) 등이 있습니다.