1단계: 알고리즘의 수학적 언어와 최적 사고법

서막: 구글은 왜 0.3초 만에 답을 찾는가

잠깐, 지금 당장 구글에 검색어를 쳐보자. 수십억 개의 웹페이지 중에서 당신이 원하는 결과를 0.3초 안에 내놓는다. 이게 단순히 "서버가 빠르기 때문"이라고 생각했다면, 오늘 그 생각이 완전히 바뀔 것이다. 서버가 아무리 빨라도, 잘못된 방법으로 찾으면 우주의 나이보다 오래 걸린다. 이것이 알고리즘을 공부하는 이유다.

컴퓨터 과학에서 알고리즘(algorithm)이란, 어떤 문제를 해결하기 위한 명확하고 유한한 절차의 집합이다. 그런데 중요한 것은, 같은 문제를 해결하는 알고리즘이 수십 가지 존재할 수 있다는 점이다. 어떤 알고리즘은 1,000개의 데이터를 처리하는 데 0.001초가 걸리고, 어떤 알고리즘은 같은 1,000개를 처리하는 데 1초가 걸린다. 그런데 데이터가 10억 개가 되면? 전자는 여전히 1초 안팎에 끝나고, 후자는 100만 초, 즉 11.5일이 걸린다. 이 차이를 수학적으로 표현하고, 예측하고, 통제하는 것이 오늘 우리가 배울 핵심이다.

1부: 이론적 기초 — 수를 세는 것에서 수학으로

알고리즘의 속도를 어떻게 측정할까

7살짜리에게 설명한다면 이렇게 말할 수 있다. "수박 1통을 자르는 데 5번 칼질하고, 10통을 자르면 50번 칼질해야 해. 칼질 횟수가 수박 개수에 비례해서 늘어나지." 이것이 선형 관계다. 그런데 어떤 요리사는 특별한 기계를 써서 수박이 100통이든 1000통이든 항상 딱 10번만 칼질해도 다 자를 수 있다고 해보자. 이것이 바로 알고리즘의 효율성 차이다.

컴퓨터가 얼마나 오래 걸리는지를 측정할 때, 실제 초(second)를 사용하지 않는다. 왜냐하면 내 컴퓨터가 느리면 같은 알고리즘도 더 오래 걸리기 때문이다. 대신 우리는 연산(operation)의 횟수를 센다. 정확히는, 입력 데이터의 크기 n이 커질수록 연산 횟수가 어떤 함수 꼴로 증가하는지를 본다. 이 아이디어를 수학적으로 정식화한 것이 바로 점근적 분석(asymptotic analysis)이고, 그 대표적 표기법이 빅-오(Big-O) 표기법이다.

[노트 기록] 점근적 분석(Asymptotic Analysis): 입력 n이 충분히 클 때의 함수 증가 속도를 비교하는 수학적 방법론. 상수나 하위 차수 항은 무시하고, 가장 지배적인 항만 남긴다.

수학적 정의: 빅-오는 무엇인가

이제 중학교 수준의 수학으로 올라가보자. 우리가 어떤 알고리즘의 연산 횟수를 세었더니 $f (n) = 3 n^{2} + 7 n + 100$ 이었다고 하자. n이 100만이면 $3 n^{2}$ 는 $3 \times 1 0^{12}$ 인데, $7 n$ 은 고작 $7 \times 1 0^{6}$ 이고 100은 거의 0에 가깝다. 즉, n이 커질수록 $n^{2}$ 항이 나머지를 압도한다. 그러니 우리는 이 알고리즘을 $O (n^{2})$ 이라고 부른다.

형식적으로, Donald Knuth가 체계화한 정의는 다음과 같다: $f (n) = O (g (n))$ 이라 함은, 충분히 큰 모든 n에 대해 $f (n) \leq c \cdot g (n)$ 을 만족하는 양의 상수 $c$ 와 $n_{0}$ 가 존재한다는 뜻이다 (The Art of Computer Programming, Knuth, 1997). 고등학교 수준에서 말하자면: g(n)이 f(n)의 성장 속도의 '상한선'이 된다는 것이다.

[노트 기록] Big-O 정의: $f (n) = O (g (n))$ ⟺ ∃c > 0, n₀ > 0 s.t. ∀n ≥ n₀, f(n) ≤ c·g(n). 직관: f가 g보다 빠르게 커지지 않는다.

이와 함께 자주 쓰이는 표기가 두 가지 더 있다. 빅-오메가(Big-Ω): f의 성장 속도의 하한선. "아무리 잘 돼도 이것보다 느리지 않다", 즉 최선의 경우. 빅-세타(Big-Θ): 상한과 하한이 같은 경우, 즉 정확한 성장 차수. 예를 들어 버블 정렬은 항상 $O (n^{2})$ 이고 $Ω (n)$ 이지만, $Θ (n^{2})$ 이다(평균적으로 $n^{2}$ 에 수렴).

흔히 보는 복잡도 함수들, 머릿속에 새기기

이제 실제로 중요한 복잡도 함수들을 감각적으로 이해해보자. 데이터 n = 1,000,000(100만)일 때 각각 얼마나 되는지 생각해보면 확 와닿는다.

$O (1)$ — 상수 시간: n이 아무리 커져도 연산이 딱 한 번, 혹은 일정 횟수만 일어난다. 배열의 i번째 원소에 접근하는 것이 대표적이다. n = 100만이든 100억이든, arr[5]는 한 번의 메모리 접근이다. $O (lo g n)$ — 로그 시간: n이 두 배가 될 때마다 연산이 딱 한 번만 늘어난다. n = 100만이면 $lo g_{2} 1 0^{6} \approx 20$ 번이다. 이진 탐색(binary search)이 대표적이다. 100만 개 정렬된 배열에서 원하는 값을 단 20번의 비교로 찾는다.

$O (n)$ — 선형 시간: 데이터를 한 번씩만 훑는다. n = 100만이면 100만 번. $O (n lo g n)$ — 선형 로그 시간: n = 100만이면 약 2,000만 번. 병합 정렬(merge sort), 힙 정렬(heap sort)이 여기 속하며, 비교 기반 정렬의 이론적 하한이 $Ω (n lo g n)$ 임이 증명되어 있다 (Introduction to Algorithms, Cormen et al., CLRS, 2009). $O (n^{2})$ — 이차 시간: n = 100만이면 $1 0^{12}$ 번, 즉 1조 번. 버블 정렬, 선택 정렬. $O (2^{n})$ — 지수 시간: n = 50만 되어도 $2^{50} \approx 1 0^{15}$ 번, 사실상 불가능.

[노트 기록] 복잡도 차수 순서: $O (1) < O (lo g n) < O (n) < O (n lo g n) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!)$

공간 복잡도: 메모리도 비용이다

학습 목표 ②인 "최소한의 자원으로 최대한의 데이터를 다룬다"는 시간만의 문제가 아니다. **공간 복잡도(space complexity)**는 알고리즘이 실행될 때 사용하는 추가 메모리의 양이다. 예를 들어, 어떤 정렬 알고리즘은 입력 배열 외에 n개짜리 보조 배열이 필요하면 $O (n)$ 의 추가 공간을 쓰는 것이고, 제자리(in-place)에서 정렬하면 $O (1)$ 의 추가 공간을 쓴다.

흔히 **시간-공간 트레이드오프(time-space tradeoff)**라는 말을 쓴다. 메모리를 더 쓰면 속도를 높일 수 있고, 메모리를 아끼면 느려질 수 있다. 뒤에서 배울 동적 계획법이 바로 이 트레이드오프의 교과서적 예시다. "이전에 계산한 결과를 메모리에 저장해두면, 같은 계산을 다시 하지 않아도 된다."

2부: 본 내용 — 비선형의 세계로

선형 자료구조의 한계

지금까지 배열(array), 연결 리스트(linked list)처럼 데이터가 순서대로 늘어선 선형 자료구조를 알고 있을 것이다. 이들은 직관적이지만 치명적인 약점이 있다. 예를 들어 정렬되지 않은 배열에서 특정 값을 찾으려면 최악의 경우 모든 원소를 다 봐야 하므로 $O (n)$ 이 걸린다. 그렇다면 계층 구조(예: 회사 조직도), 네트워크 연결(예: 도시 간 도로), 우선순위가 있는 데이터(예: 응급실 환자) 같은 복잡한 관계를 표현하기엔 턱없이 부족하다. 이 한계를 극복하기 위해 등장한 것이 비선형 자료구조다.

트리(Tree): 계층 관계를 담는 그릇

트리는 **노드(node)**와 **간선(edge)**으로 이루어진 계층적 자료구조다. 뿌리(root) 노드 하나에서 시작해 아래로 뻗어나가는 형태다. 부모(parent), 자식(child), 형제(sibling), 잎(leaf, 자식이 없는 노드), 깊이(depth, 루트에서 해당 노드까지의 간선 수), 높이(height, 가장 깊은 잎까지의 깊이) 등의 개념을 정확히 이해해야 한다.

**이진 탐색 트리(BST, Binary Search Tree)**는 트리의 가장 중요한 기본 형태다. 각 노드가 최대 두 자식을 가지고, 왼쪽 서브트리의 모든 값 < 현재 노드 < 오른쪽 서브트리의 모든 값이라는 불변식(invariant)을 유지한다. 이 구조 덕분에 탐색, 삽입, 삭제가 모두 **평균 $O (lo g n)$ **에 가능하다. 이진 탐색에서 절반씩 줄여나가는 논리와 동일하다.

그런데 여기서 결정적인 문제가 생긴다. 만약 1, 2, 3, 4, 5를 순서대로 삽입하면 BST는 오른쪽으로 쭉 늘어진 **편향 트리(skewed tree)**가 된다. 이러면 탐색이 $O (n)$ 으로 퇴화한다. 이것을 막기 위해 **자가 균형 BST(Self-Balancing BST)**가 필요하다. AVL 트리는 모든 노드에서 왼쪽/오른쪽 서브트리의 높이 차이를 1 이하로 유지하기 위해 회전(rotation) 연산을 쓰며, 레드-블랙 트리는 색깔 속성으로 균형을 보장한다. 이 둘 모두 삽입/삭제/탐색이 항상 $O (lo g n)$ 을 보장한다.

[노트 기록] BST 핵심 성질: 왼쪽 서브트리 < 루트 < 오른쪽 서브트리. 균형이 깨지면 $O (lo g n)$ 이 $O (n)$ 으로 퇴화한다. 자가 균형 트리가 이를 방지.

**힙(Heap)**은 또 다른 중요한 트리 구조다. 완전 이진 트리(complete binary tree, 마지막 레벨을 제외한 모든 레벨이 꽉 차고, 마지막 레벨은 왼쪽부터 채워지는 트리) 형태이면서, **최대 힙(max-heap)**은 모든 부모 노드가 자식보다 크거나 같다는 성질을 유지한다. 이 덕분에 항상 최댓값(또는 최솟값)을 $O (1)$ 에 조회하고, 삽입과 삭제(최댓값 제거)가 $O (lo g n)$ 에 가능하다. 힙은 우선순위 큐(Priority Queue)의 구현체이자, 힙 정렬의 핵심이다.

그래프(Graph): 관계의 수학

트리는 사실 그래프의 특수한 경우다. **그래프 G = (V, E)**는 꼭짓점(vertex, 또는 노드)의 집합 V와 간선(edge)의 집합 E로 정의된다. 간선이 방향을 가지면 유향 그래프(directed graph, digraph), 가지지 않으면 **무향 그래프(undirected graph)**다. 간선에 비용(거리, 시간 등)이 있으면 **가중 그래프(weighted graph)**다.

그래프를 컴퓨터에 저장하는 방법은 두 가지가 있다. 인접 행렬(adjacency matrix): V×V 크기의 2차원 배열. 두 노드 사이의 연결 여부를 $O (1)$ 에 확인할 수 있지만, 노드가 많고 간선이 적을 때 메모리를 낭비한다( $O (V^{2})$ 공간). 인접 리스트(adjacency list): 각 노드마다 그 노드와 연결된 노드들의 목록을 저장. 공간이 $O (V + E)$ 로 효율적이지만 두 노드의 연결 여부 확인이 $O (degree)$ 가 걸릴 수 있다.

그래프를 탐색하는 기본 알고리즘 두 가지를 반드시 이해해야 한다. **BFS(Breadth-First Search, 너비 우선 탐색)**는 시작 노드에서 가까운 노드부터 차례로 방문한다. **큐(Queue)**를 사용하며, **최단 경로(unweighted)**를 찾는 데 쓰인다. **DFS(Depth-First Search, 깊이 우선 탐색)**는 한 방향으로 끝까지 파고들다가 막히면 되돌아온다. 스택(Stack) 또는 재귀(recursion)를 사용하며, 연결 요소 탐색, 위상 정렬, 사이클 감지 등에 쓰인다. 둘 다 시간 복잡도는 $O (V + E)$ 다.

[노트 기록] BFS → 큐 → 최단 경로(비가중). DFS → 스택/재귀 → 순회/사이클/위상정렬. 복잡도 $O (V + E)$ .

최단 경로 알고리즘이야말로 학습 목표 ①과 ③의 교차점이다. 다익스트라(Dijkstra) 알고리즘은 가중치가 모두 양수인 그래프에서 단일 출발점의 최단 경로를 찾는다. 핵심 아이디어는 "현재까지 발견된 가장 짧은 경로의 노드를 먼저 방문한다"는 탐욕적 선택이다. 우선순위 큐(힙)를 쓰면 $O ((V + E) lo g V)$ 에 동작한다. 벨만-포드(Bellman-Ford) 알고리즘은 음의 가중치도 처리하며 $O (V E)$ 다. 도시 간 물류 경로, 내비게이션 시스템이 모두 이 위에 세워져 있다.

3부: 동적 계획법(DP) — 기억이 곧 속도다

재귀의 비효율성에서 출발하기

피보나치 수열을 아는가? $F (1) = 1, F (2) = 1, F (n) = F (n - 1) + F (n - 2)$ . 재귀로 구현하면 직관적이지만, F(50)을 계산하려면 F(49) + F(48)이 필요하고, F(49)를 계산하려면 F(48) + F(47)이 필요하다. F(48)이 두 번 계산된다. F(47)은 몇 번? 거슬러 올라가면 계산 횟수가 $O (2^{n})$ 에 달한다. n = 50이면 약 $1 0^{15}$ 번, 우주가 끝날 때까지 계산해도 모자란다.

핵심을 꿰뚫는 질문을 던져보자: "이미 계산한 것을 왜 다시 계산하는가?" 이 질문에 대한 답이 동적 계획법(Dynamic Programming, DP)이다. 리처드 벨만(Richard Bellman)이 1950년대에 고안한 이 방법론의 핵심은 두 가지 성질에 있다(Dynamic Programming, Bellman, 1957).

첫째, 최적 부분 구조(Optimal Substructure): 전체 문제의 최적해가 부분 문제들의 최적해로 구성된다. 즉, F(n)의 최적해는 F(n-1)과 F(n-2)의 최적해로 구성된다. 둘째, 중복 부분 문제(Overlapping Subproblems): 같은 부분 문제가 여러 번 등장한다. F(48)이 F(50)과 F(49) 양쪽에서 필요한 것처럼.

[노트 기록] DP 적용 조건: ① 최적 부분 구조 + ② 중복 부분 문제. 이 두 성질이 없으면 DP가 아닌 다른 방법을 써야 한다.

메모이제이션 vs 타뷸레이션

DP를 구현하는 방식이 두 가지다. 메모이제이션(Memoization, 하향식 Top-Down): 재귀를 그대로 쓰되, 한 번 계산한 결과를 **캐시(cache, 보통 배열이나 해시맵)**에 저장해둔다. 이미 계산된 것이라면 캐시에서 즉시 꺼낸다. 타뷸레이션(Tabulation, 상향식 Bottom-Up): 가장 작은 부분 문제부터 차례로 계산해서 테이블을 채워 올라간다. 재귀 없이 반복문으로 구현한다.

피보나치의 경우, 메모이제이션은 memo[n]이 있으면 바로 반환, 없으면 계산 후 저장. 타뷸레이션은 dp[1]=1, dp[2]=1, dp[i]=dp[i-1]+dp[i-2]를 i=3부터 n까지 반복. 둘 다 시간 복잡도 $O (n)$ , 공간 복잡도 $O (n)$ 으로, 순진한 재귀의 $O (2^{n})$ 과 비교하면 혁명적인 차이다.

더 중요한 예시는 **0/1 배낭 문제(0/1 Knapsack Problem)**다. n개의 물건이 있고 각 물건에 무게 $w_{i}$ 와 가치 $v_{i}$ 가 있다. 최대 용량 W인 배낭에 총 가치가 최대가 되도록 물건을 담아야 한다. 물건은 통째로 담거나 안 담거나(0/1)만 가능하다. 이 문제에서 dp[i][j]를 "i번째 물건까지 고려했을 때, 무게 제한이 j일 경우의 최대 가치"로 정의하면, 점화식은 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])가 된다. 이 $O (nW)$ 알고리즘이 무차별 탐색(brute force)의 $O (2^{n})$ 을 어떻게 넘어서는지 반드시 스스로 추적해봐야 한다.

4부: 그리디 알고리즘 — 지금 당장 최선을 선택하라

언제 욕심을 부려도 되는가

DP가 "모든 경우의 수를 메모리에 저장하며 최적해를 탐색"한다면, **그리디 알고리즘(Greedy Algorithm)**은 매 단계에서 현재 기준으로 가장 좋아 보이는 선택을 하고 뒤를 돌아보지 않는다. 직관적이고 빠르지만, 언제나 옳은 것은 아니다. 그리디가 최적해를 보장하려면 특별한 조건이 필요하다.

대표적인 예가 거스름돈 문제다. 500원, 100원, 50원, 10원짜리 동전으로 860원을 거슬러줄 때, 가장 큰 단위부터 최대한 쓰는 전략은 최적이다. 그런데 만약 동전이 1원, 3원, 4원짜리뿐이고 6원을 거슬러야 한다면? 그리디는 4원+1원+1원 = 3개를 선택하지만, 최적은 3원+3원 = 2개다. 그리디는 항상 옳지 않다.

그리디가 항상 최적임을 보이는 표준적인 방법이 **교환 논증(Exchange Argument)**이다. 핵심 아이디어: "그리디의 선택과 다른 최적해가 있다고 가정하자. 그 최적해에서 그리디의 선택으로 바꿔도 해의 품질이 나빠지지 않음을 보이면, 그리디가 곧 최적해다." 이 논증을 **활동 선택 문제(Activity Selection Problem)**에 적용하면, 종료 시간이 가장 빠른 활동을 먼저 선택하는 그리디가 최대한 많은 활동을 선택하는 최적해임을 증명할 수 있다(Algorithm Design, Kleinberg & Tardos, 2005).

[노트 기록] 그리디 최적 조건: ① 그리디 선택 속성(Greedy Choice Property): 지역 최적 선택이 전역 최적을 방해하지 않는다. ② 최적 부분 구조(DP와 공통). DP가 필요 없는 문제는 그리디로 더 빠르게 풀 수 있다.

DP와 그리디의 관계를 꼭 기억하자. 배낭 문제에서 물건을 쪼갤 수 있는 **분수 배낭 문제(Fractional Knapsack)**는 그리디(단위 무게당 가치 순 정렬)로 최적해를 구할 수 있지만, 0/1 배낭 문제는 DP가 필요하다. 같은 문제 구조도 제약 조건 하나의 차이로 그리디가 통하는가 아닌가가 갈린다.

5부: 모든 것을 연결하기 — 최적 알고리즘 설계의 사고 흐름

지금까지 배운 것들이 학습 목표 세 가지와 어떻게 연결되는지 정리해보자. **목표 ①(처리 속도 보장)**은 Big-O 분석으로 알고리즘을 선택하는 능력이다. 어떤 알고리즘이 $O (n^{2})$ 인지 $O (n lo g n)$ 인지 알아야 데이터가 100만이든 1억이든 예측 가능한 성능을 낼 수 있다. **목표 ②(최소 자원, 최대 데이터)**는 공간 복잡도와 자료구조 선택이다. 같은 $O (n lo g n)$ 정렬이라도 제자리 정렬이냐 아니냐에 따라 메모리 사용이 다르다. 트리 구조를 인접 행렬로 저장하느냐 인접 리스트로 저장하느냐에 따라 메모리가 $O (n^{2})$ 과 $O (n)$ 으로 갈린다. **목표 ③(최적 의사결정)**은 DP와 그리디의 영역이다. 어떤 문제에 어떤 도구를 쓸지 판단하는 것 자체가 알고리즘 설계의 핵심이다.

실무 현장에서, 예컨대 물류 이동 경로 최적화 시스템은 도시를 그래프의 노드로, 도로를 가중 간선으로 모델링하고, 다익스트라 또는 A* 알고리즘으로 최단 경로를 구하며, 이 결과를 캐시에 저장해 중복 계산을 줄이는 DP적 사고를 결합한다. 빅-오가 보장하는 성능 예측 없이는 이 시스템을 프로덕션 환경에 배포할 수 없다. 이것이 이론과 실무가 맞닿는 지점이다.

프로젝트 파트: 예제 문제 (정답 없음 — 40분 내외)

스스로 풀어보는 것이 전부다. 막힌다고 포기하지 말고, 무엇이 막히는지 정확히 파악하는 것 자체가 학습이다.

문제 1: 복잡도 분석 훈련 (약 8분)

아래 세 개의 코드 조각(의사 코드)의 시간 복잡도와 공간 복잡도를 각각 Big-O로 분석하라. 분석 과정을 단계별로 보여야 한다(핵심 연산이 몇 번 반복되는지 직접 세어보라).

(A)
for i in range(n):
    for j in range(n):
        if arr[i] > arr[j]:
            swap(arr, i, j)

(B)
def mystery(n):
    if n <= 1:
        return 1
    return mystery(n // 2) + mystery(n // 2) + 1

(C)
memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

(B)는 특히 주목하라. 재귀 트리를 그려가며 각 레벨에서 몇 번의 연산이 일어나는지 세어보면, 전체 복잡도가 보일 것이다.)

문제 2: 트리 탐색과 BFS/DFS 응용 (약 10분)

아래와 같은 이진 트리가 있다. 루트는 4다.

(가) 이 트리를 BFS로 탐색했을 때 방문 순서를 기술하라. 또한 BFS 탐색에 사용된 큐(queue)의 상태를 각 단계별로 추적하라.

(나) 이 트리를 DFS(in-order, 중위 순회)로 탐색했을 때 방문 순서를 기술하라. 이진 탐색 트리에서 중위 순회의 결과가 항상 정렬된 순서가 되는 이유를, BST의 불변식을 이용해 논리적으로 설명하라.

(다) 새로운 값 3.5를 이 BST에 삽입하려 한다. 삽입 과정을 노드 비교 순서대로 기술하고, 삽입 후 트리의 구조를 그려라.

문제 3: 동적 계획법 — 최장 공통 부분수열 (약 12분)

두 문자열 X = "ABCBDAB", Y = "BDCAB"가 있다. **최장 공통 부분수열(LCS, Longest Common Subsequence)**의 길이를 DP로 구하라. LCS란 두 문자열에서 순서는 유지하되 연속될 필요는 없는 공통 부분수열 중 가장 긴 것이다. (예: "AB"는 X와 Y 모두의 부분수열이다.)

(가) dp[i][j]를 "X의 처음 i글자와 Y의 처음 j글자의 LCS 길이"로 정의할 때, 점화식을 직접 유도하라. 힌트: X[i] == Y[j]일 때와 아닐 때 두 경우를 나누어 생각하라.

(나) 유도한 점화식을 바탕으로 dp 테이블(8×6 크기)을 직접 채워라. 테이블의 각 칸이 왜 그 값인지 두 칸 이상 직접 설명하라.

(다) 이 알고리즘의 시간 복잡도와 공간 복잡도는 무엇인가? 순진한 재귀(메모이제이션 없이)로 풀었을 때의 복잡도와 비교하라.

문제 4: 그리디 vs DP — 판단력 기르기 (약 10분)

아래 세 가지 상황을 보고, 각각 그리디로 최적해를 구할 수 있는지, 아니면 DP가 필요한지 판단하고 그 이유를 논리적으로 서술하라. 단순히 "맞다/아니다"가 아니라, 그리디 선택 속성이 성립하는지 아닌지를 기준으로 설명해야 한다.

(가) 1원, 5원, 10원, 50원짜리 동전이 있다. 어떤 금액을 최소한의 동전 개수로 거슬러줘야 한다.

(나) 1원, 3원, 4원짜리 동전이 있다. 어떤 금액을 최소한의 동전 개수로 거슬러줘야 한다.

(다) n개의 작업이 있고 각각 마감시간(deadline)과 이익(profit)이 있다. 한 번에 하나의 작업만 할 수 있고 각 작업은 1시간이 걸린다. 마감 내에 완료된 작업의 총 이익을 최대화하라.

통합 심화 문제: 다익스트라 직접 추적 (약 10분)

아래 가중 그래프에서 노드 A를 출발점으로 모든 노드까지의 최단 거리를 다익스트라 알고리즘으로 구하라.

A --4-- B
|       |
2       3
|       |
C --1-- D --5-- E
 \             /
  6-----------

간선: A-B(4), A-C(2), B-D(3), C-D(1), C-E(6), D-E(5)

(가) 다익스트라 알고리즘의 각 단계를 표로 기록하라. 각 단계에서 ① 방문된 노드, ② 우선순위 큐의 상태, ③ 각 노드까지의 현재 최단 거리 추정값을 보여야 한다.

(나) A에서 E까지의 최단 경로와 그 거리를 구하라.

(다) 만약 간선 C-E의 가중치가 음수(-1)가 된다면 다익스트라 알고리즘은 여전히 올바른 답을 내는가? 그 이유를 다익스트라 알고리즘의 핵심 전제와 연결해 설명하라.

[이 문제들을 다 풀고 나면, 알고리즘 설계의 세 가지 기둥—분석, 구조, 최적화—이 자신의 뇌 안에서 하나의 언어로 통합되기 시작할 것이다. 그것이 오늘의 진짜 목표다.]

알고리즘 및 고급 자료구조