파일 업로드 화면에서 폴더를 통째로 끌어다 놓으면 폴더 전체 용량을 보여 줘야 한다. 폴더 안에는 파일과 하위 폴더가 있고, 하위 폴더 안에 또 폴더가 있다. 관리자 메뉴 에서 권한 있는 항목만 남기는 일, 상품 옵션(사이즈 × 색상)의 모든 조합을 만드는 일도 비슷하다. 셋 다 한 갈래를 끝까지 들어갔다가 돌아와서 다음 갈래로 가는 문제다.
이렇게 깊이부터 파고드는 탐색을 깊이 우선 탐색(depth-first search, DFS)이라고 한다. 너비 우선 탐색(BFS)이 출발점에서 가까운 것부터 한 겹씩 넓혀 간다면, DFS는 한 갈래의 끝에 닿을 때까지 먼저 들어간다. 재귀 함수로 가장 짧게 쓸 수 있다. 개념 정리는 DFS, 재귀, 트리 순회 노트에 있다.
재귀 DFS: 자식을 다 더하고 돌아온다
폴더 용량 = 자기 폴더에 바로 든 파일 용량 + 하위 폴더 용량의 합. 정의 안에 같은 정의가 들어 있으니 그대로 재귀 함수가 된다. 하위 폴더가 없으면 더할 것이 없어 반복문을 돌지 않고 바로 돌아온다. 이것이 재귀가 멈추는 바닥(base case)이다.
폴더 src(2) 아래에 app(5)과 lib(4)이 있고, app 아래에 ui(3)가 있다. 괄호는 그 폴더에 바로 든 파일 용량이다. 각 폴더의 합계를 다 구한 직후 폴더 = 합계를 찍는 재귀 코드에서 가장 먼저 찍히는 줄은?
선택지와 해설 보기
실험 폴더 용량을 재귀로 더하기
폴더마다 자기 파일 용량(sizes)과 하위 폴더 목록(children)이 있습니다. 아래 콜스택 줄에서 호출이 쌓이고 빠지는 모습을 보세요.
const sizes: Record<string, number> = { src: 2, app: 5, ui: 3, lib: 4 }const children: Record<string, string[]> = { src: ['app', 'lib'], app: ['ui'] }function total(node: string): number { let acc = sizes[node] for (const child of children[node] ?? []) { acc += total(child) } console.log(`${node} = ${acc}`) return acc}total('src')
아직 변수가 없습니다.
- 해볼 것
- 폴더 4개 입력을 끝까지 실행해 출력 순서를 본다
- 깊은 폴더로 바꿔 콜스택이 가장 길어지는 순간을 찾아본다
출력은 ui = 3, app = 8, lib = 4, src = 14 순서다. total('src')가 total('app')을 부르면 src의 실행은 acc += total(child) 줄에서 멈춰 기다리고, app의 실행이 콜스택(call stack) 맨 위에 쌓인다. 콜스택은 아직 끝나지 않은 함수 호출을 쌓아 두는 곳으로, 칸마다 그 호출의 지역 변수(node, acc)를 따로 들고 있다. 그래서 app을 계산하는 동안에도 src의 acc = 2는 사라지지 않는다. ui가 3을 돌려주고 콜스택에서 빠지면 app이 그 자리에서 이어서 실행된다.
자식을 먼저 다 처리하고 자기 일을 하는 순서를 후위 순회(post-order)라고 한다. 폴더 용량처럼 "아래의 결과를 모아야 위가 정해지는" 계산이 이 모양이다. 반대로 자기 일을 먼저 하고 자식으로 내려가면 전위 순회(pre-order)다. 폴더 이름을 들여쓰기해 목록으로 찍는 일이 그렇다. 폴더가 n개면 폴더마다 한 번 들어가므로 O(n)이고, 콜스택은 가장 깊은 경로의 길이(트리 높이)만큼 쌓인다. src → pages → cart → hooks처럼 4단계 깊은 폴더면 4칸까지 쌓인다.
재귀 깊이의 한계와 명시적 스택
콜스택은 크기가 정해져 있다. Python은 인터프리터 스택의 최대 깊이를 정해 두고, 그보다 깊이 들어가면 RecursionError를 던진다(Python 문서: RecursionError). 지금 한계는 sys.getrecursionlimit()으로 보고 sys.setrecursionlimit()으로 바꿀 수 있지만, 문서는 가능한 최댓값이 플랫폼마다 다르고 너무 높이면 Python이 비정상 종료할 수 있다고 경고한다(Python 문서: sys). JavaScript에서도 호출이 너무 깊으면 Chrome·Safari는 RangeError: Maximum call stack size exceeded, Firefox는 InternalError: too much recursion을 던진다(MDN: too much recursion).
폴더 트리는 대개 수십 단계를 넘지 않아 재귀로 충분하다. 하지만 사용자가 만든 데이터처럼 깊이를 장담할 수 없으면(댓글의 답글의 답글, 길게 이어진 연결 리스트(linked list)), 콜스택 대신 배열을 스택(stack)으로 직접 들고 다닌다.
function walk(root: string): number { let acc = 0 const stack = [root] while (stack.length) { const node = stack.pop()! acc += sizes[node] stack.push(...(children[node] ?? [])) } return acc}
stack에서 꺼낸 폴더의 하위 폴더를 다시 stack에 넣는다. 배열은 콜스택보다 훨씬 크게 늘어날 수 있다. 1절의 폴더 4개에서도 walk('src')는 14를 돌려준다. 다만 이 방식은 합계만 구한다. "자식을 다 더한 뒤 자기 줄 찍기" 같은 후위 순서를 지키려면 폴더마다 "자식을 아직 안 봤음/다 봤음" 표시를 더 들고 다녀야 한다. 재귀가 콜스택에 공짜로 맡기던 일을 직접 하는 셈이다.
백트래킹: 고르고, 들어가고, 되돌리기
상품 옵션이 사이즈(S, M)와 색상(검정, 흰색)이면 조합은 4개다. 그룹이 몇 개일지 모르면 for 문을 몇 겹 쓸지 정할 수 없다. 재귀로 "i번 그룹에서 하나 고르고, 나머지는 i + 1번 그룹부터 똑같이"라고 쓰면 그룹 수와 상관없이 한 함수로 끝난다.
조합을 만드는 동안 지금까지 고른 것을 path 배열 하나에 쌓는다. 하나를 고르고(push), 다음 그룹으로 들어갔다가(재귀), 돌아오면 방금 고른 것을 빼서(pop) 같은 그룹의 다른 선택지를 고를 자리를 만든다. 이렇게 선택을 되돌리며 모든 경우를 훑는 방법을 백트래킹(backtracking)이라고 한다.
옵션 조합을 만드는 백트래킹 코드에서 path.pop() 줄을 지우면, 사이즈(S, M) × 색상(검정, 흰색) 입력에서 두 번째로 찍히는 줄은?
선택지와 해설 보기
실험 옵션 조합을 고르고 되돌리며 만들기
그룹마다 하나씩 골라 조합을 만듭니다. path는 지금까지 고른 옵션입니다. 재귀에서 돌아온 직후 pop이 무엇을 되돌리는지 보세요.
const groups = [['S', 'M'], ['검정', '흰색']]const path: string[] = []function pick(i: number) { if (i === groups.length) { console.log(path.join(' / ')) return } for (const opt of groups[i]) { path.push(opt) pick(i + 1) path.pop() }}pick(0)
아직 변수가 없습니다.
- 해볼 것
- 2 × 2 입력을 끝까지 실행해 본다
- 2 × 3 입력으로 바꿔 조합이 몇 개 나오는지 세어 본다
S / 검정을 찍고 돌아오면 pop이 검정을 빼서 path가 ['S']로 돌아간다. 그래서 다음 선택 흰색이 S 바로 뒤에 붙는다. pop이 없으면 path는 ['S', '검정', '흰색']이 되어 두 번째 줄부터 틀린다. 끝까지 실행하면 path가 다시 빈 배열이다. 넣은 만큼 정확히 뺐다는 확인이다.
조합 수는 그룹별 선택지 수의 곱이다(곱의 법칙, 『개발 수학』 Unit 6). 선택지가 2 × 3이면 6개, 사이즈 5 × 색상 8 × 소재 4라면 160개다. 백트래킹은 이 경우를 하나도 빠짐없이 만들기 때문에, 시간은 결과 개수에 비례해 그룹이 늘수록 곱으로 커진다.
함정 찾기 AI가 짠 옵션 조합 함수, 결과가 왜 이상할까?
“옵션 그룹 배열을 받아서 그룹마다 하나씩 고른 모든 조합을 배열로 돌려주는 함수를 짜 줘.”
의심스러운 줄을 모두 눌러 표시한 뒤 “검토 끝”을 누르세요. 함정은 2개입니다.
정리하면 틀린 줄은 둘이다. path 배열 자체를 결과에 넣어 모든 결과가 같은 배열을 가리키고([...path]로 복사한다), 재귀에서 돌아온 뒤 path.pop()이 없어 path가 계속 길어진다.
가지치기: 답이 될 수 없는 갈래는 들어가지 않는다
관리자 메뉴 트리에서 권한 있는 항목만 남길 때, 상위 메뉴에 권한이 없으면 그 아래는 볼 필요가 없다. 이렇게 더 들어가도 답이 나올 수 없는 갈래를 미리 자르는 것을 가지치기(pruning)라고 한다. 는 그룹이 늘수록 곱으로 커지고, 백트래킹은 그 경우를 모두 훑는다. 그래서 실제 속도는 가지치기로 얼마나 큰 덩어리를 통째로 건너뛰느냐가 정한다. 최악의 경우 복잡도는 그대로일 수 있지만, 자르는 조건이 일찍 걸릴수록 들어가는 호출 수가 크게 준다(보너스의 [3, 4] → 5는 수를 하나 고르자마자 잘려 호출 몇 번으로 끝난다). 보너스 문제에서 정렬 하나로 가지를 자르는 예를 본다.
확인 문제 장을 덮기 전에 떠올려 보기
1. 재귀로 폴더 트리 용량을 더할 때 콜스택이 가장 깊어지는 정도는 무엇으로 정해질까?
2. 백트래킹에서 고른 것을 쌓는 배열 path를 재귀 호출 바로 뒤에 pop하는 이유는?
3. Python에서 재귀 호출이 인터프리터의 최대 깊이를 넘으면 무슨 일이 생길까?
더 풀어 보기(선택) · 합이 target인 조합 모두 찾기
서로 다른 양의 정수로 이루어진 배열 nums와 양의 정수 target이 있다. 합이 정확히 target이 되는 조합을 모두 찾아 고른 수를 나열하자. 같은 수를 여러 번 써도 되고, 순서만 다른 조합(2 + 5와 5 + 2)은 하나로 친다. 답이 될 수 없는 갈래는 들어가지 않게 가지치기를 하자.
nums = [2, 3, 5], target = 7 → 2 + 2 + 3 → 2 + 5