[알고리즘 코어 파헤치기] 다이나믹 프로그래밍(DP) 완벽 해부 - 과거의 기억으로 미래를 계산하다

학습 철학 회고
다이나믹 프로그래밍(DP)은 번뜩이는 천재성을 요구하는 퍼즐이 아닙니다. 복잡하고 거대한 문제를 '완벽하게 똑같은 구조를 가진 아주 작은 문제'로 쪼개고, 그 작은 문제들의 정답을 메모장에 적어두었다가 재활용하는 철저한 메모의 기술입니다.

📌 개념 요약: DP는 무엇인가?

수학의 점화식을 코드로 옮겨 놓은 것입니다. 피보나치 수열처럼 똑같은 연산이 미친 듯이 반복될 때, 한 번 계산한 결과는 배열(dp 테이블)에 저장(Memoization)해 두고, 나중에 똑같은 질문이 들어오면 계산 없이 배열에서 바로 꺼내 쓰는 최적화 기법입니다.

• 최적 부분 구조 (Optimal Substructure): 큰 문제의 최적 해답이 작은 문제들의 최적 해답으로 구성될 때 성립합니다.
• 중복되는 부분 문제 (Overlapping Subproblems): 동일한 작은 문제들이 반복해서 나타나야 메모장의 효율이 극대화됩니다.

💡 동작 원리: 상태 전이 방정식 (점화식) 설계

DP 문제를 푸는 설계 주도형 사고(SOP)의 핵심은 dp[i]가 무엇을 의미하는지 한국어로 정확히 정의하는 것입니다.
"계단을 오를 때 연속 3번 밟지 않는 최대 점수", "1을 만들기 위한 최소 연산 횟수" 등 정의가 명확해야, dp[i]를 구하기 위해 과거의 값(dp[i-1], dp[i-2])을 어떻게 조합할지 점화식이 보입니다.

💻 추상화된 템플릿 코드

DP는 문제마다 점화식이 모두 다르기 때문에 고정된 코드는 없지만, 가장 빈번하게 사용되는 바텀업(Bottom-Up) 방식의 뼈대 설계는 정형화할 수 있습니다.

def dp_bottom_up_template(N, data):
    """
    :param N: 구하고자 하는 목표 인덱스
    :param data: 각 단계에서 주어지는 비용이나 점수 리스트
    """
    # 1. [방어적 프로그래밍] N이 작을 때의 IndexError를 방지하기 위해 넉넉한 크기 할당
    MAX_SIZE = 100001 # 문제 조건의 N_MAX + 1
    dp = [0] * MAX_SIZE
    
    # 2. 초기값 (Base Case) 세팅
    dp[1] = data[1]
    dp[2] = data[1] + data[2] # 예: 첫 칸과 두 번째 칸은 무조건 더하는 게 이득일 경우
    
    # 3. 바텀업 점화식 전개 (루프 설계)
    for i in range(3, N + 1):
        # [핵심 로직] 과거의 최적해를 조합하여 현재의 최적해를 도출
        # 예시: i-2에서 두 칸 점프해서 오거나, i-3에서 두 칸 점프 후 한 칸 걸어오는 경우 중 최댓값
        dp[i] = max(dp[i-2] + data[i], dp[i-3] + data[i-1] + data[i])
        
    # 4. 최종 목표값 반환
    return dp[N]

🚨 설계 및 회고

• 방어적 프로그래밍 (배열 크기 통제): dp = [0] * (N + 1)로 선언한 상태에서 N=1이 주어지면 dp[2]에 접근하다가 즉시 IndexError가 터집니다. 메모리를 약간 더 쓰더라도 문제의 최대 조건만큼 배열을 넉넉히 초기화해 두면 런타임 에러의 80%를 막을 수 있습니다.
• 출력의 위치 통제: DP 연산 과정인 for 문 안에 print(dp[N])이 들어가 있지 않은지 주의해야 합니다. 생명주기와 스코프를 통제하여, 모든 계산이 끝난 뒤 깔끔하게 한 번만 반환하도록 설계해야 합니다.