야, 솔직히 말할게. 동적계획법(Dynamic Programming, DP)은 처음 들었을 때 이름부터 뭔가 무섭지 않아? 😅
"동적"이라는 단어도 그렇고, "계획법"이라는 단어도 그렇고... 뭔가 엄청 복잡한 수학 이론 같은 느낌.
근데 막상 파고들면 진짜 우아하고 아름다운 아이디어야. 오늘 나랑 같이 이 세계를 완전히 뜯어보자! 💪

이 글을 다 읽고 나면 DP가 왜 수학과 컴퓨터과학에서 그토록 중요한지, 그리고 어떻게 쓰이는지 확실히 알게 될 거야.

동적계획법은 1950년대 미국의 수학자 리처드 벨만(Richard Bellman)이 개발한 최적화 기법이야.
이름이 좀 이상하지? "Dynamic Programming"인데 사실 여기서 "Dynamic"은 우리가 흔히 쓰는 "동적인"의 의미가 아니야.
벨만 본인이 나중에 밝히길, 당시 연구비를 지원하던 국방부가 "수학 연구"라는 단어를 싫어해서 그냥 멋있어 보이는 이름을 골랐다고 해 😂
그러니까 이름에 너무 겁먹지 마!

이게 전부야. 진짜로. 물론 이걸 실제로 구현하는 건 다양한 기술과 통찰이 필요하지만,
핵심 철학은 딱 이 한 줄이야. 중복 계산을 없애서 효율을 극적으로 높이는 것.

이 두 조건이 모두 만족될 때 DP는 마법 같은 효율을 발휘해. 지금부터 구체적인 예시로 살펴보자!

DP를 설명할 때 가장 많이 쓰이는 예시가 바로 피보나치 수열이야.
피보나치 수열은 이렇게 정의돼:

즉, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ... 이렇게 이어지는 수열이야.
이걸 순진하게 재귀로 구현하면 어떻게 될까?

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

코드는 깔끔한데... 문제가 있어. F(5)를 계산하는 과정을 그림으로 보면:

보이지? F(3)이 2번, F(2)가 3번, F(1)이 무려 5번 계산돼!
n이 커질수록 이 중복은 기하급수적으로 늘어나. F(50)을 이렇게 계산하면 수십억 번의 연산이 필요해 😱
시간 복잡도가 O(2ⁿ)이거든. 완전 폭발적으로 늘어나는 거야.

DP의 첫 번째 방법인 메모이제이션(Memoization)을 써보자.
"이미 계산한 값은 저장해두고, 다시 필요하면 꺼내 쓴다"는 아이디어야.

memo = {}

def fib_dp(n):
    if n <= 1:
        return n
    if n in memo:          # 이미 계산했으면 바로 반환!
        return memo[n]
    memo[n] = fib_dp(n-1) + fib_dp(n-2)
    return memo[n]

이제 시간 복잡도가 O(n)으로 줄어들어! 각 값을 딱 한 번씩만 계산하니까.
F(50)도 순식간에 계산돼. 이게 DP의 마법이야 ✨

메모이제이션이 "위에서 아래로(Top-Down)" 방식이라면,
바텀업(Bottom-Up)은 "아래에서 위로" 올라가는 방식이야.
작은 문제부터 차례차례 풀어나가는 거지.

def fib_bottom_up(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]   # 이미 계산된 값 활용!
    return dp[n]

이 방식은 재귀 호출이 없어서 스택 오버플로우 걱정도 없고, 메모리도 더 효율적으로 쓸 수 있어.
심지어 변수 두 개만 써서 O(1) 공간으로도 구현 가능해!

DP의 클래식 중의 클래식! 배낭 문제야. 🎒
이 문제는 수학, 경제학, 컴퓨터과학 전반에서 엄청나게 중요하게 다뤄져.
문제 상황은 이래:

배낭 문제의 DP 점화식은 이래:

이 점화식이 핵심이야. "넣을까 말까"를 선택하는 거야.
이걸 표로 채워나가면 O(n × W)의 시간 복잡도로 최적해를 구할 수 있어!
완전 탐색이라면 2ⁿ가지를 다 봐야 하는데, DP를 쓰면 훨씬 빠르게 해결되지.

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(W + 1):
            # 물건을 안 넣는 경우
            dp[i][w] = dp[i-1][w]
            # 물건을 넣을 수 있고, 넣는 게 더 이득이면
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w], 
                               dp[i-1][w - weights[i-1]] + values[i-1])
    
    return dp[n][W]

LCS(Longest Common Subsequence)는 두 문자열에서 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제야.
이게 왜 중요하냐고? DNA 서열 분석, 파일 비교(diff), 버전 관리 시스템 등에 실제로 쓰여!

이 점화식도 직관적이야:
두 문자가 같으면 이전 결과에 1을 더하고,
다르면 한 쪽을 제외했을 때의 최댓값을 취하는 거야.

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

print(lcs("ABCBDAB", "BDCAB"))  # 출력: 4

시간 복잡도는 O(m × n)이야. 두 문자열 길이의 곱에 비례하는 거지.
완전 탐색으로 하면 지수 시간이 걸리는데, DP 덕분에 다항 시간으로 해결돼! 🎉

DP는 그래프에서 최단 경로를 찾는 데도 핵심적으로 쓰여.
대표적인 알고리즘이 벨만-포드(Bellman-Ford)와 플로이드-워셜(Floyd-Warshall)이야.

모든 쌍의 최단 경로를 한 번에 구하는 알고리즘이야.
핵심 아이디어: "k번 노드를 거쳐서 가면 더 짧아지지 않을까?"

def floyd_warshall(graph, n):
    dist = [[float('inf')] * n for _ in range(n)]
    
    # 초기화
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in graph:
        dist[u][v] = w
    
    # 모든 중간 노드 k를 시도
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

시간 복잡도 O(n³)이지만, 모든 쌍의 최단 경로를 한 번에 구할 수 있어.
이 알고리즘도 DP의 핵심 원리인 "이미 계산한 최적해를 재활용"하는 거야.

이것도 DP의 대표 문제야! 실생활에서도 바로 연결되는 문제거든.
동전의 종류가 주어졌을 때, 특정 금액을 만들기 위한 최소 동전 개수를 구하는 거야.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 0원을 만드는 데 필요한 동전: 0개
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 10, 25], 36))  # 출력: 3

여기서 중요한 점! 탐욕 알고리즘(Greedy)으로는 항상 최적해를 구할 수 없어.
예를 들어 동전이 [1, 3, 4]이고 목표가 6이라면:
탐욕: 4 + 1 + 1 = 3개
DP: 3 + 3 = 2개 ← 더 적어!
이런 경우에 DP가 진가를 발휘하는 거야 💪

LIS(Longest Increasing Subsequence)는 수열에서 순서를 유지하면서 증가하는 가장 긴 부분 수열을 찾는 문제야.
주식 분석, 패턴 인식 등에 활용돼!

def lis(arr):
    n = len(arr)
    dp = [1] * n  # 각 원소 자체만으로 길이 1
    
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:  # 증가하는 경우
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 출력: 4

이 O(n²) 풀이를 이진 탐색을 활용하면 O(n log n)으로 더 빠르게 풀 수도 있어!
DP는 이렇게 다른 알고리즘과 결합해서 더 강력해지기도 해.

DP 문제를 처음 보면 막막하지? 😅 근데 체계적인 접근법이 있어!

기본을 마스터했다면 이제 고급 기법들을 살펴보자! 🔥
이 기법들은 경쟁 프로그래밍이나 고급 알고리즘 수업에서 자주 등장해.

상태를 비트(0과 1)로 표현해서 집합을 효율적으로 다루는 기법이야.
대표적인 문제가 외판원 순회(TSP, Traveling Salesman Problem)야!

# TSP 비트마스크 DP
# dp[visited][현재도시] = 방문한 도시 집합이 visited이고
#                         현재 도시에 있을 때의 최소 비용

def tsp(dist, n):
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 도시 0에서 시작, 도시 0만 방문
    
    for visited in range(1 << n):
        for cur in range(n):
            if dp[visited][cur] == INF:
                continue
            for next_city in range(n):
                if visited & (1 << next_city):  # 이미 방문
                    continue
                next_visited = visited | (1 << next_city)
                dp[next_visited][next_city] = min(
                    dp[next_visited][next_city],
                    dp[visited][cur] + dist[cur][next_city]
                )
    
    # 모든 도시 방문 후 출발지로 복귀
    all_visited = (1 << n) - 1
    return min(dp[all_visited][i] + dist[i][0] for i in range(n))

구간 [i, j]에 대한 최적해를 구하는 DP야.
대표 문제: 행렬 연쇄 곱셈(Matrix Chain Multiplication)

행렬 A₁ × A₂ × A₃ × A₄를 계산할 때 어떤 순서로 곱하느냐에 따라
연산 횟수가 엄청나게 달라져. DP로 최적 순서를 O(n³)에 찾을 수 있어!

DP는 이론에만 머물지 않아. 우리 일상 곳곳에 숨어있어! 👀

두 문자열 사이의 편집 거리(Levenshtein Distance)는 맞춤법 교정, 검색 엔진, 자연어 처리에 핵심적으로 쓰여.
한 문자열을 다른 문자열로 바꾸기 위한 최소 편집 횟수(삽입, 삭제, 교체)를 구하는 거야.

예를 들어 "kitten"과 "sitting"의 편집 거리는 3이야.
이 알고리즘 덕분에 우리가 오타를 쳐도 검색 엔진이 "혹시 이걸 찾으셨나요?"라고 제안해줄 수 있는 거야! 🔍

음성 인식, 자연어 처리에서 쓰이는 DP 기반 알고리즘이야.
은닉 마르코프 모델(HMM)에서 가장 가능성 높은 상태 시퀀스를 찾는 데 사용돼.
스마트폰의 음성 인식, 자동 번역 등에 핵심적으로 활용되는 기술이야!

DP는 단순한 프로그래밍 기법이 아니야. 탄탄한 수학적 기반 위에 서 있어.

강화학습의 핵심이기도 한 벨만 방정식은 DP의 수학적 표현이야:

이 방정식이 바로 현대 AI의 강화학습(Reinforcement Learning)의 근간이야.
알파고(AlphaGo)도 이 원리를 활용했어! 🤖

표를 보면 알 수 있듯이, DP는 지수 시간이나 팩토리얼 시간을 다항 시간 또는 지수 시간의 더 낮은 차수로 줄여줘.
이게 DP가 그토록 강력한 이유야!

DP를 제대로 마스터하고 싶다면 이런 순서로 공부하는 걸 추천해!

참고로, 알고리즘과 수학 실력을 키우고 싶다면 재능넷(jaenung.net)에서 알고리즘 튜터링 재능을 찾아볼 수도 있어!
다양한 전문가들이 DP를 포함한 알고리즘을 1:1로 가르쳐주는 서비스를 제공하고 있거든. 혼자 공부하다 막히면 전문가의 도움을 받는 것도 좋은 방법이야 😊

마지막으로 완전한 DP 문제 하나를 처음부터 끝까지 풀어보자!

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# 테스트
for i in range(1, 8):
    print(f"계단 {i}개: {climb_stairs(i)}가지")
# 출력:
# 계단 1개: 1가지
# 계단 2개: 2가지
# 계단 3개: 3가지
# 계단 4개: 5가지
# 계단 5개: 8가지
# 계단 6개: 13가지
# 계단 7개: 21가지

눈치챘어? 결과가 피보나치 수열이야! 🤩
이렇게 DP 문제들은 서로 연결되어 있고, 같은 패턴이 다양한 형태로 나타나.
이 패턴을 인식하는 능력이 바로 DP 마스터의 핵심이야!

그리고 재능넷에서 수학이나 알고리즘 관련 재능을 공유하거나 배울 수 있다는 것도 기억해줘.
DP 같은 어려운 개념도 좋은 선생님과 함께라면 훨씬 빠르게 이해할 수 있거든! 🎯

자, 이제 동적계획법의 세계를 꽤 깊이 탐험했어! 🎉
처음엔 이름부터 무서웠던 DP가 이제 좀 친근하게 느껴지지 않아?

DP의 핵심을 다시 한번 정리하면:

DP는 단순한 알고리즘 기법을 넘어서 문제를 바라보는 사고방식이야.
"이 문제를 어떻게 쪼갤 수 있을까?", "어떤 정보를 저장해두면 나중에 쓸 수 있을까?"
이런 질문을 습관적으로 던지다 보면 어느새 DP 마스터가 되어 있을 거야! 💪

수학과 알고리즘의 세계는 깊고 넓어. 오늘 배운 DP는 그 세계의 아주 중요한 문 하나를 연 거야.
계속 탐험하고, 계속 질문하고, 계속 성장해! 🚀