트리와 그래프: 관계를 표현하는 구조
한 줄로 늘어선 데이터를 넘어, 갈라지고 이어진 데이터를 다뤄요. 폴더 크기를 계산하며 전위 순회와 후위 순회를 익히고, 이진 탐색 트리를 만들어 넣는 순서에 따라 높이가 24와 2,000으로 갈리는 모습을 확인해요. 급한 일부터 꺼내는 힙과 우선순위 큐, 거치는 곳이 가장 적은 길을 찾는 너비 우선 탐색과 길 복원, 시간이 가장 짧은 길을 찾는 다익스트라, 격자 미로 찾기, 순환까지 잡아내는 위상 정렬을 직접 구현해요.
지금까지 다룬 구조는 모두 한 줄로 늘어선 데이터였어요. 그런데 폴더 안의 폴더, 회사의 조직도, 지하철 노선도, 친구의 친구처럼 세상의 많은 데이터는 갈라지고 이어져요. 이런 관계는 트리와 그래프로 표현해요. 수학 기초 트랙의 그래프 강의에서 용어와 너비 우선 탐색, 깊이 우선 탐색의 기본 코드를 봤으니, 이번에는 그 위에서 실제로 쓰는 구조와 알고리즘을 직접 만들어 봐요.
트리 순회: 폴더 크기 구하기
트리는 맨 위의 뿌리(루트)에서 가지가 갈라져 내려가고, 더 갈라지지 않는 끝을 잎이라고 해요. 폴더 구조를 딕셔너리로 담고, 폴더마다 크기를 구해 볼게요.
project = {
"src": {"main.py": 12, "utils.py": 4},
"data": {"raw": {"2026-11.csv": 820, "2026-10.csv": 790}, "clean.csv": 310},
"README.md": 3,
}
def total_size(node): # 폴더 크기 = 안에 든 것들의 합(후위 순회)
if isinstance(node, int): # 숫자면 파일, 값은 크기(KB)
return node
return sum(total_size(child) for child in node.values())
def show(node, name, depth=0): # 나를 먼저 찍고 자식으로 내려가요(전위 순회)
mark = "/" if isinstance(node, dict) else ""
print(" " * depth + f"{name}{mark} ({total_size(node):,}KB)")
if isinstance(node, dict):
for child_name, child in node.items():
show(child, child_name, depth + 1)
show(project, "project")
project/ (1,939KB)
src/ (16KB)
main.py (12KB)
utils.py (4KB)
data/ (1,920KB)
raw/ (1,610KB)
2026-11.csv (820KB)
2026-10.csv (790KB)
clean.csv (310KB)
README.md (3KB)
두 함수는 트리를 도는 순서가 달라요.
show는 나를 먼저 찍고 자식들로 내려가요. 이걸 전위 순회라고 해요. 목차나 파일 목록처럼 위에서부터 보여 줄 때 써요.total_size는 자식들을 먼저 다 계산한 뒤에 나를 계산해요. 이걸 후위 순회라고 해요. 폴더 크기처럼 아래의 결과를 모아야 위가 정해질 때 써요. 폴더를 지울 때도 안의 파일부터 지워야 하니 후위 순회예요.
둘 다 한 갈래를 끝까지 파고든 뒤 돌아오는 깊이 우선 탐색이에요. 웹 트랙에서 다룬 DOM도 트리라서, querySelector가 돌려주는 "처음 만나는 요소"도 이 전위 순서가 기준이에요.
이진 탐색 트리: 정렬을 유지하는 트리
자식이 많아야 둘인 트리를 이진 트리라고 하고, 그중 왼쪽에는 나보다 작은 값, 오른쪽에는 큰 값만 두는 것을 이진 탐색 트리라고 해요. 찾을 때는 뿌리에서 시작해 작으면 왼쪽, 크면 오른쪽으로 내려가요. 이진 탐색을 트리 모양으로 만든 셈이에요. 정렬된 리스트와 달리, 끼워 넣을 때 뒤를 밀 필요 없이 빈자리까지 내려가 매달면 끝이에요.
class TreeNode:
__slots__ = ("key", "left", "right")
def __init__(self, key):
self.key, self.left, self.right = key, None, None
class BST:
def __init__(self):
self.root = None
def insert(self, key): # 작으면 왼쪽, 크면 오른쪽으로 내려가 빈자리에
if self.root is None:
self.root = TreeNode(key)
return
node = self.root
while True:
side = "left" if key < node.key else "right"
child = getattr(node, side)
if child is None:
setattr(node, side, TreeNode(key))
return
node = child
def search(self, key): # 내려간 횟수도 세어요
node, steps = self.root, 0
while node:
steps += 1
if key == node.key:
return steps
node = node.left if key < node.key else node.right
return steps
def height(self):
best, stack = 0, [(self.root, 1)]
while stack:
node, depth = stack.pop()
if node:
best = max(best, depth)
stack += [(node.left, depth + 1), (node.right, depth + 1)]
return best
def in_order(self): # 왼쪽, 나, 오른쪽 순서로 돌면
result, stack, node = [], [], self.root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
result.append(node.key)
node = node.right
return result
import random
random.seed(5)
keys = random.sample(range(100_000), 2_000)
shuffled_tree, sorted_tree = BST(), BST()
for k in keys:
shuffled_tree.insert(k)
for k in sorted(keys):
sorted_tree.insert(k)
biggest = max(keys)
print(f"무작위 순서로 넣은 트리: 높이 {shuffled_tree.height()}, 가장 큰 값 찾기 {shuffled_tree.search(biggest)}번")
print(f"정렬된 순서로 넣은 트리: 높이 {sorted_tree.height():,}, 가장 큰 값 찾기 {sorted_tree.search(biggest):,}번")
print("가운데 순회 결과가 정렬된 순서인가요?", shuffled_tree.in_order() == sorted(keys))
무작위 순서로 넣은 트리: 높이 24, 가장 큰 값 찾기 4번
정렬된 순서로 넣은 트리: 높이 2,000, 가장 큰 값 찾기 2,000번
가운데 순회 결과가 정렬된 순서인가요? True
- 무작위 순서로 넣은 2,000개의 트리는 높이가 24예요. log₂ 2,000이 약 11이니 가장 낮을 수 있는 높이의 두 배쯤이지만, 2,000에 비하면 아주 낮아요. 넣기와 찾기가 높이만큼 걸리니 O(log n) 근처예요.
- 같은 값을 정렬된 순서로 넣으면 늘 오른쪽에만 매달려서 높이가 2,000이 돼요. 사실상 연결 리스트라 찾기가 O(n)이에요. 정렬 강의에서 본 퀵 정렬의 피벗 문제와 같은 모양이에요.
- 가운데 순회(왼쪽, 나, 오른쪽 순서)를 하면 값이 정렬된 순서로 나와요. 그래서 범위 찾기도 할 수 있어요. 해시 테이블이 못 하던 일이에요.
실제로는 넣고 뺄 때마다 모양을 고쳐서 높이를 O(log n)으로 지키는 균형 트리를 써요. AVL 트리와 레드블랙 트리가 대표적이고, 자바의 TreeMap이 레드블랙 트리예요. 데이터베이스 인덱스의 B-트리는 노드 하나에 값을 수백 개씩 담아서 높이를 서너 층으로 낮춘 균형 트리예요. 디스크에서 한 번 읽는 비용이 크니 층수를 줄이는 게 중요하거든요. 파이썬 표준 라이브러리에는 균형 트리가 없어서, 보통 정렬된 리스트와 bisect를 쓰거나 외부 라이브러리를 써요.
힙: 가장 급한 것을 바로 꺼내는 트리
지난 강의들에서 미뤄 둔 우선순위 큐예요. 일이 계속 들어오는데 늘 가장 급한 것부터 처리해야 한다면, 매번 정렬하면 O(n log n)이고 매번 가장 급한 것을 찾으면 O(n)이에요. 힙은 넣기와 꺼내기를 모두 O(log n)으로 해요.
힙의 규칙은 하나예요. 부모가 자식보다 급해요(값이 작아요). 형제끼리나 다른 가지와는 순서를 따지지 않아요. 그리고 이 트리를 배열에 층마다 차례로 담아서, i번 칸의 자식은 2i + 1번과 2i + 2번, 부모는 (i - 1) // 2번 칸이에요. 노드를 따로 만들 필요가 없어요.
import heapq
from itertools import count
tasks, arrival = [], count() # arrival: 같은 순위면 먼저 온 순서로
for priority, name in [(3, "보고서 정리"), (1, "서버 장애 대응"), (2, "코드 리뷰"),
(5, "메일 정리"), (1, "결제 오류 확인")]:
heapq.heappush(tasks, (priority, next(arrival), name)) # 숫자가 작을수록 급해요
print("힙 배열의 순위:", [p for p, _, _ in tasks])
print("부모가 언제나 자식보다 급한가요?",
all(tasks[(i - 1) // 2] <= tasks[i] for i in range(1, len(tasks))))
while tasks:
priority, _, name = heapq.heappop(tasks)
print(f"{priority}순위: {name}")
힙 배열의 순위: [1, 1, 2, 5, 3]
부모가 언제나 자식보다 급한가요? True
1순위: 서버 장애 대응
1순위: 결제 오류 확인
2순위: 코드 리뷰
3순위: 보고서 정리
5순위: 메일 정리
배열을 보면 5가 3보다 앞에 있어요. 힙은 정렬된 상태가 아니라 "부모가 자식보다 작다"는 것만 지켜요. 그래도 뿌리(맨 앞 칸)는 늘 가장 작은 값이라 바로 꺼낼 수 있어요.
- 넣을 때는 맨 끝에 붙인 뒤, 부모보다 작으면 자리를 바꾸며 올라가요.
- 꺼낼 때는 뿌리를 빼고 맨 끝 값을 뿌리에 올린 뒤, 자식보다 크면 더 작은 자식과 자리를 바꾸며 내려가요.
- 어느 쪽이든 높이만큼, 즉 O(log n)이에요. 힙은 늘 위층부터 꽉 채운 모양이라 높이가 log₂ n을 넘지 않아요.
같은 순위끼리는 먼저 온 순서로 꺼내려고 번호표(arrival)를 함께 넣었어요. 이게 없으면 순위가 같을 때 그다음 값인 이름끼리 비교하게 되고, 딕셔너리처럼 비교할 수 없는 값이면 오류가 나요. 정렬 강의의 heapq.nlargest도 이 힙으로 상위 몇 개만 뽑아요. 작업 대기열에서 급한 일 고르기, 가장 먼저 울릴 타이머 찾기, 아래의 다익스트라 알고리즘이 모두 우선순위 큐를 써요. 파이썬의 asyncio도 예약해 둔 일을 힙으로 관리해요.
그래프에서 길 찾기
수학 기초 트랙에서 본 인접 행렬은 정점이 100만 개면 1조 칸이라, 칸마다 1비트만 써도 125GB예요. 사람마다 친구가 평균 200명이라면 인접 리스트는 2억 칸이면 돼요. 실제 그래프는 대부분 이렇게 듬성듬성해서 인접 리스트를 써요.
이제 실제 질문에 답해 볼게요. "집에서 회사까지 어떻게 가지?" 길마다 걸리는 시간(분)이 적힌 지도를 인접 리스트로 담고, 두 가지 기준으로 길을 찾아요.
edges = [("집", "역", 5), ("집", "공원", 7), ("역", "시장", 4), ("역", "회사", 15),
("공원", "도서관", 3), ("도서관", "시장", 2), ("시장", "회사", 6),
("공원", "학교", 4), ("학교", "회사", 20)]
graph = {}
for a, b, minutes in edges: # 양쪽으로 다니는 길이라 양쪽에 모두 적어요
graph.setdefault(a, []).append((b, minutes))
graph.setdefault(b, []).append((a, minutes))
def trace(came_from, goal): # 어디서 왔는지 거꾸로 따라가 길을 복원해요
path, node = [], goal
while node is not None:
path.append(node)
node = came_from[node]
return path[::-1]
def minutes_of(path):
return sum(dict(graph[a])[b] for a, b in zip(path, path[1:]))
from collections import deque
def fewest_stops(start, goal): # 너비 우선 탐색: 거치는 곳이 가장 적은 길
came_from, queue = {start: None}, deque([start])
while queue:
here = queue.popleft()
if here == goal:
break
for nxt, _ in graph[here]:
if nxt not in came_from:
came_from[nxt] = here
queue.append(nxt)
return trace(came_from, goal)
def fastest(start, goal): # 다익스트라: 걸리는 시간이 가장 짧은 길
best, came_from, heap = {start: 0}, {start: None}, [(0, start)]
while heap:
time, here = heapq.heappop(heap) # 지금까지 가장 빨리 닿은 곳부터 꺼내요
if here == goal:
break
if time > best[here]:
continue # 더 빠른 길이 이미 확정된 곳이면 건너뛰어요
for nxt, minutes in graph[here]:
if time + minutes < best.get(nxt, float("inf")):
best[nxt] = time + minutes
came_from[nxt] = here
heapq.heappush(heap, (best[nxt], nxt))
return trace(came_from, goal)
for label, path in [("가장 적게 거치는 길", fewest_stops("집", "회사")), ("가장 빠른 길", fastest("집", "회사"))]:
print(f"{label}: {' → '.join(path)} ({len(path) - 1}구간, {minutes_of(path)}분)")
가장 적게 거치는 길: 집 → 역 → 회사 (2구간, 20분)
가장 빠른 길: 집 → 역 → 시장 → 회사 (3구간, 15분)
- 너비 우선 탐색은 가까운 곳부터 물결처럼 퍼지니, 처음 목적지에 닿는 순간의 길이 거치는 곳이 가장 적은 길이에요. 각 곳을 처음 발견할 때 어디서 왔는지(
came_from)를 적어 두면, 목적지에서 거꾸로 따라가 길 전체를 복원할 수 있어요. - 하지만 거치는 곳이 적다고 빠른 건 아니에요. 역에서 회사로 바로 가는 길은 15분이나 걸려요. 다익스트라 알고리즘은 큐 대신 힙을 써서, 지금까지 가장 빨리 닿은 곳부터 꺼내 이웃까지의 시간을 줄여 나가요. 힙에서 꺼낸 순간 그곳까지의 가장 빠른 시간이 확정돼요. 남은 곳은 모두 그보다 늦게 닿았고, 걸리는 시간이 음수인 길은 없으니 다른 곳을 거쳐 돌아온다고 더 빨라질 수 없거든요.
너비 우선 탐색은 모든 곳과 길을 한 번씩 봐서 O(V + E)(V는 정점, E는 간선의 수), 다익스트라는 힙 때문에 O((V + E) log V)예요. 가중치가 음수인 간선이 있으면 다익스트라는 틀린 답을 낼 수 있어서 벨먼-포드 같은 다른 방법을 써요. 지도 앱은 여기에 목적지 쪽부터 먼저 찾아보는 A* 같은 방법과 미리 계산해 둔 정보를 더해, 훨씬 넓은 지도에서도 빠르게 길을 찾아요.
격자도 그래프예요
그래프가 꼭 정점과 간선 목록으로 주어지는 건 아니에요. 게임 지도나 미로처럼 칸이 정점이고 이웃한 칸이 간선인 격자도 그래프예요. 벽(#)을 피해 S에서 G까지 가장 짧은 길을 찾아볼게요.
maze = [
"S..#....",
"##.#.##.",
".....#..",
".###.#.#",
"...#...G",
]
def solve(maze):
rows, cols = len(maze), len(maze[0])
cells = {(r, c): maze[r][c] for r in range(rows) for c in range(cols)}
start = next(p for p, ch in cells.items() if ch == "S")
goal = next(p for p, ch in cells.items() if ch == "G")
came_from, queue = {start: None}, deque([start])
while queue:
r, c = queue.popleft()
for nxt in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): # 위아래 양옆이 이웃
if cells.get(nxt, "#") != "#" and nxt not in came_from:
came_from[nxt] = (r, c)
queue.append(nxt)
path = trace(came_from, goal)
grid = [list(row) for row in maze]
for r, c in path[1:-1]:
grid[r][c] = "*"
return len(path) - 1, ["".join(row) for row in grid]
steps, drawn = solve(maze)
print(f"가장 짧은 길: {steps}칸")
print("\n".join(drawn))
가장 짧은 길: 11칸
S**#....
##*#.##.
..***#..
.###*#.#
...#***G
그래프를 미리 만들지 않고, 꺼낸 칸에서 위아래 양옆을 그때그때 이웃으로 계산했어요. 지도 밖은 벽으로 쳤고요. 너비 우선 탐색이라 찾은 길이 가장 짧다는 게 보장돼요. 위쪽으로 돌아가는 길도 있지만 더 길어요. 로봇 청소기의 경로, 게임 캐릭터의 길 찾기, 그림판에서 같은 색으로 이어진 영역을 한 번에 칠하는 페인트 통 도구가 모두 이런 격자 탐색이에요.
위상 정렬: 순서 정하기와 순환 찾기
수학 기초 트랙에서 개념만 본 위상 정렬을 깊이 우선 탐색으로 구현해 볼게요. 과목마다 먼저 배워야 할 과목이 정해져 있을 때 공부 순서를 정하는 문제예요.
needs = { # 왼쪽을 배우려면 오른쪽을 먼저 배워야 해요
"딥러닝": ["머신러닝", "미적분"],
"머신러닝": ["파이썬", "선형대수", "확률과 통계"],
"선형대수": ["수학 기초"],
"미적분": ["수학 기초"],
"확률과 통계": ["수학 기초"],
"파이썬": [],
"수학 기초": [],
}
def study_order(needs):
order, state = [], {} # state: 1이면 살펴보는 중, 2면 끝남
def visit(subject):
if state.get(subject) == 2:
return
if state.get(subject) == 1: # 살펴보는 도중에 다시 만났다면 순환
raise ValueError(f"순환이 있어요: {subject}")
state[subject] = 1
for before in needs[subject]:
visit(before) # 먼저 배울 것부터 끝까지 내려가요
state[subject] = 2
order.append(subject) # 필요한 걸 다 마친 뒤에야 내 차례
for subject in needs:
visit(subject)
return order
print(" → ".join(study_order(needs)))
needs["수학 기초"] = ["딥러닝"] # 말이 안 되는 조건을 하나 넣으면
try:
study_order(needs)
except ValueError as e:
print(e)
파이썬 → 수학 기초 → 선형대수 → 확률과 통계 → 머신러닝 → 미적분 → 딥러닝
순환이 있어요: 딥러닝
visit은 먼저 배울 과목을 끝까지 다 처리한 뒤에 자기를 순서에 넣어요. 폴더 크기를 구할 때와 같은 후위 순회예요. 그래서 어떤 과목이든 그 앞에는 필요한 과목이 모두 먼저 나와요.
순환은 상태로 잡아요. 살펴보는 중(1)인 과목을 그 아래에서 다시 만났다는 건, 그 과목이 돌고 돌아 자기 자신을 필요로 한다는 뜻이에요. "수학 기초를 배우려면 딥러닝이 필요하다"는 조건을 넣자 순환을 찾아냈어요. 이미 끝난(2) 과목을 다시 만나는 건 괜찮아요. 수학 기초처럼 여러 과목이 함께 필요로 할 뿐이니까요.
이 알고리즘은 곳곳에서 돌아가요. 패키지 관리자는 설치 순서를, 빌드 도구는 컴파일 순서를, 스프레드시트는 셀을 다시 계산할 순서를 이렇게 정해요. 서버 트랙의 CI 강의에서 본 needs: test도 작업 사이의 의존 관계라, 작업이 많아지면 이런 순서 정하기가 필요해요. 엑셀의 순환 참조 경고나 파이썬의 순환 import 문제도 바로 이런 순환 때문에 생겨요.
실습
show는 폴더마다total_size를 다시 불러서 깊은 곳의 파일을 여러 번 더해요. 한 번의 후위 순회로 모든 폴더 크기를 구해 두고 찍도록 고쳐 보세요.BST에 lo 이상 hi 이하의 값을 모두 찾는range_search를 만들어 보세요. 범위 밖의 가지로는 내려가지 않아야 빨라요.- 힙만 써서 정렬하는 함수(힙 정렬)를 만들어 보세요. 모두 넣은 뒤 하나씩 꺼내면 돼요. 복잡도는 얼마인가요?
- 역에서 회사로 바로 가는 길을 9분으로 바꾸면 가장 빠른 길과 가장 적게 거치는 길이 어떻게 되나요?
study_order를 진입 차수 방식으로 다시 짜 보세요. 먼저 배울 과목이 없는 것부터 큐에 넣고, 하나를 꺼낼 때마다 그 과목을 필요로 하는 과목의 "남은 선수 과목 수"를 하나씩 줄여요. 0이 되면 큐에 넣어요.
자주 하는 실수
- 정렬된 데이터를 그대로 이진 탐색 트리에 넣는다. 한쪽으로 기울어 연결 리스트가 돼요. 균형 트리를 쓰거나 정렬된 리스트와
bisect를 써요. - 힙이 정렬돼 있다고 생각한다. 맨 앞이 가장 작다는 것만 보장돼요. 전체 순서가 필요하면 하나씩 꺼내야 해요.
- 우선순위가 같을 때를 생각하지 않는다. 그다음 값끼리 비교하다 오류가 나거나 순서가 엉켜요. 번호표를 함께 넣어요.
- 방문 표시를 잊는다. 그래프에는 순환이 있어서, 이미 본 곳을 표시하지 않으면 같은 곳을 끝없이 돌아요.
- 가중치가 있는데 너비 우선 탐색을 쓴다. 거치는 곳이 적은 길이지 빠른 길이 아니에요.
- 깊은 트리나 그래프를 재귀로 돈다. 파이썬의 재귀 깊이 한계(기본 1,000)에 걸릴 수 있어요. 깊어질 수 있으면
height와in_order처럼 스택을 직접 써요.
점검 문제
- 폴더 크기를 구할 때 후위 순회를 쓰는 이유는?
- 이진 탐색 트리의 규칙은 무엇이고, 가운데 순회를 하면 정렬된 순서가 나오는 이유는?
- 같은 값을 넣어도 순서에 따라 이진 탐색 트리의 높이가 크게 달라지는 이유와 해결책은?
- 힙에서 가장 작은 값은 바로 볼 수 있고, 넣기와 꺼내기는 O(log n)인 이유는?
- 힙을 배열에 담을 때 i번 칸의 자식과 부모는 몇 번 칸인가요?
- 너비 우선 탐색으로 찾은 길과 다익스트라로 찾은 길이 다를 수 있는 이유는?
- 다익스트라에서 힙에서 꺼낸 곳의 시간이 확정되는 이유와, 음수 가중치가 있으면 안 되는 이유는?
- 위상 정렬에서 순환을 어떻게 찾아내나요?
정답
- 폴더의 크기는 안에 든 것들의 크기를 모두 알아야 정해지니, 자식들을 먼저 계산하고 나를 나중에 계산해야 하기 때문이에요.
- 왼쪽 가지에는 나보다 작은 값, 오른쪽 가지에는 큰 값만 둬요. 그래서 왼쪽을 모두 돌고, 나를 찍고, 오른쪽을 돌면 작은 값부터 차례로 나와요.
- 정렬된 순서로 넣으면 새 값이 늘 한쪽에만 매달려 높이가 n이 되고, 찾기가 O(n)이 돼요. 넣고 뺄 때마다 모양을 고쳐 높이를 O(log n)으로 지키는 균형 트리(AVL 트리, 레드블랙 트리)를 써요.
- 부모가 늘 자식보다 작으니 뿌리가 가장 작아요. 넣고 꺼낼 때는 한 줄기를 따라 올라가거나 내려가며 자리를 바꾸면 되는데, 힙은 꽉 채운 모양이라 높이가 log₂ n을 넘지 않아요.
- 자식은 2i + 1번과 2i + 2번, 부모는 (i - 1) // 2번 칸이에요.
- 너비 우선 탐색은 거치는 곳의 수가 가장 적은 길을 찾고, 다익스트라는 가중치(시간)의 합이 가장 작은 길을 찾기 때문이에요. 거치는 곳이 적어도 한 구간이 아주 오래 걸릴 수 있어요.
- 힙에서 꺼낸 곳은 아직 확정되지 않은 곳 중 가장 빨리 닿은 곳이에요. 다른 곳을 거쳐 오려면 그곳까지만 해도 이미 더 오래 걸리고, 가중치가 음수가 아니니 더 가도 줄지 않아요. 음수 가중치가 있으면 나중에 시간이 줄어들 수 있어서 이 논리가 무너져요.
- 과목마다 "살펴보는 중"과 "끝남" 상태를 두고 깊이 우선으로 내려가다가, 살펴보는 중인 과목을 다시 만나면 순환이에요. 그 과목이 돌고 돌아 자기 자신을 필요로 한다는 뜻이거든요.
다음 강의
이번 강의에서 폴더 크기와 위상 정렬처럼 "작은 문제의 답을 모아 큰 문제를 푸는" 코드를 여러 번 짰어요. 이게 재귀예요. 알고리즘 트랙의 마지막 강의에서는 재귀를 제대로 이해하고, 같은 작은 문제를 몇 번이고 다시 푸는 낭비를 기억해 두기로 없애는 동적 계획법까지 다뤄요.