IT › 컴퓨터 시스템 › 알고리즘

알고리즘 설계 기법Algorithm Design Techniques

문제를 어떻게 쪼개고 무엇을 먼저 고르는가를 정하는 설계 방법 다섯(분할 정복 · 동적 계획법 · 그리디 · 휴리스틱 탐색(A*) · 몬테카를로 방법)을 묶은 알고리즘의 한 갈래다. 비용을 재는 법은 알고리즘 분석이, 그래프 전용 절차는 그래프 알고리즘이 맡는다.

1요약

  1. 알고리즘 설계 기법은 알고리즘 안에서 분할 정복 · 동적 계획법 · 그리디 · 휴리스틱 탐색(A*) · 몬테카를로 방법을 «부분 문제가 겹치나 · 고른 것을 되돌릴 일이 없나 · 정답 대신 시간을 사나» 세 질문으로 묶고, 그 위에서 정렬 · 경로 · 배낭 같은 문제별 절차가 돈다.
  2. 같은 문제라도 기법이 비용과 정답을 가른다 — 동전 1 · 4 · 6원으로 32원을 만드는 최소 개수를 그대로 재귀로 풀면 호출 299,796번, 답을 표에 적으면 33칸이면 끝나고, 큰 동전부터 고르면 8원에서 이미 틀린 답이 나온다(직접 실행 · 그림 4 · 5).
  3. 결과가 이상할 때는 틀렸나 · 느리나 · 흔들리나로 가른다 — 틀리면 그리디의 전제(탐욕 선택 성질) 위반, 입력이 조금 늘 때 폭증하면 저장 없이 겹치는 부분 문제, 실행마다 값이 바뀌면 몬테카를로의 표본 수 부족이다.

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 구간 시간 공책 한 번 잰 구간은 다시 재지 않음 동적 계획법 3 가까운 집부터 갈림길마다 지금 가장 가까운 곳 그리디 4 남은 직선거리 표지 간 거리 + 남은 거리로 길 순서 휴리스틱 탐색(A*) 5 내일을 1,000번 흉내 무작위 교통 · 날씨로 평균 시간 몬테카를로 방법 정답 — 1 · 2 늘 보장 · 3 · 4 조건이 맞을 때 · 5 오차 범위 안 나눠 풀기 적어 두고 다시 씀 고르는 규칙 거리 추정 무작위 흉내 소장이 고름

그림 1 · 소장이 배송 계획마다 고르는 다섯 방법이 곧 다섯 설계 기법이고, 방법마다 정답을 얼마나 보장하는지가 다르다.

구역 나눔넷으로 나눠 맡기고 합침
공책 적기잰 구간은 다시 안 잼
가까운 집지금 최선을 바로 고름
거리 표지남은 거리로 길 순서
1,000번 흉내무작위로 평균을 냄
비유 — 공책 없을 때 · 있을 때 실제 — 그대로 재귀 · 메모이제이션 공책 없이 2단지 구간을 경로마다 새로 잼 → 같은 구간을 5번 잼 그대로 재귀 f(2) 5번 · f(1) 7번 · f(0) 10번 f(8) 하나에 호출 31번 공책 있음 처음 1번 재고 적어 둠 → 재기 1번 + 읽기 4번 메모이제이션 f(0) ~ f(8) 한 번씩 = 계산 9번 저장값 읽기 8번(hits 8 · misses 9) 경계 — 부분 문제가 겹치면 동적 계획법, 겹치지 않으면 분할 정복 되풀이 계산 적어 둔 값 재사용 f(a) = 동전 1 · 4 · 6원으로 a 원을 만드는 최소 개수

그림 2 · 같은 구간을 여러 번 재는지가 분할 정복과 동적 계획법의 경계이고, 공책 한 권이 호출 31번을 계산 9번으로 줄인다.

비유 속 역할실제 이름실제로 하는 일
소장 박 씨설계 기법 선택문제 성질(나뉨 · 겹침 · 크기)을 보고 기법을 고른다
구역 넷 나눔분할 정복독립인 작은 문제로 나눠 풀고 답을 합친다
구간 시간 공책동적 계획법겹치는 부분 문제의 답을 표에 저장해 다시 쓴다
가까운 집부터그리디그 순간 가장 좋은 선택을 되돌리지 않고 이어 간다
남은 직선거리 표지휴리스틱 탐색(A*)f = g + h 가 작은 상태부터 펼쳐 탐색 수를 줄인다
1,000번 흉내몬테카를로 방법무작위 표본의 평균으로 값을 추정하고 오차를 함께 낸다
기사 넷하위 절차 실행고른 기법대로 정렬 · 경로 · 배낭 같은 문제를 실제로 푼다

⚠ 비유가 맞지 않는 곳: 박 씨는 경험으로 «대충 맞는» 길을 고르지만, 그리디와 A* 는 전제가 증명될 때만 정답이고 그 전제를 따지는 일이 기법의 본체다.

4구조 — 다섯 기법의 고르는 기준

다섯 기법은 «상태를 빠짐없이 다룰 수 있나»로 먼저 나뉜다. 다룰 수 있으면 분할 정복 · 동적 계획법 · 그리디가 정확한 답을 노리고, 너무 크면 A* 가 탐색 순서를 줄이거나 몬테카를로가 표본으로 근사한다(NIST DADS heuristic).

문제 — 최적값 · 경로 · 추정값 상태를 빠짐없이 다룰 수 있다 — 나눠서 정확히 상태가 너무 많다 — 추정 · 표본 분할 정복 부분 문제가 독립 나눔 → 풂 → 합침 정답 보장 예 합병 정렬 동적 계획법 부분 문제가 겹침 표에 적고 다시 씀 정답 보장 예 배낭 · 거스름돈 그리디 지금 최선이 끝까지 되돌리지 않음 증명될 때만 정답 예 크루스칼 MST 휴리스틱 탐색(A*) f = g + h 순서 h ≤ 실제 남은 비용 그때 최단 보장 예 지도 경로 몬테카를로 방법 무작위 표본 N 개 오차 ∝ 1/√N 확률적 근사 예 적분 · 위험 추정 넘김 — 담는 구조는 자료 구조 · 비용 측정은 알고리즘 분석 · 경로 절차는 그래프 알고리즘 나눠 풀기 저장 재사용 선택 규칙 남은 비용 추정 무작위 표본

그림 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).

  1. 문제를 식으로 둔다 — f(a) = a 원의 최소 개수, f(0) = 0, f(a) = 1 + min(f(a − 1), f(a − 4), f(a − 6)).
  2. 그리디로 푼다 — 가장 큰 6원을 먼저 쓰고 남은 2원을 1원 둘로 채워 3개다.
  3. 작은 입력을 전부 따져 대조한다 — 4원 + 4원 = 2개가 있어 그리디 답이 틀렸다 → 이 동전 체계에는 탐욕 선택 성질이 없다.
  4. 식 그대로 나눠 재귀로 푼다 — 답은 2개로 맞지만 f(8) 하나에 호출 31번, f(0) 은 10번 다시 계산된다(그림 2).
  5. 같은 재귀에 @lru_cache 를 붙인다 — cache_info() 가 hits 8 · misses 9 를 보여 계산은 9번으로 준다(Python functools).
  6. 표로 바꿔 f(0) 부터 f(8) 까지 아래에서 위로 채운다 — 비교 16번에 [0, 1, 2, 3, 1, 2, 1, 2, 2] 가 나온다.
  7. f(8) 에서 되짚어 8 → 4 → 0, 답 = 4원 + 4원 2개다 — 금액을 32원으로 늘리면 그대로 재귀는 299,796번, 표는 33칸이다(그림 5).
2 8원 2원 1원 0원 −6원 −1원 −1원 3개 · 최적 아님 3 전수 대조 — 4원 + 4원 = 2개 → 탐욕 선택 성질 없음 6 표 채우기 — 0원부터 위로 · 비교 16번 금액 a f(a) 0 1 2 3 4 5 6 7 8 0 1 2 3 1 2 1 2 2 4원 동전 4원 동전 7 되짚기 — 8 → 4 → 0 · 답 = 4원 + 4원 2개 답이 지나는 칸 틀린 답 굵은 테두리 = 구하려던 f(8)

그림 4 · 큰 동전부터 고른 그리디는 3개로 틀리고, 0원부터 채운 표를 되짚으면 4원 + 4원 2개가 나온다.

호출 수 · 로그 눈금 그대로 재귀 메모(계산 수) 1 10 100 1천 1만 10만 100만 금액 8원 31번 9번 금액 16원 661번 17번 금액 24원 14,085번 25번 금액 32원 299,796번 33번 +8원마다 그대로 재귀 약 21배 · 표는 금액 + 1 칸(칸마다 동전 3개 비교)

그림 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() 의 hitshits > 0 이면 겹침 → 메모 · 표로(Python functools)
3표를 만들다 MemoryError상태 수 × 칸 크기가 메모리 초과동적 계획법상태 수 계산 · 표 크기직전 행만 필요하면 두 행만 유지
4A* 경로가 최단보다 김h 가 실제 남은 비용보다 큼휴리스틱 탐색(A*)표본 상태의 h 와 실제 비용 비교h ≤ 실제 비용이어야 최단(Hart · Nilsson · Raphael 1968)
5추정값이 실행마다 다름표본 수 부족 · 시드 미고정몬테카를로 방법표본 표준편차 s · N · 시드오차 ≈ s/√N(NIST e-Handbook 1.3.5.2) · 같은 시드면 같은 수열(Python random)

8시험 대비

출제 정보 정보관리(87회, 75회)문제 원문 — 큐넷 자료실 「기출문제(기술사)」 www.q-net.or.kr

시험에서는 다섯 기법의 조건 · 정답 보장 · 대표 문제를 견주는 정의 · 특징형과, 거스름돈 · 배낭 · 경로 같은 문제를 주고 어떤 기법을 왜 쓰는지 묻는 구현 · 설계형으로 나올 수 있다. 정의 · 특징형이면 그림 3 의 기준 두 개로 다섯을 나누고, 구현 · 설계형이면 그리디 반례 → 점화식 → 표 순서로 한 문제를 끝까지 푼다.

답안 목차
  1. 개요 — 설계 기법의 뜻 · 고르는 두 질문(상태를 다 다룰 수 있나 · 부분 문제가 겹치나)
  2. 분류 — 그림 3(분할 정복 · 동적 계획법 · 그리디 · A* · 몬테카를로)와 정답 보장 정도
  3. 비교 — 구조 표(쓰는 조건 · 정답 · 비용을 정하는 값 · 틀어지는 꼴)
  4. 적용 사례 — 그림 4 거스름돈(그리디 3개 반례 → 점화식 → 표 · 답 2개)
  5. 핵심 원리 — 그림 5 호출 수 비교(31 · 299,796번 대 9 · 33번) · 최적 부분 구조 · 부분 문제 중복
  6. 고려 사항 — 그리디 증명 · 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참고 문헌

  1. 먼저 볼 문헌
  2. ★ Dictionary of Algorithms and Data Structures - divide and conquer — 나눔 · 풂 · 합침 세 단계의 공공 정의를 볼 때
    NIST · 2010-06 · xlinux.nist.gov/dads/HTML/divideAndConquer.html · 확인 2026-11-14
  3. ★ Dictionary of Algorithms and Data Structures - dynamic programming — 동적 계획법을 «부분 문제 답의 저장(메모이제이션)»으로 정의한 문장을 볼 때
    NIST · 2022-04 · xlinux.nist.gov/dads/HTML/dynamicprog.html · 확인 2026-11-14
  4. ★ Dictionary of Algorithms and Data Structures - Monte Carlo algorithm — 몬테카를로와 라스베이거스 알고리즘의 차이(틀릴 확률 · 실행 시간)를 볼 때
    NIST · 2015-05 · xlinux.nist.gov/dads/HTML/monteCarlo.html · 확인 2026-11-14
  5. ★ 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 와 최단 보장 조건을 볼 때
    IEEE · 1968-07 · doi.org/10.1109/TSSC.1968.300136 · 확인 2026-11-14
  6. ★ functools - Higher-order functions and operations on callable objects (Python 3.15 documentation) - lru_cache · cache_info — 메모이제이션이 실제로 몇 번 재사용됐는지(hits · misses) 재는 법을 볼 때
    Python Software Foundation · 2026-11 · docs.python.org/3/library/functools.html · 확인 2026-11-14
  7. 본문 근거
  8. Dictionary of Algorithms and Data Structures - greedy algorithm — NIST · 2005-02 · xlinux.nist.gov/dads/HTML/greedyalgo.html · 확인 2026-11-14
  9. Dictionary of Algorithms and Data Structures - heuristic — NIST · 2004-02 · xlinux.nist.gov/dads/HTML/heuristic.html · 확인 2026-11-14
  10. Dictionary of Algorithms and Data Structures - Las Vegas algorithm — NIST · 2022-07 · xlinux.nist.gov/dads/HTML/lasVegas.html · 확인 2026-11-14
  11. 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
  12. 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
  13. 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
  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