알고리즘 설계 기법Algorithm Design Techniques
문제를 어떻게 쪼개고 무엇을 먼저 고르는가를 정하는 설계 방법 다섯(분할 정복 · 동적 계획법 · 그리디 · 휴리스틱 탐색(A*) · 몬테카를로 방법)을 묶은 알고리즘의 한 갈래다. 비용을 재는 법은 알고리즘 분석이, 그래프 전용 절차는 그래프 알고리즘이 맡는다.
1요약
- 알고리즘 설계 기법은 알고리즘 안에서 분할 정복 · 동적 계획법 · 그리디 · 휴리스틱 탐색(A*) · 몬테카를로 방법을 «부분 문제가 겹치나 · 고른 것을 되돌릴 일이 없나 · 정답 대신 시간을 사나» 세 질문으로 묶고, 그 위에서 정렬 · 경로 · 배낭 같은 문제별 절차가 돈다.
- 같은 문제라도 기법이 비용과 정답을 가른다 — 동전 1 · 4 · 6원으로 32원을 만드는 최소 개수를 그대로 재귀로 풀면 호출 299,796번, 답을 표에 적으면 33칸이면 끝나고, 큰 동전부터 고르면 8원에서 이미 틀린 답이 나온다(직접 실행 · 그림 4 · 5).
- 결과가 이상할 때는 틀렸나 · 느리나 · 흔들리나로 가른다 — 틀리면 그리디의 전제(탐욕 선택 성질) 위반, 입력이 조금 늘 때 폭증하면 저장 없이 겹치는 부분 문제, 실행마다 값이 바뀌면 몬테카를로의 표본 수 부족이다.
2등장 배경
1940년대 핵무기 연구에서 중성자 확산처럼 식으로 풀 수 없는 확률 문제를 만나자, Metropolis 와 Ulam 은 1949년 무작위 표본을 많이 돌려 값을 추정하는 방법을 「몬테카를로 방법」이라는 이름으로 발표했다(Metropolis · Ulam 1949). 비슷한 때 Bellman 은 단계마다 결정을 내리는 최적화 문제에서 부분 문제의 답을 다시 쓰는 틀을 정리했다(Bellman 1954).
1968년 Hart · Nilsson · Raphael 은 로봇 경로 탐색에서 «간 비용 + 남은 비용 추정»으로 탐색 순서를 정하는 A* 를 내고, 추정이 실제를 넘지 않으면 최단 경로를 보장함을 보였다(Hart · Nilsson · Raphael 1968). 지금은 NIST 용어 사전이 다섯 기법을 각각 정의하고(NIST DADS divide and conquer), 언어 표준 라이브러리가 메모이제이션 · 난수 생성기를 내장해(Python functools) 실무의 일은 기법을 «고르는 판단»이 됐다.
3쉽게 이해하기 — 택배 영업소 소장의 하루 계획
택배 영업소 소장 박 씨는 아침마다 기사 넷의 배송을 짠다. 동네를 구역 넷으로 나눠 맡기고 저녁에 결과를 합치며, 한 번 잰 «영업소 → 2단지» 걸린 시간은 공책에 적어 다시 재지 않는다. 기사는 갈림길마다 지금 가장 가까운 집으로 가고, 처음 가는 동네는 목적지까지 남은 직선거리 표지를 보며 길을 고른다. 내일 배송 시간은 무작위 교통 · 날씨로 1,000번 흉내 내 평균을 낸다.
그림 1 · 소장이 배송 계획마다 고르는 다섯 방법이 곧 다섯 설계 기법이고, 방법마다 정답을 얼마나 보장하는지가 다르다.
그림 2 · 같은 구간을 여러 번 재는지가 분할 정복과 동적 계획법의 경계이고, 공책 한 권이 호출 31번을 계산 9번으로 줄인다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 소장 박 씨 | 설계 기법 선택 | 문제 성질(나뉨 · 겹침 · 크기)을 보고 기법을 고른다 |
| 구역 넷 나눔 | 분할 정복 | 독립인 작은 문제로 나눠 풀고 답을 합친다 |
| 구간 시간 공책 | 동적 계획법 | 겹치는 부분 문제의 답을 표에 저장해 다시 쓴다 |
| 가까운 집부터 | 그리디 | 그 순간 가장 좋은 선택을 되돌리지 않고 이어 간다 |
| 남은 직선거리 표지 | 휴리스틱 탐색(A*) | f = g + h 가 작은 상태부터 펼쳐 탐색 수를 줄인다 |
| 1,000번 흉내 | 몬테카를로 방법 | 무작위 표본의 평균으로 값을 추정하고 오차를 함께 낸다 |
| 기사 넷 | 하위 절차 실행 | 고른 기법대로 정렬 · 경로 · 배낭 같은 문제를 실제로 푼다 |
⚠ 비유가 맞지 않는 곳: 박 씨는 경험으로 «대충 맞는» 길을 고르지만, 그리디와 A* 는 전제가 증명될 때만 정답이고 그 전제를 따지는 일이 기법의 본체다.
4구조 — 다섯 기법의 고르는 기준
다섯 기법은 «상태를 빠짐없이 다룰 수 있나»로 먼저 나뉜다. 다룰 수 있으면 분할 정복 · 동적 계획법 · 그리디가 정확한 답을 노리고, 너무 크면 A* 가 탐색 순서를 줄이거나 몬테카를로가 표본으로 근사한다(NIST DADS heuristic).
그림 3 · 상태를 다 다룰 수 있으면 부분 문제의 겹침과 탐욕 선택 성질이 기법을 정하고, 다 볼 수 없으면 추정치나 표본으로 시간을 산다.
| 토픽 | 쓰는 조건 | 정답 | 비용을 정하는 값 | 틀어지는 꼴 |
|---|---|---|---|---|
| 분할 정복 | 부분 문제가 서로 독립 · 합치는 비용이 작음 | 보장 | 나누는 수 · 깊이 · 합침 비용 | 한쪽으로 치우친 분할 |
| 동적 계획법 | 최적 부분 구조 + 부분 문제 중복(Bellman 1954) | 보장 | 상태 수 × 상태당 선택 수 | 표가 메모리를 넘음 |
| 그리디 | 탐욕 선택 성질이 증명됨(NIST DADS greedy) | 조건부 | 정렬 · 선택 한 번씩 | 증명 없이 써서 틀린 답 |
| 휴리스틱 탐색(A*) | 목표까지 남은 비용 추정 h 가 있음 | h ≤ 실제이면 최단(Hart · Nilsson · Raphael 1968) | h 의 정확도(펼친 상태 수) | h 과대 추정 |
| 몬테카를로 방법 | 정확 계산이 불가 · 표본 생성이 쉬움 | 확률 오차 있음(NIST DADS Monte Carlo) | 표본 수 N · 오차 ∝ 1/√N | 표본 부족 · 시드 미고정 |
🔑 기법을 정하는 것은 문제의 크기가 아니라 성질이다 — 부분 문제가 겹치는지, 지금의 최선이 끝까지 최선인지가 같은 문제를 정답 보장 기법과 조건부 기법으로 가른다.
5동작 — 동전 거스름돈 한 문제를 세 기법으로
동전 1 · 4 · 6원으로 8원을 최소 개수로 만드는 문제다(설명용 가정 값). 호출 수 · 표 값은 직접 실행 값이다(Python 3.14.0 · functools.lru_cache).
- 문제를 식으로 둔다 — f(a) = a 원의 최소 개수, f(0) = 0, f(a) = 1 + min(f(a − 1), f(a − 4), f(a − 6)).
- 그리디로 푼다 — 가장 큰 6원을 먼저 쓰고 남은 2원을 1원 둘로 채워 3개다.
- 작은 입력을 전부 따져 대조한다 — 4원 + 4원 = 2개가 있어 그리디 답이 틀렸다 → 이 동전 체계에는 탐욕 선택 성질이 없다.
- 식 그대로 나눠 재귀로 푼다 — 답은 2개로 맞지만 f(8) 하나에 호출 31번, f(0) 은 10번 다시 계산된다(그림 2).
- 같은 재귀에
@lru_cache를 붙인다 —cache_info()가 hits 8 · misses 9 를 보여 계산은 9번으로 준다(Python functools). - 표로 바꿔 f(0) 부터 f(8) 까지 아래에서 위로 채운다 — 비교 16번에 [0, 1, 2, 3, 1, 2, 1, 2, 2] 가 나온다.
- f(8) 에서 되짚어 8 → 4 → 0, 답 = 4원 + 4원 2개다 — 금액을 32원으로 늘리면 그대로 재귀는 299,796번, 표는 33칸이다(그림 5).
그림 4 · 큰 동전부터 고른 그리디는 3개로 틀리고, 0원부터 채운 표를 되짚으면 4원 + 4원 2개가 나온다.
그림 5 · 겹치는 부분 문제를 저장하지 않으면 금액이 8원 늘 때마다 호출이 약 21배로 늘고, 표는 8칸씩만 는다.
🔑 동적 계획법은 분할 정복에 «기억»을 더한 것이다 — 나누는 식은 같고, 겹치는 답을 저장하느냐가 호출 수를 지수에서 금액에 비례하는 수로 바꾼다.
6비교 — 관련 기술과의 경계
| 토픽 | 맡는 일 | 경계 | 넘기는 곳 |
|---|---|---|---|
| 알고리즘 설계 기법 | 문제를 쪼개고 고르는 방법 | 특정 자료형 · 그래프에 묶이지 않은 일반 방법 | 고른 기법의 비용은 분석으로 |
| 자료구조 | 표 · 큐 · 힙 · 트리처럼 값을 담는 구조 | 동적 계획법의 표 · A* 의 우선순위 큐를 «담는» 쪽 | 구조를 쓰는 절차는 설계 기법으로 |
| 그래프 알고리즘 | 최단 경로 · MST · 탐색 같은 그래프 전용 절차 | 기법을 그래프에 적용한 결과(다익스트라 = 그리디) | 기법 자체의 조건은 설계 기법으로 |
| 알고리즘 분석(계산 복잡도) | Big-O · 점화식 풀이 · 문제 난이도 분류 | 분할 정복 점화식의 «값»을 구하는 쪽 | 개선 방법은 설계 기법으로 |
| 강화 학습(AI 쪽) | 환경과 상호작용하며 보상 최대 정책 학습 | 벨만 식 · 몬테카를로 추정을 학습에 씀 | 모델 없는 계산 절차는 설계 기법으로 |
분석«어떻게 쪼개고 무엇을 먼저 고르나»를 묻는 문제는 설계 기법에서, «그 결과가 얼마나 드나»는 알고리즘 분석에서, «그래프 위 특정 절차»는 그래프 알고리즘에서 답을 찾는다. 근거는 표의 「경계」 열 — 다익스트라는 그리디의 전제(가중치 0 이상)를 그래프에 쓴 사례다(NIST DADS greedy).
7실무 진단 — 틀림 · 느림 · 흔들림의 기법 가르기
분석먼저 작은 입력의 전수 탐색 답과 대조해 «틀림»을 가르고, 맞으면 입력 크기를 늘려 호출 · 시간이 폭증하는지 보며, 몬테카를로는 같은 시드로 다시 돌려 재현부터 확인한다. 틀림은 기법의 전제 문제라 측정보다 먼저 봐야 한다(NIST DADS greedy · 표 첫 행).
| # | 증상 | 의심 원인 | 기법 | 확인 자료 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 작은 입력에서 전수 탐색과 답이 다름 | 탐욕 선택 성질 없음 | 그리디 | 입력 10개 이하 전수 결과와 대조 | 한 건이라도 다르면 동적 계획법으로(NIST DADS greedy) |
| 2 | 입력이 조금 늘자 시간이 몇십 배 | 겹치는 부분 문제를 다시 계산 | 분할 정복 | f.cache_info() 의 hits | hits > 0 이면 겹침 → 메모 · 표로(Python functools) |
| 3 | 표를 만들다 MemoryError | 상태 수 × 칸 크기가 메모리 초과 | 동적 계획법 | 상태 수 계산 · 표 크기 | 직전 행만 필요하면 두 행만 유지 |
| 4 | A* 경로가 최단보다 김 | h 가 실제 남은 비용보다 큼 | 휴리스틱 탐색(A*) | 표본 상태의 h 와 실제 비용 비교 | h ≤ 실제 비용이어야 최단(Hart · Nilsson · Raphael 1968) |
| 5 | 추정값이 실행마다 다름 | 표본 수 부족 · 시드 미고정 | 몬테카를로 방법 | 표본 표준편차 s · N · 시드 | 오차 ≈ s/√N(NIST e-Handbook 1.3.5.2) · 같은 시드면 같은 수열(Python random) |
8시험 대비
www.q-net.or.kr시험에서는 다섯 기법의 조건 · 정답 보장 · 대표 문제를 견주는 정의 · 특징형과, 거스름돈 · 배낭 · 경로 같은 문제를 주고 어떤 기법을 왜 쓰는지 묻는 구현 · 설계형으로 나올 수 있다. 정의 · 특징형이면 그림 3 의 기준 두 개로 다섯을 나누고, 구현 · 설계형이면 그리디 반례 → 점화식 → 표 순서로 한 문제를 끝까지 푼다.
- 개요 — 설계 기법의 뜻 · 고르는 두 질문(상태를 다 다룰 수 있나 · 부분 문제가 겹치나)
- 분류 — 그림 3(분할 정복 · 동적 계획법 · 그리디 · A* · 몬테카를로)와 정답 보장 정도
- 비교 — 구조 표(쓰는 조건 · 정답 · 비용을 정하는 값 · 틀어지는 꼴)
- 적용 사례 — 그림 4 거스름돈(그리디 3개 반례 → 점화식 → 표 · 답 2개)
- 핵심 원리 — 그림 5 호출 수 비교(31 · 299,796번 대 9 · 33번) · 최적 부분 구조 · 부분 문제 중복
- 고려 사항 — 그리디 증명 · A* 의 h 조건 · 몬테카를로 오차 s/√N 과 라스베이거스 알고리즘의 차이
꼭 쓸 키워드
최적 부분 구조부분 문제 중복메모이제이션탐욕 선택 성질허용 휴리스틱평가 함수 f = g + h표본 오차라스베이거스 알고리즘
다른 답안과 차이를 내는 한 가지는 같은 문제 하나(동전 1 · 4 · 6원)로 그리디의 반례와 동적 계획법의 호출 수 감소(299,796번 → 33번)를 숫자로 함께 보이는 것이다.
9오해와 사실
- 오해거스름돈 문제는 큰 동전부터 고르면 언제나 최소다.사실동전 체계에 달렸다 — 1 · 5 · 10 · 50 · 100 · 500원 체계는 1 ~ 2,000원 전부에서 그리디 답이 최소와 같지만(직접 실행), 1 · 4 · 6원 체계는 8원에서 3개 대 2개로 틀린다.
- 오해몬테카를로는 정답을 못 내는 대충 계산이다.사실NIST 정의는 «틀릴 확률이 유계인» 무작위 알고리즘이고, 오차는 s/√N 으로 계산해 함께 낸다(NIST DADS Monte Carlo · NIST e-Handbook 1.3.5.2) — 늘 정답이고 시간만 변하는 쪽은 라스베이거스 알고리즘이다(NIST DADS Las Vegas).
- 오해휴리스틱을 쓰면 최적을 포기한 것이다.사실A* 는 남은 비용 추정이 실제를 넘지 않으면 최단 경로를 보장하고, 추정이 정확할수록 펼치는 상태만 준다(Hart · Nilsson · Raphael 1968).
10핵심 정리
| 기법 | 쪼개는 방식 | 다시 쓰는 것 | 고르는 규칙 | 정답 | 대표 문제 |
|---|---|---|---|---|---|
| 분할 정복 | 독립 부분 문제로 나눔 | 없음 | 모두 풀고 합침 | 보장 | 합병 정렬 · 퀵 정렬 |
| 동적 계획법 | 겹치는 부분 문제로 나눔 | 표 · 메모 | 모든 선택 중 최소 · 최대 | 보장 | 배낭 · 거스름돈 · 편집 거리 |
| 그리디 | 한 단계씩 | 없음 | 지금 최선 · 되돌리지 않음 | 증명될 때 | MST · 활동 선택 |
| 휴리스틱 탐색(A*) | 상태 공간 탐색 | 열린 목록(우선순위 큐) | f = g + h 최소부터 | h ≤ 실제이면 | 지도 경로 · 퍼즐 |
| 몬테카를로 방법 | 무작위 표본 N 개 | 없음 | 표본 평균 | 오차 s/√N | 적분 · 위험 추정 |
| 기법 선택 | 문제 성질 판단 | — | 겹침 · 탐욕 선택 성질 · 크기 | — | 전수 대조 · 호출 수 측정 |
11참고 문헌
- 먼저 볼 문헌
- ★ Dictionary of Algorithms and Data Structures - divide and conquer — 나눔 · 풂 · 합침 세 단계의 공공 정의를 볼 때
- ★ Dictionary of Algorithms and Data Structures - dynamic programming — 동적 계획법을 «부분 문제 답의 저장(메모이제이션)»으로 정의한 문장을 볼 때
- ★ Dictionary of Algorithms and Data Structures - Monte Carlo algorithm — 몬테카를로와 라스베이거스 알고리즘의 차이(틀릴 확률 · 실행 시간)를 볼 때
- ★ A Formal Basis for the Heuristic Determination of Minimum Cost Paths (P. E. Hart · N. J. Nilsson · B. Raphael · IEEE Transactions on Systems Science and Cybernetics SSC-4(2) · 100-107) — A* 의 평가 함수 f = g + h 와 최단 보장 조건을 볼 때
- ★ functools - Higher-order functions and operations on callable objects (Python 3.15 documentation) - lru_cache · cache_info — 메모이제이션이 실제로 몇 번 재사용됐는지(hits · misses) 재는 법을 볼 때
- 본문 근거
- Dictionary of Algorithms and Data Structures - greedy algorithm — NIST · 2005-02 ·
xlinux.nist.gov/dads/HTML/greedyalgo.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - heuristic — NIST · 2004-02 ·
xlinux.nist.gov/dads/HTML/heuristic.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - Las Vegas algorithm — NIST · 2022-07 ·
xlinux.nist.gov/dads/HTML/lasVegas.html· 확인 2026-11-14 - The Monte Carlo Method (N. Metropolis · S. Ulam · Journal of the American Statistical Association 44(247) · 335-341) — American Statistical Association · Taylor & Francis · 1949-09 ·
doi.org/10.1080/01621459.1949.10483310· 확인 2026-11-14 - The theory of dynamic programming (R. Bellman · Bulletin of the AMS 60(6) · 503-515) — American Mathematical Society · 1954-11 ·
www.ams.org/journals/bull/1954-60-06/S0002-9904-1954-09848-8/· 확인 2026-11-14 - NIST/SEMATECH e-Handbook of Statistical Methods 1.3.5.2 Confidence Limits for the Mean — NIST · 2026-11 ·
www.itl.nist.gov/div898/handbook/eda/section3/eda352.htm· 확인 2026-11-14 - random - Generate pseudo-random numbers (Python 3.15 documentation) - seed · Notes on Reproducibility — Python Software Foundation · 2026-11 ·
docs.python.org/3/library/random.html· 확인 2026-11-14