문제 정의와 불변식
알고리즘은 입력을 출력으로 바꾸는 절차이지만, 설계의 시작은 코드가 아니라 문제의 의미입니다. 입력의 범위, 출력의 정확한 형태, 허용되지 않는 상태와 비용 단위를 먼저 정합니다. “정렬한다”면 오름차순인지, 동점의 입력 순서를 보존하는지, 같은 원소를 잃거나 복제하지 않는지까지 포함해야 합니다.
불변식은 절차가 진행되는 동안 계속 참이어야 하는 문장입니다. 이진 탐색에서 아직 답이 될 수 있는 구간과 이미 답이 아닌 구간을 나누는 문장이 한 예입니다. 루프 시작, 한 번의 갱신 뒤, 종료 시점에 불변식이 어떻게 이어지는지 쓰면 경계 오류를 추적하기 쉽습니다.
정확성 주장은 종료와 결과로 나눕니다. 먼저 구간 길이·잔여 입력·재귀 크기 같은 종료 측정값이 매 단계 줄어드는지 확인합니다. 그 다음 종료할 때 출력이 요구 조건을 만족하는지 확인합니다. 구간 길이가 줄지 않거나 재귀 호출에 같은 문제가 다시 들어가면 올바른 아이디어도 실제로는 끝나지 않습니다.
복잡도는 입력 크기만의 숫자가 아닙니다. 비교 함수가 긴 문자열을 읽거나 외부 저장소를 호출하면 비교 한 번의 비용이 추가됩니다. 메모리 대역폭, 캐시, 파일 I/O, 재귀 스택과 결과 복원 비용을 문제의 workload에 맞춰 해석합니다.
전략의 구분
분할 정복은 서로 겹치지 않는 작은 문제를 풀고 결과를 결합하는 전략입니다. 병합 정렬은 배열을 두 구간으로 나누고 정렬된 두 결과를 병합합니다. 동적 계획법은 같은 부분 문제의 답을 저장해 재사용합니다. 모든 재귀가 DP인 것은 아니며, 부분 문제가 겹치지 않는다고 해서 저장이 필요한 것은 아닙니다.
탐욕법은 매 단계에서 당장 가장 좋아 보이는 선택을 확정합니다. 구현은 간단할 수 있지만 그 선택을 포함하는 최적해가 항상 존재한다는 증명이 필요합니다. 선택을 바꿔도 해가 나빠지지 않는 교환 논증, 절단 성질, 최적 부분 구조 같은 근거 없이 “빨라 보인다”는 이유로 최적 알고리즘이라고 부르지 않습니다.
전략을 고르는 순서는 문제 의미 고정, 단순 기준 구현, 작은 입력 trace, 상태 또는 분할 정의, 정확성 증명, 비용 분석입니다. 증명할 수 없는 탐욕 규칙에는 반례를 만들고, 상태를 줄인 DP에는 서로 다른 미래를 가진 과거를 같은 상태로 합치는 반례를 만듭니다.
| 전략 | 재사용 또는 분할 조건 | 정확성의 핵심 |
|---|---|---|
| 분할 정복 | 독립적인 하위 문제와 결합 규칙 | 분할 경계·결합 불변식 |
| 동적 계획법 | 중복 하위 문제와 미래 충분 상태 | 점화식·상태 의미·순회 방향 |
| 탐욕법 | 현재 선택을 포함하는 최적해의 존재 | 교환 논증·절단 성질·반례 부재 |
동적 계획법의 상태
동적 계획법은 재귀 문법의 이름이 아니라, 같은 부분 문제의 답을 저장하고 재사용하는 설계입니다. 상태에는 미래 선택을 결정하는 데 필요한 최소 정보가 있어야 합니다. 과거를 모두 넣으면 정확할 수 있지만 상태 수가 커지고, 너무 줄이면 서로 다른 미래 가능성을 같은 상태로 합쳐 오답이 됩니다.
동전이 1·3·4이고 금액 6을 정확히 만들 때 큰 동전부터 고르면 4+1+1로 세 개지만 3+3은 두 개입니다. 금액 x의 최소 동전 수를 best[x]로 두면 마지막 동전 c를 뺀 best[x-c]에 하나를 더한 후보 중 최솟값을 택합니다. 양수 동전과 무제한 사용이라는 전제가 있어 x가 줄어드는 상태 의존이 생깁니다.
| 금액 | 마지막 선택 후보 | 최소 구성 | 최소 개수 |
|---|---|---|---|
| 0 | 없음 | 빈 선택 | 0 |
| 1 | 1 | 1 | 1 |
| 2 | 1 | 1+1 | 2 |
| 3 | 3 | 3 | 1 |
| 4 | 4 | 4 | 1 |
| 5 | 1 또는 4 | 4+1 | 2 |
| 6 | 1, 3 또는 4 | 3+3 | 2 |
동전 종류마다 한 개만 쓸 수 있다면 금액만으로는 상태가 충분하지 않습니다. 금액 4에 도달했더라도 어떤 동전을 이미 사용했는지에 따라 이후 선택 가능성이 달라집니다. 종류 인덱스나 남은 물건을 상태에 포함하고, 상태를 줄이는 최적화가 미래 가능성을 보존하는지 증명합니다.
0-1 배낭에서는 같은 물건을 두 번 쓰지 않도록 용량을 큰 값에서 작은 값으로 갱신합니다. 무게 2, 가치 3인 물건 하나와 용량 4에서 작은 방향으로 갱신하면 방금 갱신한 용량 2를 읽어 가치 6이 됩니다. 내림차순이면 이번 물건을 반영하기 전의 값을 읽어 가치 3만 얻습니다.
그림을 글로 읽기
- 원래 문제: 최적값과 선택 복원
- 충분한 상태: 금액·남은 물건·용량
- 점화식·갱신 방향
- 최적값·역추적 결과
- 원래 문제 → 충분한 상태: 미래 정보 추출
- 충분한 상태 → 점화식·갱신 방향: 가능한 마지막 선택
- 점화식·갱신 방향 → 최적값·역추적 결과: 답 재사용
탐욕법의 선택 조건
동전 1·3·4의 금액 6에서 큰 동전 우선은 4+1+1을 만들지만 3+3보다 나쁩니다. 이 반례는 모든 동전 체계에 탐욕 규칙을 이식할 수 없다는 뜻이지, 탐욕법이 쓸모없다는 뜻은 아닙니다. 문제 구조가 선택을 교환해도 손해가 없도록 허용하는지 확인해야 합니다.
분할 가능한 배낭은 가치/무게 비율이 높은 물건부터 선택할 수 있습니다. 용량 50에 (10,60),(20,100),(30,120)이 있으면 10과 20을 전부 담고 30짜리에서 20만큼을 취해 가치 240을 얻습니다. 일부를 나눌 수 있다는 전제가 있어 낮은 비율의 일부를 높은 비율로 바꾸는 교환 논증이 성립합니다.
같은 입력에서 물건을 통째로만 담는 0-1 배낭의 최적은 220이며 비율 순서대로 통째로 고르면 160에 그칠 수 있습니다. 문제 문장에 “나눌 수 없음”이 들어가면 분할 가능한 배낭의 증명이 사라집니다. 문제 이름이 비슷하다는 이유로 알고리즘을 전환하지 않습니다.
탐욕 선택을 쓰려면 현재 선택 뒤의 남은 문제가 원래 문제와 같은 구조인지, 선택을 바꾸는 교환 논증이나 절단 성질이 가능한지, 최적 부분 구조가 있는지 확인합니다. 증명이 길어지거나 반례가 쉽게 생기면 DP로 상태를 명시하는 편이 안전하지만, DP가 언제나 다항 시간인 것은 아닙니다.
분할 정복의 경계
퀵소트는 피벗을 기준으로 분할하지만 결합 때 별도 병합이 필요 없도록 피벗의 왼쪽과 오른쪽에 순서 조건을 만듭니다. Lomuto 분할에서 [lo,i)는 피벗 이하이고 [i,j)는 피벗보다 크며 [j,hi)는 아직 검사하지 않은 구간입니다. 마지막에 피벗을 i에 놓으면 피벗 위치가 확정됩니다.
[4,2,5,1,3]을 피벗 3으로 분할하면 [2,1,3,4,5]가 됩니다. 3은 제자리에 있지만 두 이웃 구간은 아직 정렬되지 않았습니다. 이후 호출에서 p를 다시 포함하면 같은 위치를 반복 처리할 수 있으므로 재귀 경계를 분할 함수의 반환 의미와 일치시킵니다.
나쁜 피벗이 계속되면 한쪽 크기가 n-1인 분할이 되어 O(n²)이 됩니다. 무작위 피벗은 특정 입력과 피벗 선택의 상관을 약화하지만 절대 최악 상한은 아닙니다. introsort는 깊이 예산이 소진되면 힙 정렬로 전환하여 최악 시간 계약을 보완할 수 있지만, 깊이 예산과 fallback 구현은 라이브러리별로 확인해야 합니다.
정렬 정확성
비교 정렬에서는 비교자가 사용하는 구현의 순서 계약을 만족해야 합니다. 예를 들어 strict weak ordering은 동등한 키의 묶음을 허용하며, 모든 레코드를 서로 다른 순위로 정할 필요는 없습니다. 병합 정렬의 병합 단계는 두 입력 구간이 각각 정렬되어 있다는 불변식을 사용합니다. 두 앞 원소 중 작은 값을 출력하면 출력 접두부는 정렬되어 있고, 같은 값에서는 왼쪽을 먼저 출력하면 안정성이 유지됩니다.
안정성은 정렬됨과 다릅니다. (80,A),(90,B),(80,C)를 점수로 정렬한 결과는 [80,A],[80,C],[90,B]처럼 동점 입력 순서를 보존해야 안정적입니다. 제자리 여부와 최악 시간도 별도 계약입니다. 보조 배열을 쓴 병합 정렬이 안정적일 수 있지만, 보조 배열을 쓴다는 사실만으로 안정성이 생기지는 않습니다.
키에 원본 순번을 붙여 (score,inputOrder)를 전순서로 만들면 불안정 정렬에서도 결과 순서를 명시할 수 있습니다. 대신 순번의 수명·범위·저장 비용과 비교 의미가 추가됩니다. 원본 순번만 붙이고 정렬 알고리즘이 그 키를 실제로 비교하지 않으면 요구를 충족하지 않습니다.
기수 정렬은 키를 자리별로 분배합니다. LSD는 낮은 자리에서 만든 동점 내부 순서를 높은 자리 분배가 안정적으로 보존해야 합니다. 32비트 signed 정수는 부호 비트 변환과 엔디언을 구분하고, 문자열은 종료 기호·UTF-8 바이트 순서·정규화·언어별 collation을 먼저 고정합니다.
탐색 경계
이진 탐색은 정렬된 배열에서 값을 찾는 절차로만 기억하기보다 단조 조건의 첫 참 위치를 찾는 방법으로 정의할 수 있습니다. lower_bound는 target 이상인 첫 위치를 돌려주며, 값이 없으면 삽입 위치를 돌려줍니다. 조건이 false...false,true...true로 한 번만 바뀐다는 전제가 필요합니다.
반열린 구간 [lo,hi)를 쓰면 [0,lo)는 target보다 작고 [hi,n)은 target 이상이라는 불변식을 유지할 수 있습니다. a[mid] < target이면 mid를 제외하고 lo=mid+1, 아니면 mid를 후보로 남겨 hi=mid로 둡니다. 구간 길이가 줄어 lo==hi가 되면 그 위치가 답입니다.
[1,2,2,4]에서 target 2의 lower_bound는 1이고 upper_bound는 target보다 큰 첫 위치인 3입니다. 따라서 같은 값의 구간은 [1,3)이고 개수는 2입니다. 중간에서 2를 발견해 즉시 반환하면 첫 번째 위치라는 요구를 놓칠 수 있습니다. 중간값은 lo + (hi-lo)//2로 계산해 고정 폭 정수의 lo+hi overflow를 피합니다.
복잡도와 자원
동전 DP의 상태가 금액 M과 동전 종류 C로 구성되면 시간 O(MC), 공간 O(M)입니다. M이 이진수로 짧게 표현되는 큰 수라면 표의 크기가 입력 비트 길이에 다항이라는 보장은 없으므로 의사 다항 시간이라고 부릅니다. 메모이제이션은 도달 상태를 줄일 수 있지만 최악의 상태 수를 자동으로 제거하지는 않습니다.
외부 병합 정렬은 메모리보다 큰 입력을 run으로 나눈 뒤 병합합니다. run k개를 한 번에 병합하면 비교 비용은 O(N log k)이지만, 입력·출력 버퍼와 힙·디코딩 객체가 메모리를 사용합니다. fan-in을 줄이면 병합 단계와 디스크 읽기·쓰기가 늘고, 늘리면 열린 파일과 버퍼 압박이 커집니다.
복잡도는 정확성 조건을 대신하지 않습니다. O(log n)인 이진 탐색도 저장 배열이 그 비교 기준으로 정렬되어 있지 않으면 오답입니다. O(n+R)인 계수 정렬도 R이 지나치게 크면 실제 메모리를 감당하지 못합니다. 수식의 변수와 전제를 workload 표에 적습니다.
성능을 확인할 때는 최종 평균만 기록하지 않습니다. 비교 횟수, 이동 바이트, 최대 재귀 깊이, 메모리 피크, 캐시·디스크 I/O, 결과 복원 시간과 오류율을 입력 분포별로 나눕니다. 실행하지 않은 수치를 이론적 상한이나 예시 숫자와 섞어 보고하지 않습니다.
구현과 반례 검증
다음은 설명용 의사코드입니다. 특정 라이브러리의 실제 API가 아니며 valid_comparator, state_is_sufficient, deadline 같은 검증 조건을 구현해야 합니다.
solve(problem):
define_input_output_and_boundaries(problem)
assert valid_comparator_or_transition(problem)
if has_overlapping_subproblems(problem):
state = choose_minimal_future_sufficient_state(problem)
prove_update_order_and_reconstruction(state)
return dynamic_program(state)
if has_provable_greedy_choice(problem):
prove_exchange_or_cut_property(problem)
return greedy(problem)
if has_valid_division_and_combination(problem):
return divide_and_conquer_with_merge_invariant(problem)
return choose_another_strategy_or_use_reference_search(problem)
각 알고리즘은 작은 기준 구현과 대조합니다. 정렬은 빈 배열, 역순, 모두 같은 키, 중복 레코드와 다중집합 보존을 확인합니다. DP는 완전 탐색과 최적값·복원 결과를 비교하고, 상태를 축약한 경우 서로 다른 미래를 가진 과거를 합치는 반례를 찾습니다.
이진 탐색은 빈 배열, 양끝보다 작은·큰 target, 중복, 모든 값 동일 입력을 선형 기준과 비교합니다. 매 반복의 불변식을 assertion으로 검사하고, 정렬 기준을 바꾸고 탐색 비교를 바꾸지 않은 실패도 만듭니다. 외부 정렬은 큰 레코드, 디스크 부족, 중단 출력, 재개와 완료 파일 공개를 따로 검증합니다.
운영에서는 알고리즘이 선택한 가정이 실제 입력에서 계속 유지되는지 관찰합니다. 키 범위가 갑자기 커졌는지, 동점률이 달라졌는지, 재귀 깊이·재시도·임시 run 수가 늘었는지, comparator 오류가 발생했는지 확인합니다. 입력 분포 변화는 구현 결함이 아니라 선택 계약의 만료일 수 있습니다.
참고 자료와 검증 범위
- 감사 대상 Algorithm README — 2026-09-17 확인, 커밋
26c959a31f279295931130833cb6d0a43592e26e, 전략·비교·비교 불가 정렬의 원문 범위입니다. - 동적 계획법의 상태와 탐욕 반례 — 기존 심화 노트, 상태 충분성과 갱신 방향의 연결 자료입니다.
- 이진 탐색과 경계 불변식 — 기존 심화 노트, 반열린 구간과 lower/upper bound의 연결 자료입니다.
- 퀵소트의 분할과 최악 시간 — 기존 심화 노트, 분할 불변식과 퇴화 입력의 연결 자료입니다.
- 정렬 안정성과 introsort의 서로 다른 보장 — 기존 심화 노트, 안정성·최악 시간·스택 상한의 연결 자료입니다.
- 계수 정렬과 기수 정렬의 키 표현 — 기존 심화 노트, 안정 분배·signed 키·문자열 키의 연결 자료입니다.
이 장의 표와 trace는 논리 예이며 이 문서의 작성 과정에서 알고리즘 성능 벤치마크나 특정 언어 라이브러리 내부 구현을 실행하지 않았습니다. 실제 적용 전에는 목표 언어·입력 분포·자원 예산에서 기준 구현과 속성 검사를 수행해야 합니다.