Algorithm Design Techniques

1. Overview

알고리즘 설계 기법(Algorithm Design Techniques, ADT)은 복잡한 문제를 풀 수 있는 작은 단위로 분해하고 최적의 해답을 찾아가는 체계적인 전략들을 다룹니다.

자료 구조가 '데이터의 상태'라면, 설계 기법은 '데이터를 다루는 지능'입니다. 학습자는 분할 정복(Divide & Conquer)을 통해 문제의 규모를 줄이고, 동적 계획법(DP)으로 중복 연산을 제거하며, 탐욕법(Greedy)을 통해 매 순간의 최선을 선택하는 물리적/논리적 방법론을 학습합니다. 이를 통해 단순히 정답을 내는 것을 넘어 자원 효율성이 극대화된 최적해(Optimal Solution)를 도출합니다.

2. Scope & Boundaries

In-Scope

Recursive Strategies: 분할 정복(Divide & Conquer)의 기본 원리와 재귀 호출의 물리적 스택 거동
Optimization Paradigms: 동적 계획법(DP)의 메모이제이션(Memoization) vs 타뷸레이션(Tabulation)
Heuristic Choices: 탐욕 알고리즘(Greedy)의 최적 부분 구조(Optimal Substructure) 증명
Search & Pruning: 백트래킹(Backtracking)과 분기 한정(Branch & Bound)을 통한 상태 공간 탐색

Out-of-Scope

선형 계획법(Linear Programming) 등 순수 수치 해석 연산 (01. Mathematics 영역으로 위임)
특정 비즈니스 로직 최적화 (09. Software Engineering 영역으로 위임)

Boundaries

Technique vs. Graph: 본 노드는 '사고하는 틀' 자체에 집중하며, 이 틀을 그래프라는 데이터 구조에 적용한 구체적인 사례는 04-04(Graph, String & Optimization) 노드로 분리합니다.

3. Counterexample

단순히 재귀 함수를 만드는 것은 ADT 학습이 아닙니다. 재귀 호출 시 발생하는 스택 오버헤드를 줄이기 위해 어떻게 **미리 계산된 값(Lookup Table)**을 활용할지, 그리고 특정 문제가 탐욕법으로 풀었을 때 **전역 최적해(Global Optimum)**를 보장하는지 수학적으로 증명할 수 있어야 합니다.

4. Prerequisites

이산 구조 및 모델링 (Recommended): 점화식(Recurrence relation)과 수학적 귀납법 증명 이해가 필요합니다. (01. Discrete Structures)
기초 및 복잡도 (Basic): 마스터 정리(Master Theorem)를 통한 재귀 식의 복잡도 분석 능력이 필수입니다. (04. Foundations)

5. Learning Map

Splitting Problems: 문제를 독립적인 하위 문제로 나누는 분할 정복의 논리를 익힙니다.
Reusing Results: 하위 문제의 중복을 발견하고 결과값을 저장하는 DP 메커니즘을 이해합니다.
Local to Global: 매 단계의 선택이 최종 결과에 미치는 영향(탐욕 속성)을 분석합니다.
Pruning the Tree: 불필요한 탐색 경로를 조기에 차단하는 백트래킹 기법을 배웁니다.

6. Learning Topics

Basic

Core: 분할 정복과 재귀 (Divide & Conquer)

Why to Learn: 대규모 문제를 동일한 유형의 작은 문제로 치환하여 해결 효율을 높이기 위함입니다.
What to Learn:
- Divide(분리), Conquer(정복), Combine(결합) 3단계 프로세스
- 주요 사례: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색
- 재귀 호출의 깊이(Depth)와 스택 메모리 한계 인지
How to Learn:
- 병합 정렬 과정을 수기 트라이(Tree)로 그려보며 결합 오버헤드 분석
- 재귀를 반복문(Iterative)으로 변환했을 때의 메모리 이득 실습
Implement: 퀵 정렬의 피벗(Pivot) 선택 전략에 따른 최악의 경우 시뮬레이터

Why to Learn: 동일한 계산을 반복하지 않도록 하여 지수 시간 복잡도를 다항 시간으로 줄이기 위해서입니다.
What to Learn:
- Top-down (Memoization) vs Bottom-up (Tabulation) 물리 구현 방식
- 최적 부분 구조(Optimal Substructure)와 중복 하위 문제(Overlapping Subproblems) 판별
- 0/1 배낭 문제(Knapsack)를 통한 차원 축소 공간 최적화
How to Learn:
- 피보나치 수열을 단순 재귀, 메모이제이션, 타뷸레이션으로 구현하여 실행 속도 비교
- DP 테이블 채우기 과정을 엑셀이나 수기로 가시화하여 점화식 유도 연습
Implement: 두 문자열의 유사도를 측정하는 편집 거리(Edit Distance) 최적화 알고리즘

Practical

Core: 탐욕적 선택과 증명 (Greedy Algorithms)

Why to Learn: 모든 가능성을 검토할 수 없는 상황에서 충분히 좋은 해를 빠르게 찾기 위함입니다.
What to Learn:
- Greedy Choice Property(탐욕적 선택 속성)의 물리적 정의
- 활동 선택 문제(Activity Selection)와 허프만 코딩(Huffman Coding) 논리
- 탐욕법이 실패하는 사례(예: 거스름돈 문제의 특정 화폐 단위) 분석
How to Learn:
- 반례(Counter-example)를 찾아보며 특정 알고리즘의 정당성 검증 연습
- 우선순위 큐(Priority Queue)를 활용한 탐욕적 선택 가속화 실습
Implement: 허프만 압축을 이용한 기초 텍스트 인코딩/디코딩 모듈

Advanced

Core: 상태 공간 탐색과 가지치기 (Backtracking & Pruning)

Why to Learn: 정답이 될 가능성이 없는 경로를 미리 제거하여 탐색 성능을 극대화하기 위해서입니다.
What to Learn:
- DFS(깊이 우선 탐색) 기반의 유망성(Promising) 판단 메커니즘
- N-Queen 문제 등을 통한 백트래킹 전개 과정의 시각화
- 하한값(Lower Bound)을 이용한 분기 한정(Branch & Bound) 최적화 기초
How to Learn:
- 탐색 트리에서 '가지치기(Pruning)'가 일어나는 시점을 로그로 출력하여 확인
- 단순 DFS 대비 백트래킹의 방문 노드 수 감소량 정량 분석
Implement: 스도쿠(Sudoku)나 퍼즐 해결을 위한 효율적인 백트래킹 엔진

7. Terminology

Term (EN / ko, abbr)	1문장 정의	단계(기본/권장/실무/심화)	역할/맥락	관련 개념	유사/대비/함께 사용	오해 포인트	Evidence(Primary/Secondary/Industry)	Flags(core/misused/legacy)
Optimal Substructure	큰 문제의 최적해가 그 하위 문제들의 최적해들로부터 구성될 수 있는 성질입니다.	추천	정당성 증명	DP / Greedy	Sub-problem	단순히 '문제가 작아짐'과 혼동	P1:CS2023/Fundamental	core
Memoization	재귀 함숫값을 저장해두었다가 재활용하여 중복 계산을 피하는 기법입니다.	기본	성능 최적화	Top-down	Tabulation	단순히 'Caching' 일반과 혼동	P1:CS2023/Fundamental	core
Pruning (가지치기)	탐색 과정에서 해답이 될 가능성이 없는 하위 트리를 더 이상 탐색하지 않는 행위입니다.	실무	탐색 효율화	Backtracking	DFS	전체 탐색(Brute force)과 대조	P1:CS2023/Fundamental	core
Divide & Conquer	문제를 서로 겹치지 않는 하위 문제로 분할하고 각각을 해결한 뒤 결합하는 패러다임입니다.	기본	문제 해결	Recursion	DP	DP와 겹치는 부분이 있다고 오해	P1:CS2023/Fundamental	core

8. References

Primary References

[P1] CS2023 - AL/Algorithmic Strategies — Design paradigms.
[P2] SWEBOK - Computing Foundations — Logic and algorithmic problem solving.

Secondary References

[Algorithm Design] Jon Kleinberg & Éva Tardos — Focus on proof and modeling.
[The Algorithm Design Manual] Steven Skiena — Practical "War Stories" context.

Industry References

[TopCoder Statistics - Educational Content] — Competitive programming patterns.
[Google Interview Preparation Guide] — Core algorithmic strategies.

9. Final Checklist

Primary Checklist

특정 문제에 대해 분할 정복과 동적 계획법 중 어떤 방식이 물리적 중복 계산을 더 잘 효과적으로 줄이는지 판단 가능한가? (P1)
동적 계획법의 '점화식'을 유도하고 이를 메모이제이션 코드로 변환할 수 있는가? (P1)

Secondary Checklist

재귀 알고리즘 설계 시 기저 조건(Base Case) 부재로 인한 무한 루프나 스택 오버플로우 리스크를 예측하는가?
탐욕법을 적용하기 전 '탐욕적 선택'이 이후 단계의 최적성을 해치지 않음을 증명할 수 있는가?

Industry Checklist

코딩 테스트 수준을 넘어 실무 대규모 데이터 필터링 시 백트래킹을 통한 시간 단축 효과를 시뮬레이션 가능한가? (SFIA)
분산 처리 환경(MapReduce)에서 분할 정복 패러다임이 어떻게 확장되는지 기본 원리를 인지하는가?