[AlgorithmTheory] 다이나믹 프로그래밍 개념

코딩 테스트를 준비하며 가장 거대한 벽으로 느껴지는 알고리즘, 바로 다이나믹 프로그래밍(Dynamic Programming)입니다. 수많은 개발자 지망생들이 여기서 좌절을 겪곤 합니다.

이번 포스트에서는 교과서적인 개념 정리를 넘어, 실전 코딩 테스트에서 DP를 어떻게 대하고 공부해야 하는지 저만의 언어로 자세히 풀어보고자 합니다.

1. 다이나믹 프로그래밍이란?(개념)

다이나믹 프로그래밍은 이름처럼 거창한 알고리즘이 아닙니다. 핵심은 단 하나 “기억하며 풀기(Memoization)”입니다. 큰 문제를 작은 부분 문제로 나누어 해결하되, 한 번 계산한 결과를 배열이나 메모리에 저장해 두고 다시 계산하지 않는 기법을 말합니다.

아무 때나 이 기법을 쓸 수 있는 것은 아니며, 반드시 다음 두 가지 조건을 만족해야 합니다.

1. 부분 문제 중복(Overlapping Subproblems):

   동일한 작은 문제들이 반복해서 나타나야 합니다. (예 피보나치 수열에서 $f(3)$이 여러번 호출되는 현상 )

2. 최적 부분 구조(Optimal Substructure):

   부분 무제의 최적 결과값을 이용해 전체 문제의 최적 결과를 낼 수 있어야 합니다. (예: 서울에서 부산을 갈 때, 대전을 거쳐 가는 것이 최단 경로라면, 서울-대전 구간도 최단 경로여야함)

참고로 DP를 구현하는 방식으로는 재귀 함수를 이용하는 탑다운(Top-Down)과 반복문을 이용하는 바텀업(Bottom-Up)이 있습니다. 실전 코딩 테스트에서는 파이썬의 재귀 깊이 제한과 메모리 이슈를 피하기 위해 가급적 바텀업 방식(반복문 + 1차원/2차원 배열)으로 접근하는 것을 강력히 권장합니다.

2. 다이나믹 프로그래밍 공부 방법

DP는 단순히 문제를 많이 푼다고 실력이 늘지 않습니다. 새로운 문제를 볼 때마다 “이걸 어떻게 유추하지?”라며 백지상태가 되기 때문입니다. 제가 추천하는 DP 공부 방법은 다음과 같습니다.

• 디자인 패턴(문법) 암기하듯 접근하기:

  DP문제는 5~6개의 거대한 뼈대(패턴) 위에서 스토리만 바뀌어 출제됩니다. 영문법을 외우듯 핵심 기출문제의 점화식과 배열 상태 정의를 내 머릿속 “도구함”에 각인시켜야 합니다.

• 상태 정의(State Definition) 훈련:

  코드를 짜기 전에 dp[i] 또는 dp[i][j]가 정확히 무엇을 의미하는지 한글로 명확히 적어보는 습관을 들여야 합니다. (예: dp[i][j] = i번째 물건까지 확인했을 때, j의 문제로 얻을 수 있는 최대 가치)

• 초기화의 중요성 파악:

  최솟값을 구할 때는 불가능한 값을 $\infty$ (무한대)로, 경의 수를 구할 때는 dp[0] = 1로 설정하는 등, 0번째 인덱스의 초기값 설정이 점화식만큼 중요합니다.

• 나선형 반복 복습:

  이게 가장 중요한데, 풀었던 문제를 단순히 풀었다고 해서 끝나는 것이 아니라 3일, 1주일, 한 달 뒤에 다시 풀어보며 코드가 손끝에서 자연스럽게 나올 때까지 반복 숙달해야 합니다.

3. 다이나믹 프로그래밍 문제의 유형

세상에 수백 개의 DP 문제가 있는 것 같지만, 실전 코딩 테스트에 등장하는 핵심 유형은 크게 5가지로 압축 됩니다.

1. 0/1 배낭 문제(0/1 Knapsack):

   물건을 쪼갤 수 없고 딱 1번만 담을 수 있는 유형으로 “선택한다 / 안 한다”의 이지선다로 나뉘며 2차원 배열이나 뒤에서부터 탐색하는 1차원 배열을 사용합니다.
   배낭채우기2 문제풀이 Link

2. 무한 배낭 문제(Unbounded Knapsack):

   동전 교환 문제처럼 같은 아이템을 무제한으로 쓸 수 있는 유형으로 정방향 1차원 배열 탐색을 사용합니다. 배낭채우기1 문제풀이 Link

3. 최장 증가 부분 수열(LIS, Longest Increasing Subsequence):

   주어진 수열에서 오름차순으로 가장 길게 이어지는 부분 수열 패턴을 찾는 문제입니다.

4. 최장 공통 부분 수열(LCS Longest Common Subsequence):

   두 문자열의 유사도를 검사할 때 쓰이는 패턴으로, 2차원 그리드를 그려서 해결합니다.

5. 구간 / 트리DP:

   특정 구간의 최적해를 구하거나, 트리의 부모-자식 노드 간의 상태 전이를 다루는 심화 유형입니다.

4. 코딩 테스트 시 DP를 사용해야 할 때 (접근 시그널)

실전에서 문제를 마주했을 때, 다음의 시그널들이 보인다면 주저 없이 DP 배열을 그려야 합니다.

• 키워드:

  문제에서 “~의 최댓값/최솟값을 구하시오”, “~하는 경우의 수를 구하시오”라고 묻는 다면 십중팔구 DP 아니면 그리디(Greedy)입니다. 반례가 쉽게 떠오른다면 무조건 DP입니다.

• 시간 복잡도 제한:

  DFS/BFS나 완전 탐색을 돌렸을 때 경우의 수가 $O(2^N)$이나 $O(N!)$로 굉장히 많아 시간초과가 날 것 같은데 N의 범위가 100~10,000 정도로 주어졌다면 100% DP를 통해 $O(N^2)$ 이하로 줄이라는 출제자의 의도입니다.

• 결정의 누적:

  현재의 결정을 내리기 위해, 과거에 내가 어떤 값들을 만들어 왔는지(과거의 상태들)를 참조해야만 풀리는 문제일 때 DP를 떠올려야 합니다.

마치며

DP는 천재들의 IQ 테스트가 아닙니다. 선배 개발자들이 만들어둔 훌륭한 ‘설계 패턴’을 얼마나 잘 숙지하고 응용하는지를 묻는 시험에 가깝습니다. 처음엔 도저히 점화식이 유추되지 않아 해설을 보고 좌절할 수도 있습니다. 하지만 그것은 내 논리력이 부족해서가 아니라 단지 ‘새로운 패턴’을 아직 배우지 못했을 뿐입니다.

자신만의 핵심 문제 리스트를 만들어 꾸준히 복습한다면, 어느 순간 어떤 낯선 문제 앞에서도 출제자의 기만을 꿰뚫어 보는 통찰력이 생길 것입니다.