왜 두 기법을 묶어서 다루는가

15편의 분할정복은 부분 문제들이 서로 독립적이라고 가정했다. 그런데 현실의 많은 최적화 문제에서는 부분 문제들이 서로 겹친다. 예를 들어 “물건 몇 개를 배낭에 담아 가치를 최대화하라”는 문제를 재귀로 풀면, “남은 용량 5로 물건 2개 중 고르기”라는 부분 문제가 여러 경로에서 반복해서 등장한다. 이렇게 겹치는 부분 문제를 매번 다시 계산하지 않고 한 번 계산한 결과를 저장해 재사용하는 기법이 동적계획법(Dynamic Programming, DP)이다. 한편 탐욕 알고리즘(greedy algorithm)은 매 단계에서 “지금 당장 가장 좋아 보이는 선택”만 하고 다시 돌아보지 않는 방식인데, 어떤 문제에서는 이 단순한 전략이 최적해를 보장하지만 어떤 문제에서는 보장하지 않는다. 두 기법을 나란히 다루는 이유는, 같은 유형의 최적화 문제를 두고 “이 문제는 DP로 풀어야 하는가, 탐욕으로 충분한가”를 구분하는 것이 독학사 4단계에서 가장 자주 나오는 판별 유형이기 때문이다.

쉽게 말하면: 동적계획법은 “한 번 푼 부분 문제의 답을 기록해 두고 재사용”하는 전략이고, 탐욕은 “매 순간 당장 최선인 것만 고르고 절대 후회하지 않는” 전략이다.

동적계획법이 필요한 조건 두 가지

동적계획법을 적용할 수 있으려면 문제가 다음 두 성질을 모두 가져야 한다.

• 최적 부분 구조(optimal substructure): 원래 문제의 최적해가 부분 문제들의 최적해로부터 만들어질 수 있다는 성질. 예를 들어 “1부터 n까지 최단경로”의 최적해는 그 경로 위 임의의 두 지점 사이 구간도 반드시 최단경로여야 한다(13편의 최단경로 알고리즘들이 동적계획적 성격을 갖는 이유이기도 하다).
• 중복 부분 문제(overlapping subproblems): 재귀로 문제를 풀 때 같은 크기·같은 조건의 부분 문제가 여러 번 반복해서 나타난다는 성질. 이 성질이 없다면(부분 문제가 모두 서로 다르다면) 저장해 재사용할 것이 없으므로 굳이 동적계획법을 쓸 이유가 없다(15편의 분할정복이 이런 경우다).

자주 틀리는 점: “최적 부분 구조만 있으면 동적계획법을 써야 한다”고 오해하기 쉽다. 최적 부분 구조는 분할정복도 가지고 있는 성질이다. 동적계획법이 특별히 유리해지는 것은 여기에 중복 부분 문제까지 더해질 때다. 부분 문제가 겹치지 않는다면 그냥 분할정복으로 충분하다.

동적계획법 예제 — 동전 교환 문제

동전 교환 문제(coin change problem)는 “주어진 동전 종류로 특정 금액을 만들 때, 필요한 동전 개수를 최소화하라”는 문제다. 동전 종류가 1원, 3원, 4원이고 목표 금액이 6원일 때를 계산한다.

금액 $i$를 만드는 데 필요한 최소 동전 개수를 $dp[i]$라 하면, 점화식은 다음과 같다.

• $c$: 사용 가능한 동전 하나(1원, 3원, 4원 중 하나).
• $dp[i-c]$: 지금 동전 $c$ 하나를 쓰고 남은 금액 $i-c$를 만드는 데 필요한 최소 동전 개수(이미 계산해 둔 부분 문제의 답).
• $+1$: 방금 사용한 동전 $c$ 한 개를 더하는 것.
• $\min$: 세 가지 동전 선택지 중 전체 동전 개수가 가장 적은 경우를 고른다.

이 점화식 자체가 “중복 부분 문제”의 증거다. $dp[6]$을 구하려면 $dp[5]$, $dp[3]$, $dp[2]$가 필요한데, 이 값들은 다시 $dp[4]$, $dp[3]$, $dp[2]$, $dp[1]$처럼 더 작은 부분 문제를 공유하며 반복해서 참조된다.

DP 테이블 채우기

$dp[0]=0$(아무 동전도 안 써서 0원을 만드는 방법)에서 시작해 $dp[6]$까지 하나씩 채운다.

결과: $dp[6]=2$, 3원짜리 동전 두 개(3+3)로 6원을 만드는 것이 최소 동전 개수다.

같은 문제를 탐욕으로 풀면 — 실패 사례

같은 문제를 “매번 남은 금액을 넘지 않는 가장 큰 동전을 고른다”는 탐욕 전략으로 풀어 본다.

탐욕 전략은 4 + 1 + 1 = 3개의 동전을 쓴다. 그런데 DP로 구한 최적해는 3 + 3 = 2개다. 같은 문제, 같은 목표 금액인데도 탐욕은 최적해보다 동전 하나를 더 쓰는 답을 내놓았다.

결과 해석: 이 예제는 “탐욕 알고리즘이 항상 최적해를 보장하지는 않는다”는 사실을 숫자로 직접 확인시켜 주는 대표적인 반례다. 동전 종류가 1원, 5원, 10원, 50원, 100원처럼 서로 배수 관계가 잘 맞는 화폐 체계에서는 우연히 탐욕이 최적해를 내놓는 경우가 많지만(그래서 실생활에서 거스름돈을 셀 때 무의식적으로 탐욕을 써도 문제가 없다), 동전 종류가 1, 3, 4처럼 임의로 주어지면 탐욕이 실패할 수 있다.

탐욕이 성공하는 예제 — 활동 선택 문제

탐욕이 항상 실패하는 것은 아니다. 활동 선택 문제(activity selection problem)는 탐욕이 실제로 최적해를 보장하는 대표적인 예다. 문제는 “여러 활동(시작 시각, 종료 시각)이 주어졌을 때, 겹치지 않게 최대한 많은 활동을 선택하라”는 것이다.

다음 여섯 개 활동이 있다고 하자(시작, 종료 시각).

탐욕 전략: 종료 시각이 가장 빠른 활동부터 순서대로 확인하며, 지금까지 고른 마지막 활동의 종료 시각 이후에 시작하는 활동만 추가로 선택한다.

ActivitySelection(활동 목록):
  활동들을 종료 시각 기준으로 오름차순 정렬한다
  선택 목록 = 비어 있음, 마지막선택종료시각 = -무한대
  정렬된 순서대로 각 활동을 확인:
    만약 활동의 시작 시각 >= 마지막선택종료시각이면:
      이 활동을 선택 목록에 추가하고, 마지막선택종료시각 = 이 활동의 종료 시각으로 갱신
  선택 목록을 반환한다

종료 시각 순으로 정렬하면 A(1,3), B(2,5), C(4,6), E(5,8), D(6,7), F(7,9) 순서가 된다.

선택된 활동: A, C, D, F (총 4개), B와 E는 건너뛴다.

왜 이 탐욕은 최적해를 보장하는가 — 탐욕 선택 속성

활동 선택 문제에서 “종료 시각이 가장 빠른 활동을 첫 선택으로 고르는 것이 항상 안전하다”는 사실을 탐욕 선택 속성(greedy choice property)이라 부른다. 직관적으로, 종료 시각이 가장 빠른 활동을 골라 두면 그다음에 선택할 수 있는 활동의 후보가 절대 줄어들지 않는다(오히려 다른 어떤 활동을 먼저 골랐을 때보다 남은 시간이 가장 넉넉해진다). 이 속성이 성립하는 문제에서만 “한 번 고른 선택을 절대 번복하지 않는” 탐욕 전략이 최적해를 보장한다.

자주 틀리는 점: “활동을 짧은 것부터 고르면 되지 않을까”라고 생각하기 쉽지만, 이 문제의 탐욕 선택 속성은 종료 시각 기준이지 활동 길이(종료−시작) 기준이 아니다. 위 표에서 B(2,5)는 길이가 3으로 A(1,3)의 길이 2보다 길지만, 종료 시각(5)이 A의 종료 시각(3)보다 늦다는 이유만으로 A가 먼저 선택된다. 길이가 짧은 활동을 우선하는 탐욕은 이 문제에서 최적해를 보장하지 않는다(반례를 직접 구성할 수 있다).

동적계획법 vs 탐욕 — 판별 기준 정리

자주 틀리는 점: “그래프 알고리즘 중 크루스칼·프림·다익스트라는 탐욕인데, 왜 어떤 최적화 문제는 탐욕으로 안 되는가”라는 의문이 들 수 있다. 이 세 알고리즘은 각각 “간선을 가중치 순으로 고르면 사이클을 만들지 않는 한 항상 안전하다(MST)”, “이미 확정된 정점에서 가장 가까운 정점을 먼저 확정해도 안전하다(비음수 다익스트라)“는 탐욕 선택 속성이 수학적으로 증명되어 있는 특수한 문제이기 때문이다. 반대로 동전 교환처럼 탐욕 선택 속성이 성립하지 않는다고 알려진(또는 반례가 존재하는) 문제에는 탐욕을 적용하면 안 된다.

핵심 정리

• 동적계획법은 최적 부분 구조와 중복 부분 문제를 모두 가진 문제에서, 부분 문제의 답을 저장해 재사용함으로써 반복 계산을 없앤다.
• 동전 교환 문제(동전 1, 3, 4로 6원 만들기)에서 DP는 최적해 2개(3+3)를 찾지만, 탐욕(가장 큰 동전 우선)은 3개(4+1+1)로 최적이 아닌 답을 낸다.
• 활동 선택 문제에서는 “종료 시각이 가장 빠른 활동을 먼저 고르는” 탐욕 선택 속성이 성립해, 탐욕 전략만으로도 최적해(A, C, D, F)를 보장한다.
• 어떤 문제에 탐욕을 적용해도 되는지는 “지금 당장 최선의 선택이 전체 최적해로 이어짐”이 증명되어 있는지에 달려 있으며, 이것이 증명되지 않았거나 반례가 있다면 동적계획법으로 모든 선택지를 따져야 한다.

마무리 복습

참고 자료

• 설계기법 강의노트 - Greedy Algorithms / Dynamic Programming (GeeksforGeeks)  — 탐욕 선택 속성, 활동 선택 문제, 동전 교환 문제의 동적계획법 풀이를 정리한 자료.
• 국가평생교육진흥원 독학학위제  — 독학사 4단계 알고리즘 과목의 최신 출제기준·평가영역 확인용 공식 안내.