통합 요약노트
Ch.9 재귀와 백트래킹
콜스택, 가지치기, 순열/조합 — 경우의 수를 다루는 기술
이 챕터의 내용
재귀의 본질 — base case, recursive case, factorial
base case로 멈추고, recursive case로 쪼개는 두 가지 원칙만 잡으면 재귀는 강력한 도구가 됩니다.
러시아 인형 마트료시카를 아시나요?
큰 인형을 열면 작은 인형이 나오고, 그 안에 또 작은 인형이 있습니다
가장 작은 인형에 도달하면 더 이상 열 수 없습니다. 이것이 바로 Base Case입니다
재귀→반복 변환 — 콜스택 시각화, Explicit Stack
명시적 스택을 사용하면 재귀의 논리를 그대로 유지하면서 스택 오버플로우를 피할 수 있습니다.
함수를 호출하면 컴퓨터 내부에서 프레임이 스택처럼 쌓입니다
factorial(4) 호출 시 4개의 프레임이 쌓입니다. n=1에서 반환이 시작되면 아래서부터 하나씩 pop됩니다
Python의 기본 재귀 깊이 제한은 1,000입니다
백트래킹 — 가지치기, Subsets
가지치기(Pruning)로 불필요한 경로를 미리 잘라내면 효율적입니다.
미로를 탈출하는 방법을 생각해봅시다
갈림길에서 왼쪽을 선택 → 막다른 길 → 되돌아와서 오른쪽 선택 → 출구 발견!
백트래킹 = 선택 → 탐색 → 실패 시 되돌리기(undo)를 반복하는 패턴
순열과 조합 — Permutations, Combinations
순열은 visited 배열, 조합은 start 인덱스 — 이 한 가지 차이만 기억하면 됩니다.
A, B, C 세 명 중 두 명을 선택하는 방법
코드 차이 한 줄: 순열 → visited[] 사용, 조합 → start 인덱스 사용
Permutations: [1,2,3]의 모든 순열을 구하라
면접실전 — Combination Sum, N-Queens, Word Search
종료 조건, 선택지 범위, 가지치기 조건 — 이 세 가지만 바꾸면 됩니다.
같은 원소를 여러 번 사용해도 되는 조합 문제입니다
핵심: `backtrack(i, ...)` — i+1이 아닌 i부터 시작. 같은 원소를 다시 선택할 수 있습니다
n×n 체스판에 n개의 퀸을 서로 공격하지 않게 배치하라
챕터 9 종합 퀴즈 — 재귀 & 백트래킹 총정리
실전 면접 수준의 문제들로 자신감을 키워봅시다.
다음 재귀 함수의 출력은? def f(n): if n == 0: return 0 return n + f(n-1) print(f(4))
재귀 함수에 Base Case가 없으면 어떤 일이 발생하는가?
factorial(5) 재귀 호출 시 콜스택에 최대 몇 개의 프레임이 쌓이는가?
- 재귀 = Base Case + Recursive Case (3단계 설계)
- 콜스택 → Explicit Stack으로 반복 변환 가능
- 백트래킹 = 선택 → 탐색 → 되돌리기 + 가지치기
- 순열(visited) vs 조합(start) 한 줄 차이
- N-Queens, Word Search 등 면접 핵심 문제 정복
핵심 용어 모음
재귀 (Recursion)
함수가 자기 자신을 호출하여 문제를 해결하는 기법
Base Case
재귀를 멈추는 종료 조건
Recursive Case
문제를 더 작은 부분으로 쪼개어 자기 자신을 호출
콜스택
함수 호출 시마다 쌓이는 실행 컨텍스트의 스택
스택 프레임
지역 변수, 매개변수, 복귀 주소를 저장하는 블록
Explicit Stack
리스트/배열로 직접 구현한 스택 자료구조
백트래킹
막히면 이전 단계로 되돌아가는 탐색 기법
가지치기
불필요한 경로를 미리 잘라내어 탐색 범위 축소
결정 트리
각 선택지를 노드로 표현한 탐색 공간의 트리
순열 (P)
AB, BA, AC, CA, BC, CB → 6가지 (순서 구분)
조합 (C)
AB, AC, BC → 3가지 (순서 무관)
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 코스 시작하기