2026-05-27 TIL (65일차)

알고리즘: 다이나믹 프로그래밍 (Dynamic Programming)

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

다이나믹 프로그래밍(동적 계획법)은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법입니다. 가장 큰 특징은 “이미 계산된 결과는 별도의 메모리 영역에 저장(Caching/Memoization)하여, 다시 계산하지 않도록 만드는 것”입니다. 이를 통해 완전 탐색으로 풀면 기하급수적인 시간이 걸리는 문제도 획기적으로 시간 복잡도를 줄일 수 있습니다.

참고: 알고리즘에서의 ‘다이나믹(Dynamic)’은 프로그램 실행 도중 메모리를 할당하는 ‘동적 할당(Dynamic Allocation)’과는 다르게, 별다른 의미 없이 쓰인 용어입니다.

---

2. 다이나믹 프로그래밍의 사용 조건

DP를 적용하려면 다음 두 가지 조건을 만족해야 합니다.

1. 최적 부분 구조 (Optimal Substructure)
   • 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 구조입니다.
2. 중복되는 부분 문제 (Overlapping Subproblem)
   • 동일한 작은 문제가 반복적으로 호출되어, 똑같은 계산을 여러 번 해야 하는 구조입니다. (예: 피보나치 수열)

---

3. DP의 2가지 구현 방식

① 탑다운 (Top-Down) / 하향식

• 특징: 큰 문제를 해결하기 위해 작은 문제를 재귀적(Recursion)으로 호출하는 방식입니다.
• 메모이제이션(Memoization): 한 번 계산된 결과를 배열이나 리스트에 기록해 두는 기법입니다. (캐싱이라고도 함)
• 재귀 함수가 너무 깊어지면 스택 오버플로우가 발생할 수 있습니다.

② 보텀업 (Bottom-Up) / 상향식

• 특징: 가장 작은 문제부터 차례대로 정답을 구해 나가면서, 반복문(Loop)을 이용해 큰 문제를 해결하는 방식입니다.
• DP 테이블: 보텀업 방식에서 계산된 결과를 저장하기 위해 사용하는 리스트/배열을 ‘DP 테이블’이라고 부릅니다.

---

4. 다이나믹 프로그래밍 vs 분할 정복 (Divide & Conquer)

• 공통점: 둘 다 큰 문제를 작은 문제로 나누는 ‘최적 부분 구조’를 가집니다.
• 차이점: 부분 문제의 중복 여부입니다.
  • 다이나믹 프로그래밍: 부분 문제가 서로 중복되어 재사용됩니다. (메모이제이션 필수)
  • 분할 정복(예: 퀵 정렬): 한 번 분할된(피벗이 자리 잡은) 문제는 다시 호출되거나 중복되지 않습니다.

---

5. 대표적인 DP 문제 및 점화식

강의에서 다룬 5가지 핵심 DP 문제와 점화식 도출 과정입니다.

1. 개미 전사

• 문제: 인접하지 않게 식량 창고를 털어서 가장 많은 식량을 얻는 문제.
• 점화식: a[i] = max(a[i-1], a[i-2] + k[i]) (이전 창고를 턴 경우 vs 두 칸 앞 창고를 털고 현재 창고를 턴 경우)

2. 1로 만들기

• 문제: x에 대해 4가지 연산(-1, /2, /3, /5)을 적절히 사용하여 1을 만드는 최소 횟수. (그리디로 풀 수 없음)
• 점화식: a[i] = min(a[i-1], a[i/2], a[i/3], a[i/5]) + 1

3. 효율적인 화폐 구성

• 문제: N가지 화폐를 이용해 합이 M원이 되도록 하는 최소 화폐 개수.
• 점화식: 각 화폐 단위 k를 확인하며, a[i] = min(a[i], a[i-k] + 1) (단, a[i-k]를 만드는 방법이 존재할 때)

4. 금광

• 문제: n x m 크기의 금광에서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 방향으로만 이동하며 얻을 수 있는 금의 최댓값.
• 점화식: dp[i][j] = array[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1]) (배열 범위를 벗어나는지 체크 필수)

5. 병사 배치하기 (가장 긴 증가하는 부분 수열 - LIS 응용)

• 문제: 전투력이 높은 병사가 앞쪽에 오도록 내림차순 배치하되, 열외시키는 병사의 수를 최소화하는 문제.
• 해결법: 원본 배열을 뒤집은 뒤, 전형적인 LIS (Longest Increasing Subsequence) 알고리즘을 수행하여 전체 길이에서 LIS 길이를 뺍니다.
• LIS 점화식: 모든 0 <= j < i 에 대하여 D[i] = max(D[i], D[j] + 1) (단, array[j] < array[i] 일 때)

---

팀 프로젝트 마무리

느낀 점

마지막에 팀 프로젝트를 깔끔하게 마쳐서 좋았지만, 다른 팀원의 발표와 결과물을 보고 UI나 유저 친화적으로 고려하고 만든 부분도 많아서 배울 점이 되게 많았다고 느꼈습니다. 아직 부족한 점이 많다고 느껴서 더욱 노력해야겠다고 생각했습니다.