14. 같은 부분문제를 다시 풀지 않는다
해설글
작성 · 7분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
여러 이동 방법 중 가장 싼 비용을 찾는 문제
에어텔 문제의 입력은 도시 사이 비행 요금과 경유 도시의 숙박비다. 도시는 번호가 증가하는 방향으로만 이동한다. 출발 도시 s에서 도착 도시 d까지 갈 때 원하는 답은 항공료와 필요한 숙박비를 합친 최소 비용이다.
도시: 0, 1, 2
1칸 비행: 4원, 2칸 비행: 7원
도시 1 숙박: 2원
0→2 직항: 7원
0→1→2: 4+2+4=10원
답: 7원
큰 문제를 풀기 위해 다시 사용하는 작은 문제를 부분문제(subproblem)라고 한다. 여기서는 “출발점 s에서 도시 i까지 가는 최소 비용”이 부분문제다. 그 답을 C(i)라고 두면 도시가 달라도 질문의 모양이 같아진다.
상태(state)는 부분문제를 구분하는 정보다. 이 문제는 출발점과 요금표가 고정되어 있으므로 도착 도시 i가 상태가 된다. 점화식(recurrence)은 더 작은 상태의 답으로 현재 상태의 답을 만드는 규칙이다. 동적 계획법(DP)은 같은 상태를 여러 번 계산하지 않도록 답을 저장하고, 필요한 순서에 맞춰 재사용한다.
DP를 적용하려면 두 조건을 먼저 확인한다.
- 최적 부분 구조: 최적 경로가 k를 마지막 경유지로 쓴다면, s에서 k까지도 최적이어야 한다.
- 중복 부분문제: 서로 다른 재귀 경로가 같은
C(k)를 반복해서 요구한다.
이 정의를 먼저 두고 보고서의 두 함수를 보면, 둘은 다른 문제를 푸는 것이 아니라 같은 점화식을 서로 다른 계산 순서로 실행한다는 점이 드러난다.
같은 답을 내는 두 함수가 남아 있다
에어텔 과제 보고서에는 airtelDC와 airtelDP가 나란히 들어 있다. 전자는 앞 도시까지의 최소 비용을 재귀로 다시 구하고, 후자는 배열에 저장해 둔 값을 읽는다. 이 자료는 설명과 코드가 정리된 보고서라, 문장 전부를 당시의 자발적인 의문이나 깨달음으로 볼 수는 없다.
그래서 이 글은 보관된 코드의 선택을 직접 따라가는 데서 시작한다. 특히 재귀 함수에는 다음 주석이 있다.
주의 출발지 s에서 머무는 것은 숙박비에 포함되지 않으므로 0원으로 처리
알고리즘 이름보다 먼저 확인할 것은 이 조건이다. 같은 점화식을 효율적으로 계산해도, 어디서 숙박비를 내는지 잘못 세면 더 빨리 틀린 답을 내게 된다. 이번에는 작은 요금표를 새로 만들어 비용, 호출 횟수, 실제 이동 경로를 함께 검사했다.
마지막 비행기 직전의 도시를 고른다
도시 번호가 증가하는 방향으로만 이동한다고 하자. 거리 r인 비행의 요금은 fare[r], 도시 k에서 묵는 비용은 hotel[k]다. 출발지 s와 도착지 d에서는 숙박비를 내지 않고 경유지에서만 낸다.
도시 i로 오는 마지막 비행기가 k에서 출발했다면, 전체 비용은 s→k의 최소 비용에 k에서의 숙박비와 k→i 항공료를 더한 값이다. k가 출발지일 때만 숙박비를 0으로 만든다.
\[C(s)=0,\qquad C(i)=\min_{s\le k<i}\left(C(k)+h_s(k)+A[i-k]\right)\]점화식의 각 항을 비용 영수증처럼 나누면 다음과 같다.
| 항 | 의미 |
|---|---|
| $C(k)$ | 출발 도시 s에서 마지막 경유 후보 k까지 오는 최소 비용 |
| $h_s(k)$ | k에서 묵는 비용. k가 출발지 s이면 0 |
| $A[i-k]$ | k에서 i까지 마지막 비행의 항공료 |
| $\min_{s\le k<i}$ | 가능한 마지막 출발 도시를 모두 비교해 가장 싼 후보 선택 |
예를 들어 C(4)를 구할 때 k=2를 고른 항은 “2까지 오는 최선의 비용 + 2에서 숙박 + 2에서 4로 비행”이다. 최소값을 고른 뒤에는 previous[4]=2처럼 선택한 k를 저장해야 비용뿐 아니라 실제 경로도 복원할 수 있다.
여기서 $h_s(k)$는 $k=s$이면 0, 나머지는 $H[k]$다. 이 식은 보고서의 코드에 있는 조건을 명시해 다시 쓴 것이다. 보고서 앞쪽의 짧은 점화식에는 Hotel[k]가 그대로 들어 있지만, 코드에서는 출발지 예외를 따로 처리했다.
C(k)는 k에 도착하기까지의 비용이다. k에서 떠나 다음 도시로 갈 때 숙박비를 더하므로 경유지 비용이 한 번씩만 들어가고, 도착지의 숙박비는 더할 기회가 없다. 한 상태가 어디까지의 비용을 포함하는지 먼저 정하니 중복 계산을 구분하기 쉬워진다.
재귀 호출 트리에는 같은 목적지가 반복된다
C(4)를 계산하려면 C(0), C(1), C(2), C(3)을 본다. 그 안의 C(3)은 다시 C(0), C(1), C(2)를 본다. 출발점과 요금표는 그대로인데 C(2)의 답을 두 번 구하는 것이다. C(1)은 더 많이 반복된다.
아래는 보고서의 재귀를 변수 이름과 계수 장치만 정리해 만든 검증 함수다. dc_calls는 기저 호출까지 포함한다.
static long long airtel_dc(const int fare[N], const int hotel[N], int s, int d) {
++dc_calls; if (s == d) return 0;
long long best = INF;
for (int k = s; k < d; ++k) {
long long value = airtel_dc(fare, hotel, s, k) + (k == s ? 0 : hotel[k]) + fare[d - k];
if (value < best) best = value;
}
return best;
}
이 구현의 호출 횟수를 목적지까지의 번호 차 r로 나타내면 T(0)=1, T(r)=1+T(0)+...+T(r-1)이다. 따라서 T(r)=2^r이다. 분할 정복이라는 이름 자체가 느린 것이 아니라, 같은 부분문제를 저장 없이 다시 푸는 이 재귀에 중복이 생긴다.
위에서 아래로 호출하면서 이미 구한 값을 보관하면 메모이제이션으로 바꿀 수 있다. 보고서의 airtelDP는 다른 방향을 택했다. 앞 도시부터 순서대로 답을 채우는 bottom-up tabulation이다. 보고서에 “메모이제이션을 이용한 상향식”이라고 적혀 있지만, 이 글에서는 두 구현 방식을 구분한다.
배열의 왼쪽은 이미 계산되었다
static long long airtel_dp(const int fare[N], const int hotel[N], int s, int d, int previous[N]) {
long long cost[N]; cost[s] = 0; previous[s] = -1;
dp_transitions = 0;
for (int i = s + 1; i <= d; ++i) {
cost[i] = INF; previous[i] = -1;
for (int k = s; k < i; ++k) {
++dp_transitions;
long long value = cost[k] + (k == s ? 0 : hotel[k]) + fare[i - k];
if (value < cost[i]) { cost[i] = value; previous[i] = k; }
}
}
return cost[d];
}
dp_transitions는 안쪽 반복에서 후보 하나를 검사할 때마다 증가시키는 계수기다. i를 계산하는 동안 필요한 것은 cost[s..i-1]뿐이고, 이 값들은 앞선 반복에서 이미 구했다. 도시 번호가 증가하는 방향으로만 이동한다는 조건이 계산 순서를 보장한다.
배열을 전부 초기화하지 않아도 되는 이유도 여기 있다. cost[s]를 먼저 정하고, cost[i]를 쓸 차례에 초기화하며, 아직 정하지 않은 뒤쪽 칸은 읽지 않는다. 임의 방향 이동을 허용하거나 같은 도시를 다시 방문하는 문제로 바꾸면 이 점화식과 계산 순서를 그대로 쓸 수 없다.
이번 예제의 요금은 다음과 같다. 출발지와 도착지의 숙박비를 일부러 99로 두어도 답에 포함되면 안 된다.
fare[1..4] = 4, 7, 13, 20
hotel[0..4] = 99, 2, 1, 3, 99
s = 0, d = 4
| 목적지 i | 마지막 경유 후보별 비용 | C(i) | 직전 도시 |
|---|---|---|---|
| 1 | 4 | 4 | 0 |
| 2 | 7, 4+2+4=10 | 7 | 0 |
| 3 | 13, 4+2+7=13, 7+1+4=12 | 12 | 2 |
| 4 | 20, 4+2+13=19, 7+1+7=15, 12+3+4=19 | 15 | 2 |
답 15만 보는 대신 previous[4]=2, previous[2]=0을 따라가면 경로는 0→2→4다. 항공료 7 두 번과 경유지 2의 숙박비 1을 합해 15가 되는지 별도로 확인할 수 있다.
시간을 재기 전에 같은 일을 세어 본다
보고서에는 n=30에서 재귀 약 4,825ms, DP 약 0.003ms라는 수치가 적혀 있다. 하지만 함께 보관된 내용에는 실행 환경과 측정 원본이 충분하지 않다. 이 수치를 이번 실행 결과처럼 재사용하지 않고, 새 예제에서는 호출과 후보 검사 횟수를 셌다.
Airtel 0->4: 15, DC calls: 16, DP transitions: 10, reverse route: 4 2 0
번호 차가 r이면 DP는 1+2+...+r개의 후보를 검사하므로 O(r²) 시간이다. 재귀 호출은 이 구현에서 2^r회다. DP의 표와 경로 복원 배열은 입력 구간 길이에 비례하는 공간을 사용한다. 중복 계산을 없애도 도시가 늘면 DP 작업량은 계속 증가한다.
새 검증에서는 40개 요금표와 출발·도착 조합을 합친 1,200개 문제를 만들었다. 모든 경유지 부분집합을 열거한 답, 재귀 답, DP 답이 일치하는지 비교하고 복원한 경로의 비용도 다시 합산했다. 이 일치가 모든 입력의 정확성을 증명하지는 않지만, 출발지 예외나 숙박비 중복처럼 이 글에서 따진 조건을 실제로 검사한다.
방향 그래프 관점에서는 도시 k에서 i로 가는 간선에 h_s(k)+fare[i-k]를 붙인 DAG의 최단 경로이기도 하다. 번호순이 곧 위상 순서라 이미 구한 앞쪽 답으로 뒤쪽 답을 갱신한다. 이름으로 떨어져 보이던 그래프와 DP가 같은 계산 순서로 이어진다.
이 과제에서 남길 핵심은 “DP가 빠르다”보다 구체적이다. 상태가 포함하는 비용을 정하고, 같은 상태의 답을 한 번 계산한 뒤, 의존하는 순서대로 재사용한다. 그러면 속도 차이와 함께 출발지 숙박비를 빼야 하는 이유, 뒤쪽 배열을 아직 읽지 않아도 되는 이유까지 같은 코드에서 설명할 수 있다.
기록과 실행 코드
- 개인 보관 자료 「알고리즘 1130 과제 보고서」, 2025-11-30
- 이번에 작성한 C 코드와 검증 전체:
airtel_dc,airtel_dp,airtel_routes,check_dp