Algorithm Design Techniques

1. Overview

알고리즘 설계 기법(Algorithm Design Techniques, ADT)은 눈앞에 닥친 거대하고 막막한 컴퓨팅 문제를 컴퓨터가 소화할 수 있는 가장 작고 독립적인 연산 단위로 쪼개고, 그 조각들을 다시 지능적으로 조립하여 최적의 해답을 찾아내는 체계적인 사고의 틀(Paradigm)을 다룹니다.

데이터 구조(자료구조)가 정보를 담아두는 '물리적인 그릇'이라면, 설계 기법은 그 그릇 속 데이터를 어떻게 덜어내고 섞을지를 결정하는 '소프트웨어의 뇌'입니다. 학습자는 거대한 배열을 반씩 쪼개며 재귀적으로 들어가는 분할 정복(Divide & Conquer)의 스택 호출 역학을 분해하고, 한 번 푼 문제는 메모리에 캐싱하여 지수(Exponential) 시간의 재앙을 다항(Polynomial) 시간으로 구원해 내는 동적 계획법(Dynamic Programming, DP)의 진수를 배웁니다. 더불어 미래를 보지 않고 당장 눈앞의 최선만 좇아도 전체의 최적해에 도달하는 탐욕법(Greedy)의 수학적 성질과, 가망이 없는 경로의 싹을 조기에 잘라버리는 백트래킹(Backtracking)의 가지치기 물리량을 훈련하여 압도적인 자원 효율성을 갖춘 문제 해결사로 성장합니다.

2. Scope & Boundaries

In-Scope

• 재귀와 분할 정복 (Recursive & Divide/Conquer): 마스터 정리(Master Theorem) 기반의 재귀 깊이 분석, 병합 정렬(Merge Sort)/퀵 정렬(Quick Sort)의 파티션 알고리즘.
• 상태의 캐싱 (Dynamic Programming, DP): 메모이제이션(Memoization, Top-down)과 타뷸레이션(Tabulation, Bottom-up)의 메모리/캐시 히트 물리 차이, 최적 부분 구조(Optimal Substructure).
• 매 순간의 국소 최적해 (Greedy Algorithms): 탐욕적 선택 속성(Greedy Choice Property) 증명, 허프만 코딩(Huffman Coding) 압축 논리, 활동 선택 문제.
• 완전 탐색과 가지치기 (Search & Pruning): 상태 공간 트리(State Space Tree), DFS 기반의 백트래킹(Backtracking) 유망성(Promising) 검증, 분기 한정법(Branch & Bound).

Out-of-Scope

• 데이터 자체의 물리적 저장 구조 구현: 트리의 회전 로직(AVL)이나 해시 테이블 충돌 해결 프로그래밍 자체 → 04-02. Core Data Structures 영역으로 위임.
• 최단 경로(Dijkstra) 및 네트워크 유량 등 특정 도메인 적용: DP나 탐욕법을 이용한 구체적 그래프 탐색 최적화 알고리즘 → 04-04. Graph, String & Optimization 영역으로 위임.
• 비즈니스 도메인의 소프트웨어 아키텍처 패턴: MVC, Singleton, Factory 패턴 등 객체 지향 소프트웨어 설계 방법론 → 09. Software Engineering 영역으로 위임.

Boundaries

• ADT vs. CDS (04-02): Core Data Structures 노드가 '어떤 모양의 바구니(트리/해시)에 데이터를 담을까'에 대한 것이라면, ADT 노드는 '그 바구니에 담긴 데이터들에 어떤 수학적 조작 패턴(예: 반으로 나누기, 계산 결과 적어두기)을 가해야 정답이 나올까'라는 동적인 연산 전략에 집중합니다.

3. Counterexample

• 동적 계획법을 맹목적인 '2차원 배열 채우기'로 오해: DP 문제를 풀 때 메모리 할당의 물리적 의미를 생각하지 않고, 습관적으로 $N \times M$ 크기의 $O(N^2)$ 거대 배열부터 malloc 하고 보는 것은 안티패턴입니다. 현재 행(Row)을 계산하기 위해 바로 직전 행의 데이터만 필요하다면, 배열 크기를 $2 \times M$ 혹은 $1 \times M$으로 극단적으로 줄이는 **공간 복잡도 차원 축소(Space Optimization, Sliding Window 기법)**를 수행할 수 있어야 합니다.
• 증명 없는 탐욕법(Greedy) 적용: 특정 잔돈 거스름돈 문제에서 "그냥 가장 큰 동전부터 주면 되겠지"라고 탐욕법을 적용했다가, 화폐 단위가 배수 관계가 아닐 때(예: 120원, 100원, 50원 화폐로 150원 만들기) 오답을 내는 치명적 오류를 범하는 것. 어떤 문제에 탐욕법을 쓰려면 **'현재의 탐욕적 선택이 향후 단계의 최적성을 절대로 훼손하지 않음(Greedy Choice Property)'**을 귀류법 등으로 수학적으로 증명하는 과정을 반드시 거쳐야 합니다.

4. Prerequisites

• 이산 구조 및 복잡도 (Basic): 재귀(Recursion)가 동작할 때 메모리의 함수 콜 스택(Call Stack)이 늘어나는 개념과, 수학적 귀납법, Big-O 표기법을 완전히 숙지해야 합니다. (01-01. Discrete Structures / 04-01. Foundations)
• 핵심 자료 구조 (Recommended): 트리의 계층 구조 탐색(DFS)과 우선순위 큐(Heap)의 특성에 대한 선행 이해가 있으면 백트래킹/탐욕법 이해가 수월해집니다. (04-02. CDS)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 분할 정복의 역학 (Divide & Conquer)

• Why to Learn: 10억 개의 데이터를 한 번에 정렬하는 것은 불가능하지만, 2개씩 쪼개서 비교한 뒤 다시 합치는 방식으로는 현대 컴퓨터로 불과 몇 초 만에 처리할 수 있기 때문입니다.
• What to Learn:
  • Concepts: 분할(Divide), 정복(Conquer), 결합(Combine) 패러다임.
  • Skills: 병합 정렬(Merge Sort)의 임시 배열 결합 병목 분석, 퀵 정렬(Quick Sort)의 제자리 정렬(In-place) 파티셔닝(Partitioning) 물리.
  • Tools: 마스터 정리(Master Theorem) 계산식, 콜 스택 추적.
  • Trade-offs: 병합 정렬의 $O(N)$ 추가 메모리 할당(안정적 성능 보장) vs 퀵 정렬의 캐시 친화적 제자리 연산(하지만 피벗을 잘못 고르면 $O(N^2)$으로 추락하는 리스크).
• How to Learn:
  • 1단계: 크기 8의 배열을 병합 정렬할 때, 배열이 요소 1개가 될 때까지 분할되며 내려가는 분할 재귀 트리와, 다시 합쳐지며 정렬되는 결합 트리를 그려 각 층의 시간 비용이 $O(N)$임을 확인합니다.
  • 2단계: 퀵 정렬에서 이미 정렬된 배열을 첫 번째 원소를 피벗으로 삼아 분할했을 때 발생하는 최악의 파티셔닝(1개와 N-1개 분할) 현상을 $O(N^2)$ 공식으로 시연합니다.
• Implement: 입력 배열을 재귀적으로 반으로 쪼개고 정렬하며, 스택 깊이(Depth)가 깊어질 때마다 공백을 들여쓰기하여 실행 흐름을 터미널에 시각화하는 커스텀 Merge Sort 모듈 작성.

Recommended

Core Topic 02: 동적 계획법과 캐싱 역학 (Dynamic Programming)

• Why to Learn: 동일한 재귀 함수가 똑같은 입력값으로 수만 번 반복 호출되는 무식한 연산 폭발을 막고, 메모리(배열)를 조금 희생하여 실행 시간을 수백 배 단축하기 위해서입니다.
• What to Learn:
  • Concepts: 최적 부분 구조(Optimal Substructure), 중복되는 하위 문제(Overlapping Subproblems), Top-down(Memoization), Bottom-up(Tabulation).
  • Skills: 피보나치 수열, 배낭 문제(0/1 Knapsack), 최장 공통 부분 수열(LCS)의 2차원 점화식 도출 및 DP 배열 크기 할당 물리.
  • Tools: 점화식 전개 시트, 2차원 배열 디버거.
  • Trade-offs: Top-down 방식의 직관적인 재귀 코드 작성이 주는 개발 편의성(단, 재귀 콜 스택 오버헤드와 깊이 제한 리스크) vs Bottom-up의 순수 for문을 통한 캐시 친화성(단, 점화식 순서 설계의 난해함).
• How to Learn:
  • 1단계: 단순 재귀로 짠 $O(2^N)$ 피보나치 함수에 F(5)를 넣었을 때 F(2)가 무려 3번이나 호출되는 콜 트리의 중복을 그리고, 그 반환값을 cache[2]에 저장해 재사용하는 원리를 체득합니다.
  • 2단계: 무게 제한이 W인 배낭에 가치가 다른 물건들을 넣는 0/1 Knapsack 문제를, DP 테이블 $DP[i][w]$ (i번째 물건까지, 배낭 여유가 w일 때의 최대 가치)로 정의하고 max() 점화식을 엑셀 표의 셀을 채워가며 도출합니다.
• Implement: 2개의 문자열 간 삽입/삭제/수정 비용을 최소화하여 유사도를 판별하는 편집 거리(Levenshtein Distance) 알고리즘을 2차원 DP 테이블 기반의 C 로직으로 개발.

Practical

Core Topic 03: 탐욕적 선택과 최적화 (Greedy Algorithms)

• Why to Learn: 매 순간마다 모든 경우의 수를 비교하는 DP가 자원 낭비일 때, '지금 당장 가장 커 보이는 것'만 계속 주워 담아도 마법처럼 전체 최적해에 도달하는 우아한 효율성을 끌어내기 위함입니다.
• What to Learn:
  • Concepts: 탐욕적 선택 속성(Greedy Choice Property), 국소 최적해(Local Optimum)와 전역 최적해(Global Optimum).
  • Skills: 회의실 배정(Activity Selection Problem) 최적화 로직, 허프만 코딩(Huffman Coding)을 통한 데이터 압축 빈도 트리 생성.
  • Tools: 우선순위 큐(std::priority_queue)를 통한 탐욕 속도 $O(\log N)$ 가속화.
  • Trade-offs: 탐욕 알고리즘이 보장하는 압도적인 $O(N)$ 또는 $O(N \log N)$ 실행 속도 vs 이 방식이 해당 문제에 적합하다는 것을 입증하기 위한 매우 엄밀한 귀류법적 수학 증명의 까다로움.
• How to Learn:
  • 1단계: 시작 시간과 종료 시간이 섞인 회의 목록이 주어졌을 때, '가장 일찍 시작하는 회의'를 고르는 탐욕 vs '가장 짧은 회의'를 고르는 탐욕 vs '가장 일찍 끝나는 회의'를 고르는 탐욕 중 왜 세 번째 방식만이 예외 없는 정답인지 반례를 통해 검증합니다.
  • 2단계: 문서의 알파벳 빈도수를 기반으로, 가장 적게 나오는 글자 두 개를 반복해서 트리의 밑바닥으로 합쳐 나가는 허프만 압축 트리의 원리를 우선순위 큐 연산으로 매핑합니다.
• Implement: 거스름돈 화폐 단위 배열이 주어졌을 때, 가장 큰 단위부터 빼나가는 단순 탐욕 로직이 언제 정답을 보장(배수 관계)하고 언제 오답을 내는지 자동 판별하는 그리디 체커 알고리즘.

Advanced

Core Topic 04: 상태 공간 탐색과 가지치기 (Backtracking & Branch and Bound)

• Why to Learn: 해답이 될 수 있는 모든 콤비네이션(조합)을 전부 시도해 보되(완전 탐색), 도중에 "이 길은 백날 가봐야 정답이 나올 리 없다"고 판단되는 순간 즉시 되돌아와(Backtrack) 탐색 비용을 수십 배 감축하기 위함입니다.
• What to Learn:
  • Concepts: 상태 공간 트리(State-Space Tree), 깊이 우선 탐색(DFS), 유망성(Promising), 가지치기(Pruning), 분기 한정(Branch & Bound).
  • Skills: N-Queen 문제의 체스판 2차원 배열 공격 범위 마스킹 팁, 외판원 순회 문제(TSP)의 하한값(Lower Bound)을 통한 경로 컷오프(Cut-off) 물리.
  • Tools: 재귀 호출 스택 디버깅 툴, 노드 방문 카운터.
  • Trade-offs: 단순히 for문을 돌리는 무식한 완전 탐색($O(N!)$)의 끔찍한 소요 시간 vs 영리한 가지치기 조건문(if (!is_promising) return;) 단 한 줄을 넣음으로써 방문 노드 수를 99% 깎아내는 성능 마법.
• How to Learn:
  • 1단계: $4 \times 4$ 체스판에서 4개의 퀸을 놓는 N-Queen 트리를 그립니다. 첫 행 1열에 퀸을 둔 순간, 바로 아래 행의 1열, 2열은 공격 범위이므로 더 이상 하위 트리를 생성하지 않고 즉각 return 해버리는 가지치기의 절단면을 시각화합니다.
  • 2단계: 분기 한정법에서 BFS(너비 우선) 방식에 우선순위 큐를 섞어, 현재까지 계산된 '가장 좋은 정답(Upper Bound)'보다 이미 비용이 커져버린 경로 노드를 과감히 버리는 로직을 파악합니다.
• Implement: 스도쿠(Sudoku) 퍼즐 데이터를 2차원 배열로 입력받아 백트래킹으로 빈칸을 추론하며, 어떤 가지치기(가로/세로/3x3 검증)가 가장 탐색 스택 수를 드라마틱하게 줄이는지 측정하는 솔버 엔진.

7. Terminology

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)에서 분할 정복 패러다임이 어떻게 확장되는지 기본 원리를 인지하는가?