분할정복·그리디·동적계획·백트래킹

이어 읽을 선수 설명: 정당성은 불변조건과 종료를 한 줄로 잇는다, 순차·분기·반복·재귀. 각 설명의 전제를 확인한 뒤 아래의 단계 풀이와 자체 문제를 연결한다.

같은 문제도 구조를 어떻게 보느냐에 따라 풀이가 달라진다

큰 문제를 잘게 나누어 각각 푼 뒤 합칠 수도 있고, 지금 가장 좋아 보이는 선택을 이어 갈 수도 있다. 같은 부분문제가 반복되면 답을 저장할 수 있고, 가능한 선택을 따라가다가 틀리면 되돌아올 수도 있다. 이 네 생각이 각각 분할정복, 그리디, 동적계획, 백트래킹이다.

중요한 것은 알고리즘 이름을 문제에 붙이는 일이 아니다. 문제에 실제로 존재하는 구조를 확인하고, 그 구조가 정답과 비용을 보장하는 이유를 설명하는 일이다. 그리디가 빠르다는 이유만으로 쓰면 오답을 낼 수 있고, 동적계획이 정답을 보장해도 상태 수가 너무 크면 실행할 수 없다. 백트래킹은 가지치기가 약하면 모든 경우를 사실상 다 볼 수 있다.

알고리즘 설계전략의 정확한 뜻

알고리즘 설계전략은 문제의 부분구조와 선택관계를 이용하여 해법을 구성하고, 그 해법의 정당성과 비용을 함께 설명하는 재사용 가능한 사고방식이다. 하나의 전략이 하나의 코드 모양을 뜻하지는 않는다. 재귀로 썼다고 모두 분할정복은 아니며, 표를 썼다고 모두 동적계획도 아니다.

전략을 선택하려면 먼저 문제 명세에서 다음을 찾아야 한다.

• 입력 크기와 값의 범위는 무엇인가?
• 구해야 하는 것이 가능한 해 하나인지, 모든 해인지, 최적해인지 구분했는가?
• 작은 문제의 답으로 큰 문제의 답을 만들 수 있는가?
• 부분문제가 서로 독립적인가, 같은 부분문제가 반복되는가?
• 지금의 선택이 이후 선택을 망치지 않는다는 성질을 증명할 수 있는가?
• 후보를 일찍 버릴 수 있는 제약이나 상한·하한이 있는가?

이미 배운 기반을 짧게 연결한다

알고리즘은 유한한 단계로 입력을 출력으로 바꾸는 명확한 절차이고, 문제 명세는 입력·출력·제약·성공조건을 고정한다. 재귀는 더 작은 같은 형태의 문제와 종료사례로 풀이를 표현하며, 시간·공간 복잡도는 입력이 커질 때 필요한 연산과 저장공간의 증가를 본다. 이번 절은 이 정의를 토대로 부분문제 관계 → 선택전략 → 정당성 근거 → 시간·공간 비용 → 실패조건의 연결을 깊게 다룬다.

전략과 자료구조를 분리해서 보지 않는다

어떤 전략도 적절한 자료구조 없이 독립적으로 존재하지 않는다. 동적계획의 상태표, 그리디의 우선순위 큐, 백트래킹의 선택 스택도 모두 비용의 일부다. 같은 수학적 전략이라도 자료표현과 입력 범위가 달라지면 실제 시간·공간과 실패조건도 달라진다.

네 전략을 한눈에 잡는다

네 전략은 배타적이지 않다. 분할정복을 재귀로 표현할 수 있고, 동적계획은 재귀 메모이제이션이나 반복형 표 채우기로 구현할 수 있다. 백트래킹도 깊이우선탐색과 재귀를 흔히 사용한다. 구분 기준은 문법이 아니라 부분문제와 선택을 어떤 원리로 줄이는가이다.

분할정복: 나누기·풀기·합치기

분할정복은 다음 세 단계로 진행한다.

1. 분할: 크기 n인 문제를 더 작은 부분문제로 나눈다.
2. 정복: 충분히 작은 종료사례는 직접 풀고, 나머지는 같은 방법으로 푼다.
3. 결합: 부분문제의 답을 원래 문제의 답으로 합친다.

병합정렬은 배열을 반씩 나누어 각각 정렬한 뒤 두 정렬열을 합친다. 부분배열 정렬은 서로 독립적이고, 병합은 전체 원소 수에 비례한다. T(n)은 크기 n인 입력을 처리하는 연산량이며, 2T(n/2)는 절반 크기 두 문제를 푸는 비용, +O(n)은 그 두 결과를 합치는 비용을 뜻한다. 그래서 전형적인 비용은 T(n)=2T(n/2)+O(n), 전체 시간은 O(n log n)이다. 이진탐색도 정렬된 구간의 절반만 남기는 분할정복이지만, 버린 절반은 풀 필요가 없어 T(n)=T(n/2)+O(1)이고 O(log n)이다. 일반형 aT(n/b)+f(n)을 만나면 a는 풀 부분문제 수, b는 크기를 줄이는 비율, f(n)은 나누기·합치기의 추가 비용으로 읽는다.

분할정복이라고 항상 빠른 것은 아니다. 부분문제가 겹치는데 답을 저장하지 않으면 같은 계산을 반복하고, 분할은 쉽지만 결합이 비싸면 전체 비용을 지배한다. 재귀 깊이에 따른 스택 공간과 병렬 실행 시 작업 분할·결과 결합 비용도 포함해야 한다.

그리디: 가장 좋아 보이는 선택을 언제 확정할 수 있는가

그리디 알고리즘은 현재 상태에서 목적함수에 가장 유리해 보이는 후보를 선택하고, 그 선택을 되돌리지 않은 채 다음 단계로 간다. 일반적인 구성은 후보집합 → 선택규칙 → 가능성 검사 → 선택 확정 → 종료 검사다.

하지만 국소 최선이 전체 최선인지는 문제마다 다르다. 다음 둘을 설명할 수 있어야 한다.

• 그리디 선택 성질: 어떤 최적해도 첫 그리디 선택을 포함하는 최적해로 바꿀 수 있다.
• 최적 부분구조: 첫 선택 뒤 남은 문제의 최적해를 붙이면 전체 최적해가 된다.

예를 들어 한 회의실에서 겹치지 않는 회의를 가장 많이 고르는 문제는 종료시각이 가장 이른 회의를 고르는 규칙을 교환논증으로 증명할 수 있다. 어떤 최적해의 첫 회의를 더 일찍 끝나는 그리디 회의로 바꾸어도 뒤의 회의를 잃지 않기 때문이다. 반면 동전 {1, 3, 4}로 금액 6을 최소 개수로 만들 때 큰 동전부터 고르면 4+1+1 세 개지만 최적은 3+3 두 개다. 선택규칙이 그럴듯해도 증명이 없으면 정확한 알고리즘이 아니다.

교환논증은 임의의 최적해 일부를 그리디 선택으로 바꾸어도 해가 유효하고 품질이 나빠지지 않음을 보이는 방법이다. 절단 성질은 그래프처럼 후보를 두 집합으로 나눈 경계에서 특정 선택을 현재 부분해에 더해도 최적성을 보존하며, 그 선택을 포함하는 적어도 하나의 최적해가 존재함을 보이는 문제별 성질이다. 두 방법 모두 모든 그리디 문제에 자동 적용되는 공식이 아니라, 해당 선택규칙이 안전한 이유를 증명하는 도구다.

동적계획: 상태가 미래에 필요한 정보를 모두 담아야 한다

동적계획은 같은 부분문제의 답이 반복해서 필요할 때 그 답을 저장해 재계산을 없앤다. 최솟값·최댓값뿐 아니라 경우의 수를 세거나 가능한지를 판정하는 문제에도 쓴다. 모든 동적계획에 공통으로 필요한 것은 현재 상태가 더 작은 상태들에 의존하는 재귀적 관계, 그 의존을 먼저 계산할 수 있는 순서, 그리고 미래의 답을 구별할 만큼 충분한 상태다. 최적 부분구조나 최적성 원리는 그중 최적화 문제에서 각 상태의 최적해를 결합할 때 요구되는 조건이다. 단순히 배열을 채우는 기법이 아니라 다음 여섯 요소를 설계하는 일이다.

1. 상태: 부분문제를 유일하게 구별하는 최소 정보
2. 값의 의미: 그 상태에 저장된 수가 무엇을 뜻하는지
3. 점화식: 더 작은 상태의 답으로 현재 값을 만드는 규칙
4. 초깃값: 더 쪼갤 필요 없이 직접 아는 상태
5. 계산순서: 필요한 이전 상태가 먼저 준비되는 순서
6. 최종위치와 복원: 정답 값과 실제 선택을 어디서 꺼내는지

동전 {1, 3, 4}에서 금액 x를 만드는 최소 개수를 dp[x]라 두면 dp[x]=1+min(dp[x-1], dp[x-3], dp[x-4])로 표현할 수 있다. 존재하지 않는 음수 상태는 제외하고 dp[0]=0에서 작은 금액부터 채우면 dp[6]=2를 얻는다. 시간은 금액 B와 동전 종류 수 k에 대해 O(Bk), 공간은 O(B)다.

위에서 필요한 상태만 재귀적으로 계산해 저장하는 방식을 메모이제이션, 작은 상태부터 순서대로 채우는 방식을 표 채우기 또는 태뷸레이션이라 한다. 둘은 같은 점화식을 쓸 수 있지만 호출 스택, 실제 방문 상태, 순서 통제와 상수비용이 다르다.

최소 개수가 나오는 중간 계산은 다음과 같다. 각 후보는 마지막에 쓴 동전 한 개와 남은 금액의 최적 개수를 더한 값이며, —는 음수 금액이라 사용할 수 없다는 뜻이다.

금액 6에서는 마지막 3을 택한 후보가 1+dp[3]=2로 가장 작다. 선택한 동전 3을 빼고 금액 3의 선택 3을 다시 따라가면 실제 해 3+3을 복원한다.

min은 후보 중 가장 작은 값을 고르라는 뜻이며 dp의 대괄호 안 숫자는 금액, 저장값은 동전 개수다. 표에 이어 금액 7의 세 후보와 실제 동전 선택을 채워 보자. 마지막 1이면 1+dp[6]=3, 마지막 3이면 1+dp[4]=2, 마지막 4이면 1+dp[3]=2이므로 최소는 2개, 선택은 3+4다. 동률의 두 후보는 서로 다른 마지막 선택으로 같은 조합을 얻는다. 금액 7을 그대로 dp 값 7로 적었다면 상태를 구별하는 금액과 그 상태의 답인 개수를 혼동한 것이므로 표의 6 행에서 금액 6·개수 2를 다시 확인한다.

불가능한 상태와 서로 다른 미래를 구별한다

동전 종류에 1이 있어서 앞의 모든 금액은 만들 수 있었다. 동전을 {3,4}로 바꾸면 dp[1], dp[2], dp[5]는 불가능하다. 이 칸을 0으로 적으면 “그 금액을 동전 없이 만들었다”는 거짓 답이 된다. dp[0]=0만 직접 가능한 초기 상태로 두고 나머지는 무한대 표식으로 시작한다. dp[x-c]가 유한한 후보에서만 한 개를 더하며, 후보가 하나도 없으면 불가능 상태를 유지한다. 예컨대 dp[5]는 남은 금액 2 또는 1이 불가능해 그대로이고, dp[6]은 1+dp[3]=2가 가능하다.

무제한 동전과 한 번만 쓸 수 있는 과제도 다른 상태가 필요하다. 동전을 반복 사용할 때는 남은 금액이 같으면 다음에 쓸 동전도 같다. 반면 0/1 과제에서 “남은 예산 2”라는 정보만 보면 비용 2인 A를 이미 썼는지, 아직 선택할 수 있는지 알 수 없다. 그래서 dp[i][b]는 고려한 과제의 경계 i와 예산 b를 함께 넣는다. 1차원으로 압축해도 i에 해당하는 바깥 반복과 예산 순회 방향으로 그 경계를 지켜야 한다. 두 경우를 같은 상태로 합쳤을 때 가능한 다음 선택이 달라지는가를 묻는 것이 상태 충분성의 첫 검사다.

백트래킹: 선택트리를 완전하게 만들고 안전하게 잘라낸다

백트래킹은 해의 일부를 하나씩 만들며 선택트리를 깊이우선으로 탐색한다. 후보를 선택하고, 제약을 확인하고, 더 진행할 수 없으면 선택을 취소한 뒤 다음 후보를 시도한다.

정확성을 지키려면 두 조건이 필요하다. 첫째, 생성규칙이 가능한 모든 완전해를 빠뜨리지 않아야 한다. 둘째, 가지치기는 그 가지에서 유효한 해나 더 나은 최적해가 절대로 나오지 않는다는 근거가 있어야 한다. 지금 보기 싫다는 이유로 자르면 정답을 잃는다.

되돌리기가 실제로 무엇을 복구하는지 작은 예로 보자. 자체 교육 예제로 예산 5, 과제 A의 비용 2·효과 3, B의 비용 3·효과 4, C의 비용 4·효과 6을 두고 각 과제를 한 번씩만 선택한다. 현재 상태는 (선택목록, 비용합, 효과합)이며 처음에는 (빈 목록,0,0)이다. A 선택 뒤 ({A},2,3), B 선택 뒤 ({A,B},5,7)이 된다. 여기서 C를 추가하면 비용이 9이므로 이 가지는 예산을 넘겨 더 진행하지 않는다. B 선택을 취소하면 반드시 ({A},2,3)으로 돌아가며, 다음 C 선택도 비용 6이라 제외한다. A까지 취소하면 (빈 목록,0,0)이 되어 B만 고른 해와 C만 고른 해도 조사할 수 있다.

가능한 완성 선택은 빈 목록, {A}, {B}, {C}, {A,B}이며 효과는 각각 0,3,4,6,7이어서 최적은 {A,B}다. {A,C}, {B,C}, {A,B,C}는 비용이 예산을 넘는다. 비용이 모두 양수이므로 이미 예산을 넘은 부분선택에 과제를 더해도 유효해가 될 수 없다는 것이 여기서 가지치기를 정당화하는 이유다. B를 취소할 때 목록에서만 B를 빼고 비용합 5를 남기면 어떤 문제가 생기는가? 이후 상태가 실제 선택 {A}의 비용 2와 달라져 가능한 선택을 잘못 버린다. 선택과 취소가 목록·비용·효과를 함께 되돌려야 한다는 것을 앞 두 상태와 대조한다.

N-퀸은 N×N 격자에서 서로 같은 행·열·대각선에 놓이지 않도록 N개의 말을 배치하는 문제다. 한 행에 하나씩 놓으면서 이미 사용한 열과 두 대각선을 집합으로 관리하고 충돌하는 후보는 즉시 버린다. 제약전파는 한 선택으로 불가능해진 값을 연결된 다음 후보에서도 제거하는 것이고, 대칭제거는 회전·반사처럼 본질적으로 같은 해를 대표 하나만 탐색하도록 줄이는 것이다. 최악에는 경우의 수가 지수적으로 커질 수 있지만, 좋은 후보 순서·제약전파·대칭제거·상한 계산은 실제 탐색량을 크게 줄일 수 있다.

같은 축으로 비교한다

빠르다, 정확하다 같은 한 단어 비교는 부족하다. 정확성 보장 조건, 최악복잡도, 필요한 메모리, 입력 범위와 근삿값 허용 여부를 함께 써야 한다.

정답을 보장하는 이유를 전략별로 쓴다

앞서가기 논증은 그리디가 만든 부분해가 매 단계에서 어떤 최적해의 같은 길이 부분보다 뒤처지지 않음을 보인 뒤 최종 품질을 결론 내리는 방법이다. 앞 단계의 비교기준과 다음 단계에도 그 관계가 보존되는 이유를 함께 써야 한다.

증명을 장황한 수식으로만 쓸 필요는 없다. 다만 최적이라고 가정한다로 결론을 반복해서도 안 된다. 무엇을 바꾸어도 손해가 없는지, 점화식이 모든 마지막 선택을 포함하는지, 가지치기 조건이 왜 안전한지를 구체적으로 밝힌다.

여기까지의 결론

분할정복은 나눈 답의 결합, 그리디는 되돌리지 않는 선택의 증명, 동적계획은 충분한 상태와 의존순서, 백트래킹은 후보공간의 완전성과 안전한 가지치기가 핵심이다. 재귀나 표 같은 코드 모양만으로 전략을 구분하지 않는다. 다음부터는 문제의 목표·겹침·증명 가능성·상태 수·자원예산으로 전략을 선택한다.

선택은 여덟 질문으로 좁힌다

1. 목표: 가능해 하나, 모든 해, 정확한 최적해, 근사해 중 무엇인가?
2. 분해: 더 작은 같은 형태로 나눌 수 있는가?
3. 겹침: 같은 부분문제가 여러 경로에서 반복되는가?
4. 국소선택: 선택을 되돌리지 않아도 된다는 증명이 있는가?
5. 상태: 미래에 필요한 정보를 작고 유일한 상태로 표현할 수 있는가?
6. 가지치기: 불가능하거나 현재 최선보다 나쁜 가지를 안전하게 판정할 수 있는가?
7. 예산: 입력 최대치에서 시간·공간 상한을 감당할 수 있는가?
8. 검증: 작은 전수탐색과 반례 생성으로 정확성을 비교할 수 있는가?

그리디 증명이 없다면 동적계획이나 탐색을 검토한다. 상태 수가 너무 크면 상태압축·문제분해·근사 또는 제약탐색을 비교한다. 빠르게 쓸 만한 답을 찾되 일반적인 정확성이나 품질보장은 따로 증명되지 않은 경험적 규칙을 휴리스틱(heuristic)이라고 하므로, 이를 선택하면 실패사례와 품질 측정방법을 함께 밝힌다. 정확한 최적해가 필수가 아니라면 오차보장과 실행시간을 명시한 근사법이 더 적절할 수도 있다.

시간과 공간을 세는 법

동적계획의 O(nB)에서 B가 숫자값이면 입력 비트 길이에 대해서는 매우 클 수 있다. 이처럼 숫자값에는 다항식이지만 그 수를 적는 비트 길이에 대해서는 지수적으로 커질 수 있는 비용을 의사다항(pseudopolynomial)이라고 하며, 단순히 다항시간이라고 쓰면 오해가 생긴다. 백트래킹도 가지치기 후 평균 실행이 빠르다는 실험과 최악 상한을 분리해야 한다. 그리디는 선택 전에 정렬하면 전체가 흔히 O(n log n)이며, 분할정복은 재귀식의 결합항을 빼먹지 않는다.

없앨 수 없는 교환관계

좋은 설계는 한 전략을 끝까지 고집하지 않는다. 예를 들어 백트래킹의 남은 최적값 상한을 동적계획으로 계산하거나, 분할정복한 부분을 동적계획으로 풀 수 있다. 조합할수록 경계와 비용을 더 명확히 써야 한다.

어디서 실패하는가

하나의 작은 반례로 전략 차이를 확인한다

문제는 동전 {1, 3, 4}를 반복 사용하여 금액 6을 최소 개수로 만드는 것이다.

그리디: 가장 큰 4 선택 → 남은 2 → 1, 1 선택 = 3개
최적해: 3, 3 = 2개

DP 상태: dp[x] = 금액 x의 최소 동전 수
초기값: dp[0] = 0
전이:   dp[x] = 1 + min(dp[x-c])  (c는 x 이하의 동전)
결과:   dp[6] = 2

그리디는 유효한 해를 빠르게 만들지만 최적성을 잃었다. 동적계획은 금액별 최적 답을 저장해 정확한 답을 만든다. 백트래킹으로 모든 조합을 탐색해도 정답을 얻지만, 금액과 동전 종류가 커지면 후보 수가 급증한다. 분할정복만 적용하면 같은 남은 금액을 여러 경로에서 반복 계산하므로, 답을 저장하는 순간 동적계획의 핵심으로 넘어간다.

이 예는 동적계획이 언제나 우월하다는 뜻이 아니다. 통화 체계처럼 특정 동전집합에서 그리디 최적성이 증명되거나 입력 범위가 매우 크고 근사해가 허용되면 다른 선택이 적절할 수 있다.

알고리즘 설계의 핵심 학습 논점

알고리즘을 공부할 때는 특정 정렬법 하나를 외우는 데 그치지 않고, 문제구조에 맞는 전략과 그 전략이 옳은 이유를 설명해야 한다. 다음 다섯 가지를 점검하자.

1. 문제 명세와 입력 제약을 기준으로 설계전략을 선택한다.
2. 분할정복·그리디·동적계획·백트래킹의 부분문제 구조와 작동원리를 구분한다.
3. 정당성 조건과 반례, 시간·공간 복잡도를 함께 제시한다.
4. 상태·자료구조·가지치기·결합방식이 성능과 정확성에 미치는 영향을 설명한다.
5. 실패조건과 검증방법까지 답안 구조로 전환한다.

앞 절의 탐색·정렬·그래프 알고리즘은 이 원리를 구체화한 사례다. 같은 사례를 다시 볼 때, 부분문제의 관계·선택의 정당성·상태 수·가지치기 조건을 기준으로 전략을 설명해 보자.

시험에서는 어떻게 묻는가: 10점

다음은 알고리즘 설계전략의 선택과 정당성을 연습하기 위한 자체 제작 문제다. 실제 기출이나 공식 배점 기준을 뜻하지 않는다.

분할정복, 그리디, 동적계획, 백트래킹의 작동원리와 적용조건을 비교하고, 각 전략의 대표 실패조건을 설명하시오.

작동원리는 부분문제를 줄이는 방식, 적용조건은 정당성을 보장하는 문제구조, 실패조건은 오답 또는 실행불능이 생기는 조건을 요구한다. 알고리즘 예시만 네 개 쓰면 요구어를 충족하지 못한다.

예산 5에서 두 과제를 끝까지 계산한다

독립적인 과제 A는 비용 2·효과 3, B는 비용 3·효과 4이며 각 과제는 최대 한 번만 선택한다. dp[i][b]는 앞의 i개 과제로 예산 b 이하에서 얻는 최대효과다. 과제 i를 빼면 dp[i−1][b], 넣을 수 있으면 dp[i−1][b−c[i]]+v[i]이므로 두 후보의 큰 값을 저장한다. 표에는 b=0,1,2,3,4,5 순서의 값을 한 행으로 묶었다.

최종칸 7은 이전 행 3과 다르므로 B를 선택하고 남은 예산은 5−3=2다. A 행의 예산 2 값 3도 이전 행 0과 다르므로 A를 선택한다. 선택목록 {A,B}의 비용 2+3=5, 효과 3+4=7이 표와 일치한다. 동률이면 제외를 택하는 등 복원 규칙을 고정하면 여러 최적해 중 하나를 일관되게 얻는다.

1차원 배열에서 A를 처리할 때 예산을 오름차순으로 순회하면 dp[2]=3을 만든 뒤 dp[4]=dp[2]+3=6으로 같은 A를 두 번 쓰게 된다. 내림차순이면 예산 4를 계산할 때 아직 이전 행의 dp[2]=0을 읽어 3에 머문다. 이 차이가 0/1과 무제한 선택을 가르는 실제 상태 변화다.

2차원 점화식을 1차원으로 줄일 때 순서가 바뀌면 답도 바뀐다

2차원 표 dp[i][b]는 i번째 과제를 계산할 때 이전 행 i-1만 읽는다. 최댓값만 필요하면 한 배열을 재사용할 수 있지만, 예산 b를 작은 값부터 갱신하면 이번 과제로 방금 바꾼 dp[b-c[i]]를 다시 읽어 같은 과제를 여러 번 고르게 된다. 따라서 0/1 선택에서는 b=B..c[i]의 역순으로 갱신해 각 칸이 여전히 이전 행의 값을 읽도록 한다.

실제 선택목록까지 복원하려면 2차원 표나 별도의 선택·부모정보를 남겨야 한다. 단순한 1차원 최댓값 배열만으로는 일반적으로 어떤 과제를 골랐는지 되살릴 수 없다. 공간을 줄이는 결정과 답을 복원하는 결정은 함께 검토해야 한다.

시험에서는 어떻게 묻는가: 25점

다음 역시 본문만으로 풀 수 있게 만든 자체 제작 문제다.

비용과 기대효과가 주어진 정보화 개선과제 중 예산 한도 안에서 총효과를 최대화하는 0/1 선택 알고리즘을 설계하시오. 동적계획의 상태·점화식·복잡도와 복원방안을 제시하고, 그리디 및 백트래킹 대안의 적용조건·실패조건·검증방안을 비교하시오.

0/1은 각 과제를 선택하거나 선택하지 않는다는 뜻이다. 효과가 선택한 분량에 선형으로 비례하고 과제들이 서로 독립적이어서 임의 비율로 나눌 수 있을 때는 효과/비용 비율 그리디를 정당화할 수 있다. 과제를 쪼갤 수 없거나 효과가 비선형이거나 과제 간 종속성이 있으면 그 결론을 그대로 쓸 수 없으며, 일반적인 0/1 문제의 정확해도 보장하지 않는다. 답안은 상태의 뜻과 범위부터 고정해야 한다.

직접 연습: 숫자와 조건을 바꾸어 전략을 검증한다

다음 세 문제는 자체 연습이다. 먼저 결과를 계산하고, 그 결과를 보장하는 조건을 함께 적어 보자.

1. 동전 {3,4}를 반복 사용하여 금액 5와 6을 만드는 최소 개수를 구하라. 불가능한 상태를 0으로 초기화하면 금액 5에서 어떤 거짓 후보가 나오는가?
2. 예산 5, A(비용 2·효과 3), B(3·4), C(4·6)를 각각 한 번만 선택한다. 효과/비용 비율 순서로 고르는 그리디와 모든 부분집합의 최적해를 비교하라. 같은 비용·효과라도 과제를 자유롭게 나눌 수 있다면 왜 결론이 달라지는가?
3. 과제 1000개, 예산 B=1,000,000, 값 한 칸을 8바이트로 두자. 2차원 (n+1)×(B+1) 표와 1차원 B+1 배열의 값 저장공간을 바이트로 계산하라. 1차원 배열이 작으면 O(nB) 실행시간도 자동으로 감당할 수 있는가?

근거와 현행성

정의와 전략 경계는 미국 국립표준기술연구소(NIST) 정보기술연구소의 Dictionary of Algorithms and Data Structures에서 divide and conquer, greedy algorithm, dynamic programming, memoization, principle of optimality, backtracking, recursion 항목과 대조했다. 사이트 DOI는 10.18434/T4/1422485, 기준 확인일은 2026-08-31이다.

예산 수치와 입력 길이를 구별하는 비용 설명은 MIT 6.006의 배낭문제·의사다항 시간 강의자료와 함께 대조했다. 추가 연습의 메모리 수치는 한 칸 8바이트라는 자체 가정의 계산이며 특정 언어의 실제 배열 메모리를 뜻하지 않는다.

본문의 표·도식·동전 반례·정보화 과제 선택 문제와 답안은 원문 표현이나 그림을 옮기지 않고 교재용으로 독자 구성했다. 복잡도는 본문에 명시한 전형적 구현과 전제 아래의 이론값이며 특정 언어·제품의 보장을 뜻하지 않는다. 각 문제의 조건에서 전략이 올바른지 확인하는 것이 목적이며, 자체 제작 답안을 공식 채점 기준으로 해석하지 않는다.

30초 정리

1. 분할정복은 독립 부분문제를 나누어 풀고 결합하며, 그리디는 증명 가능한 국소선택을 확정한다.
2. 동적계획은 겹치는 부분문제를 상태·점화식으로 한 번씩 풀고, 백트래킹은 완전한 선택트리를 안전하게 가지치기한다.
3. 전략 이름보다 정당성 조건, 상태·자료구조, 시간·공간과 반례·최악입력을 함께 써야 한다.
4. 작은 전수정답과 경계입력으로 검증하고 입력 범위나 정확도 요구가 바뀌면 전략을 다시 선택한다.

다음 장부터는 같은 원칙을 운영체제, 수치해석, 가상화와 네트워크의 구체적인 문제구조에 적용한다.