알고리즘 - 14. 반복적 DFS (스택을 사용한 트리 순회)
algorithmstreetraversalstackiteration
By sko•10/9/2025•9 min read
반복적 DFS를 사용하는 경우
반복적 DFS는 재귀 없이 트리나 그래프를 순회해야 할 때 사용합니다. 깊은 트리에서 스택 오버플로를 피하기 위해 가장 일반적으로 사용되지만, 다음과 같은 용도로도 적용할 수 있습니다:
- 이진 트리 순회 (중위, 전위, 후위) - 대표적인 사용 사례
- 재귀 깊이가 한계를 초과할 수 있는 경우의 그래프 탐색
- 상태 공간 탐색 - 문제의 모든 가능한 구성이나 상태를 탐색
- 퍼즐 해결 (8-퍼즐, 루빅스 큐브, 스도쿠)
- 게임 상태 탐색 (체스 수, 틱택토 결과)
- 제약이 있는 경로 찾기 (열쇠/문이 있는 미로)
- 구성 문제 (충족 가능성, 제약 충족)
- 명시적 스택은 탐색 경로에 대한 완전한 가시성을 제공하여, 방문한 상태를 추적하고, 사용자 지정 가지치기 전략을 구현하거나, 목표 상태를 찾았을 때 실제 해결 경로를 추출할 수 있습니다
- 스택을 세밀하게 제어해야 하는 백트래킹 문제
- 메모리 사용을 제어하는 트리 직렬화/역직렬화
- 정확한 경로를 유지하면서 트리/그래프에서 경로 찾기
- 호출 스택을 일시 중지, 재개 또는 검사해야 하는 모든 순회
예제 문제
일시 중지 가능한 파일 시스템 검색: 수백만 개의 파일이 깊은 폴더 트리에 구성된 클라우드 스토리지 시스템용 파일 검색 기능을 구축하고 있습니다. 검색에는 다음이 필요합니다:
- 패턴과 일치하는 모든 파일 찾기 (예: "*.pdf")
- 1000개 파일마다 일시 중지하여 진행률 표시줄을 업데이트하고 사용자가 취소했는지 확인
- 사용자가 계속하기를 원하면 중단한 곳에서 정확히 재개
- 일치하는 각 파일의 전체 경로 반환
- 깊게 중첩된 폴더 (수천 레벨 깊이)에서 스택 오버플로 방지
다음과 같은 폴더 구조가 있다고 가정합니다:
Root/
├── Documents/
│ ├── reports/
│ │ ├── report1.pdf ✓ 일치
│ │ └── data.txt
│ └── archive/
│ └── old.pdf ✓ 일치
└── Downloads/
└── ebook.pdf ✓ 일치왜 재귀가 작동하지 않는가:
- 재귀 도중 일시 중지할 수 없음 - 재귀 호출은 완료될 때까지 차단됩니다
- 현재 경로를 검사할 수 없음 - 호출 스택이 숨겨져 있습니다
- 스택 오버플로 위험 - 깊게 중첩된 폴더가 메모리를 소진합니다
- 재개할 수 없음 - 중단되면 처음부터 다시 시작해야 합니다
답: 반복적 DFS는 일시 중지하고, 검사하고 (파일 경로 구축을 위해), 재개할 수 있는 명시적 스택을 제공합니다 - 이는 재귀의 숨겨진 호출 스택으로는 불가능한 일입니다.
반복적 DFS가 실제로 수행하는 작업
반복적 DFS는 데이터 구조 (일반적으로 스택)를 사용하여 재귀 호출 스택을 명시적으로 시뮬레이션합니다. 재귀를 위해 시스템의 호출 스택에 의존하는 대신, 순회 순서를 제어하기 위해 자체 스택을 수동으로 관리합니다.
이를 파일링 캐비닛 검색에 비유하면:
- 재귀적 DFS: 뒤에서 사라지는 빵 부스러기를 따라가는 것 - 현재 위치만 볼 수 있고, 어디에 있었는지, 탐색할 것으로 남아 있는 것이 무엇인지 볼 수 없습니다. 중지해야 하는 경우 모든 진행 상황이 손실됩니다.
- 반복적 DFS: 가시적인 북마크 목록을 가지고 있는 것 - 아직 검색되지 않은 폴더가 무엇인지 정확히 확인할 수 있고, 언제든지 일시 중지할 수 있고, 진행 상황을 확인할 수 있고, 나중에 정확히 같은 위치에서 재개할 수 있습니다
스택 작업의 작동 방식
핵심 패턴 - "호출 스택을 수동으로 관리"
스택으로 순회할 때:
-
푸시 노드를 스택에 넣습니다 (재귀 호출과 같이)
- 나중에 탐색하기 위해 노드를 저장합니다
- 순서가 중요합니다: 마지막에 푸시된 것이 먼저 처리됩니다 (LIFO)
-
팝 노드를 스택에서 꺼냅니다 (재귀 호출에서 반환하는 것처럼)
- 다음에 작업할 노드를 검색합니다
- 하위 트리를 탐색한 후 "돌아가기"를 시뮬레이션합니다
-
처리 적절한 시점에 노드를 처리 (순회 순서에 따라)
- 전위: 처음 만났을 때 즉시 처리 (자식을 푸시하기 전)
- 중위: 더 이상 왼쪽으로 갈 수 없을 때 처리 (왼쪽과 오른쪽 탐색 사이)
- 후위: 두 자식이 모두 완료된 후에만 처리 (두 번째 방문 시)
- 파일 검색: 팝될 때 처리 (패턴과 일치하는지 확인)
-
필요에 따라 상태를 추적 (복잡한 순회의 경우)
- 후위: 첫 번째 방문인지 두 번째 방문인지 알기 위해 "방문됨" 플래그 필요
- 파일 검색: 스택에
[node, path]쌍을 저장하여 전체 경로 추적 - 그래프 순회: 사이클을 피하기 위해 방문한 노드 추적
- 일시 중지 가능한 검색: 진행 카운트, 배치 제한, 완료 상태 추적
3가지 고전적인 트리 순회
중위 순회 - "왼쪽, 루트, 오른쪽"
처리 패턴:
- 가능한 한 왼쪽으로 이동 (노드를 스택에 푸시)
- 더 이상 왼쪽으로 갈 수 없을 때 현재 노드를 처리
- 그런 다음 오른쪽 하위 트리 탐색
- 스택이 비어 있을 때까지 반복
전위 순회 - "루트, 왼쪽, 오른쪽"
처리 패턴:
- 방문할 때 즉시 노드를 처리
- 나중에 처리하기 위해 오른쪽 자식을 푸시 (존재하는 경우)
- 왼쪽 자식으로 이동
- 왼쪽 자식이 없으면 스택에서 팝
후위 순회 - "왼쪽, 오른쪽, 루트"
처리 패턴:
- 자식을 방문했는지 추적
- 첫 번째 방문: 자식을 스택에 푸시
- 두 번째 방문: 노드를 처리
- 세 가지 패턴 중 가장 복잡
이러한 패턴이 적용되는 경우
이러한 패턴은 많은 실제 시나리오에 직접 매핑됩니다:
// 전위: 자식 전에 부모를 처리 (하향식)
// 예: 트리 복사, 구조 직렬화
// 중위: 정렬 순서로 처리 (BST의 경우)
// 예: 정렬된 값 가져오기, 범위 쿼리
// 후위: 부모 전에 자식을 처리 (상향식)
// 예: 크기 계산, 노드 삭제, 식 평가반복적 DFS의 아름다움은 순회를 완전히 제어할 수 있다는 것입니다 - 일시 중지하거나, 스택을 검사하거나, 실행 중에 순회 전략을 수정할 수 있습니다!
가장 중요한 통찰
재귀 호출을 명시적 스택 작업으로 교체하며, 여기서 푸시는 호출을 시뮬레이션하고 팝은 반환을 시뮬레이션합니다 - 그리고 스택 작업에 대해 노드를 처리하는 시점을 신중하게 제어함으로써 재귀 없이 모든 순회 순서를 달성할 수 있습니다.
메모: 알고리즘의 천재성은 탐색할 노드의 간단한 "할 일 목록"을 유지하는 데 있습니다. 스택은 그 목록에 불과합니다. 각 단계에서 목록에서 다음 항목을 가져오고 (팝), 그것에 대한 작업을 수행하고, 발견한 새 항목을 목록에 추가합니다 (푸시). 이 직접적인 멘탈 모델 - "할 일 목록 처리" - 은 재귀에 대해 생각하는 것보다 간단하고, 자연스럽게 재귀가 제공할 수 없는 일시 중지, 진행 상황 검사 또는 사용자 지정 상태 추적 제어를 제공합니다.
의사 결정 프레임워크
각 반복에서 다음에 무엇을 할지 결정하기 위해 간단한 질문을 합니다. 파일 검색 예제의 패턴은 다음과 같습니다:
파일 검색 의사 결정 흐름 (가장 간단한 패턴):
스택에서 다음 항목 팝
↓
파일인가 폴더인가?
↓
┌───────────────┬───────────────┐
│ 파일 │ 폴더 │
└───────────────┴───────────────┘
↓ ↓
일치하는가? 자식을 스택에
↓ 추가
일치하면 저장 ↓
↓ 루프 계속
루프 계속각 단계에서의 질문:
- "일시 중지해야 하는가?" → 충분한 노드를 처리했는지 확인
- "이것은 파일인가 폴더인가?" → 무엇을 할지 결정
- "패턴과 일치하는가?" → 파일의 경우에만
- "어떤 자식을 탐색하는가?" → 스택에 푸시
고전적인 트리 순회의 경우, 패턴은 노드를 처리하고 싶은 시점에 따라 변경됩니다:
전위 (노드 처리 → 자식 탐색):
노드 방문
↓
지금 처리 (값 수집)
↓
오른쪽 자식 푸시 (나중을 위해 저장)
↓
왼쪽 자식으로 이동 (즉시 탐색)사용 사례: 트리 구조 복사, 데이터 직렬화
중위 (왼쪽 탐색 → 노드 처리 → 오른쪽 탐색):
왼쪽으로 갈 수 있는가?
↓
┌─────예─────┬─────아니오────┐
│ │ │
현재 푸시 팝 후 처리
왼쪽으로 이동 그 다음 오른쪽으로사용 사례: BST에서 정렬된 값 가져오기
후위 (자식 탐색 → 노드 처리):
노드에 대한 첫 방문?
↓
┌─────예─────┬─────아니오────┐
│ │ │
노드 푸시 지금 처리
(방문됨 표시) (자식 완료)
자식 푸시사용 사례: 트리 크기 계산, 노드 삭제
핵심 결정: 모든 순회는 "자식을 탐색하는 것에 대해 이 노드를 언제 처리하는가?"로 귀결됩니다. 명시적 스택을 사용하면 이 타이밍을 정확하게 제어할 수 있습니다.
코드
세 가지 순회 유형을 모두 실용적인 예제로 살펴보겠습니다. 주요 차이점은 자식 탐색에 대해 각 노드를 언제 처리하는가입니다.
전위 순회: 처리 → 탐색
패턴: 자식을 탐색하기 전에 현재 노드를 처리 사용 사례: 검색, 트리 복사, 전위 식 평가
// 데모용 간단한 이진 트리 노드
type TreeNode = {
val: number;
left: TreeNode | null;
right: TreeNode | null;
};
// === 전위: 자식 전에 노드 처리 ===
function preorderIterative(root: TreeNode | null): Array<number> {
if (root == null) return [];
const result: Array<number> = [];
const stack: Array<TreeNode> = [root];
while (stack.length > 0) {
const node = stack.pop();
if (node == null) continue;
// 의사 결정 프레임워크: 노드를 볼 때 즉시 처리
result.push(node.val); // 부모를 먼저 처리
// 그런 다음 향후 탐색을 위해 자식 추가
// 왼쪽이 먼저 처리되도록 오른쪽을 먼저 푸시 (LIFO)
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return result;
}
// 예제 트리: 1
// / \
// 2 3
// / \
// 4 5
// 전위: [1, 2, 4, 5, 3] (루트 → 왼쪽 → 오른쪽)실제 예제: 파일 시스템 검색
// 파일 시스템 노드 정의
class FileNode {
name: string;
isFile: boolean;
children: Array<FileNode>;
constructor(
name: string,
isFile: boolean = false,
children: Array<FileNode> = []
) {
this.name = name;
this.isFile = isFile;
this.children = children; // FileNode 배열 (isFile이 true면 비어 있음)
}
}
// 검색 결과 및 진행 상황 타입 정의
type SearchStatus = "paused" | "complete" | "already_complete";
type PausedSearchResult = {
status: "paused";
processed: number;
matches: number;
stackDepth: number;
};
type CompleteSearchResult = {
status: "complete" | "already_complete";
processed: number;
matches: number;
results: Array<string>;
};
type SearchResult = PausedSearchResult | CompleteSearchResult;
type ProgressInfo = {
nodesProcessed: number;
matchesFound: number;
remainingInStack: number;
isComplete: boolean;
};
// 스택 항목 타입: 노드와 루트로부터의 전체 경로를 가진 객체
type StackEntry = {
node: FileNode;
path: string; // 루트로부터의 전체 경로 (예: "Root/Documents/reports")
};
// === 일시 중지 가능한 파일 검색 ===
// 패턴과 일치하는 파일을 검색하며, 일시 중지 및 재개 기능이 있음
// 전위 순회 사용: 자식을 탐색하기 전에 각 노드를 처리
class PausableFileSearch {
private root: FileNode;
private pattern: string;
private searchStack: Array<StackEntry>;
private matchingFiles: Array<string>;
private totalNodesProcessed: number;
private isComplete: boolean;
constructor(root: FileNode, pattern: string) {
this.root = root;
this.pattern = pattern;
// 명시적 스택은 노드와 루트로부터의 전체 경로를 가진 객체를 저장
// 처음에는 루트의 경로가 이름뿐
this.searchStack = [{ node: root, path: root.name }];
// 검색 결과 및 진행 상황 추적
this.matchingFiles = [];
this.totalNodesProcessed = 0;
this.isComplete = false;
}
// 트리를 순회하고, 노드를 처리하며 자식으로 확장
// 노드 제한에 도달하거나 순회를 완료할 때까지 계속
traverse(nodeLimit: number = 1000): SearchResult {
let nodesProcessedThisCall = 0;
while (true) {
// 의사 결정 프레임워크: 순회가 완료되었는가?
const isStackEmpty = this.searchStack.length === 0;
if (isStackEmpty) {
// 더 이상 탐색할 노드가 없음 - 검색 완료
this.isComplete = true;
return {
status: "complete",
processed: this.totalNodesProcessed,
matches: this.matchingFiles.length,
results: this.matchingFiles,
};
}
// 의사 결정 프레임워크: 일시 중지해야 하는가?
const shouldPause = nodesProcessedThisCall >= nodeLimit;
if (shouldPause) {
// 여기서 일시 중지 - 스택이 정확한 위치를 보존
return {
status: "paused",
processed: this.totalNodesProcessed,
matches: this.matchingFiles.length,
stackDepth: this.searchStack.length,
};
}
// 스택에서 다음 노드와 전체 경로 팝
// 위에서 스택이 비어 있지 않음을 이미 확인함
const stackEntry = this.searchStack.pop();
// 위의 비어 있지 않음 확인으로 인해 이것은 절대 일어나지 않아야 하지만,
// TypeScript는 제어 흐름을 이해하지 못함
if (stackEntry == null) {
throw new Error("Unexpected: stack was empty after non-empty check");
}
const currentNode = stackEntry.node;
const currentPath = stackEntry.path;
nodesProcessedThisCall++;
this.totalNodesProcessed++;
// 전위: 자식을 탐색하기 전에 현재 노드 처리
// 의사 결정 프레임워크: 이것은 파일인가 폴더인가?
if (currentNode.isFile) {
// 파일이 패턴과 일치하는지 확인
const matchesPattern = currentNode.name.endsWith(this.pattern);
if (matchesPattern) {
this.matchingFiles.push(currentPath);
}
} else {
// 폴더인 경우 - 향후 탐색을 위해 스택에 자식 추가
// 이것은 현재 노드를 처리한 후에 발생 (전위)
// 왼쪽에서 오른쪽으로 처리되도록 역순으로 푸시
const children = currentNode.children;
for (let i = children.length - 1; i >= 0; i--) {
const childNode = children[i];
const childPath = `${currentPath}/${childNode.name}`;
// 전체 경로와 함께 자식 푸시
this.searchStack.push({ node: childNode, path: childPath });
}
}
}
}
// 일시 중지한 위치에서 순회 재개
resume(nodeLimit: number = 1000): SearchResult {
const canResume = !this.isComplete && this.searchStack.length > 0;
if (canResume) {
return this.traverse(nodeLimit);
}
return {
status: "already_complete",
processed: this.totalNodesProcessed,
matches: this.matchingFiles.length,
results: this.matchingFiles,
};
}
// 현재 진행 상황 가져오기
getProgress(): ProgressInfo {
return {
nodesProcessed: this.totalNodesProcessed,
matchesFound: this.matchingFiles.length,
remainingInStack: this.searchStack.length,
isComplete: this.isComplete,
};
}
}
// === 사용 예제: 파일 시스템 검색 ===
// 예제에서 파일 시스템 트리 구축
const fileSystem = new FileNode("Root", false, [
new FileNode("Documents", false, [
new FileNode("reports", false, [
new FileNode("report1.pdf", true),
new FileNode("data.txt", true),
]),
new FileNode("archive", false, [new FileNode("old.pdf", true)]),
]),
new FileNode("Downloads", false, [new FileNode("ebook.pdf", true)]),
]);
// PDF 파일 검색 생성
const search = new PausableFileSearch(fileSystem, ".pdf");
// 첫 번째 순회: 2개 노드를 처리한 후 일시 중지
let result = search.traverse(2);
console.log(`상태: ${result.status}`);
console.log(`처리됨: ${result.processed} 노드`);
console.log(`일치 수: ${result.matches}`);
// 일시 중지 결과에 대한 타입 가드
if (result.status === "paused") {
console.log(`스택 깊이: ${result.stackDepth} (여기서 재개 가능)`);
}
// 진행 상황 확인
console.log(search.getProgress());
// 재개: 3개 노드를 더 순회한 후 일시 중지
result = search.resume(3);
console.log(`상태: ${result.status}`);
console.log(`처리됨 합계: ${result.processed} 노드`);
console.log(`일치 수: ${result.matches}`);
// 완료될 때까지 재개
result = search.resume(1000);
console.log(`상태: ${result.status}`);
console.log(`처리된 노드 합계: ${result.processed}`);
console.log(`일치 합계: ${result.matches}`);
// 완료 결과에 대한 타입 가드
if (result.status === "complete" || result.status === "already_complete") {
console.log("\n일치하는 파일:");
result.results.forEach((path) => console.log(` ${path}`));
}중위 순회: 왼쪽 탐색 → 처리 → 오른쪽 탐색
패턴: 왼쪽과 오른쪽 자식을 탐색하는 사이에 노드를 처리 사용 사례: 이진 탐색 트리 (정렬된 출력 제공), 식 트리
// === 중위: 자식 사이에서 노드 처리 ===
function inorderIterative(root: TreeNode | null): Array<number> {
if (root == null) return [];
const result: Array<number> = [];
const stack: Array<TreeNode> = [];
let current: TreeNode | null = root;
// 처리를 명시적으로 만드는 헬퍼 함수
function processNode(value: number) {
result.push(value); // 또는 다른 로직
}
while (current != null || stack.length > 0) {
// 의사 결정 프레임워크: 먼저 가능한 한 왼쪽으로 이동
while (current != null) {
stack.push(current); // 스택 작업: 나중을 위해 저장
current = current.left;
}
// 더 이상 왼쪽으로 갈 수 없을 때 노드 처리
const node = stack.pop(); // 스택 작업: 저장된 노드 검색
if (node != null) {
processNode(node.val); // 왼쪽과 오른쪽 사이에서 처리 (스택 작업 아님)
current = node.right; // 그런 다음 오른쪽 하위 트리 탐색
}
}
return result;
}
// 예제 BST: 4
// / \
// 2 6
// / \ / \
// 1 3 5 7
// 중위: [1, 2, 3, 4, 5, 6, 7] (정렬됨!)실제 예제: 데이터베이스 인덱스 순회
무엇을 하고 있는가: 사용자 레코드가 있는 데이터베이스 테이블이 있고, 모든 사용자를 이름의 알파벳 순서로 검색하려고 합니다. 전체 테이블을 스캔하고 정렬하는 대신, 데이터베이스는 이진 탐색 트리 (BST) 인덱스를 사용하여 이름을 구성합니다.
문제: "name" 열의 BST 인덱스가 주어졌을 때, 모든 사용자 레코드를 알파벳 순서로 검색합니다.
데이터베이스 테이블 예제 (Users):
| Record ID | Name | Email | | --------- | ------- | --------------- | | 101 | Charlie | charlie@ex.com | | 102 | Alice | alice@ex.com | | 103 | David | david@ex.com | | 104 | Bob | bob@ex.com | | 105 | Alice | alice2@ex.com |
"Name" 열에 구축된 인덱스 트리:
"Charlie" → [101]
/ \
"Alice" → [102,105] "David" → [103]
\
"Bob" → [104]각 노드는 다음을 저장:
- key: 이름 (인덱스 값)
- recordIds: 해당 이름을 가진 행 ID 배열 (예: 2명의 Alice: 행 102와 105)
목표: 중위 순회를 사용하여 모든 이름을 알파벳 순서로 가져오기: Alice → Bob → Charlie → David
// 데이터베이스 인덱스용 이진 탐색 트리
class IndexNode {
key: string; // 인덱스 값 (예: 사용자 이름 "Alice")
recordIds: Array<number>; // 이 키 값을 가진 모든 데이터베이스 행의 ID
left: IndexNode | null = null;
right: IndexNode | null = null;
constructor(key: string, recordId: number) {
this.key = key;
this.recordIds = [recordId]; // 처음에는 하나의 레코드 ID를 포함
}
}
// 알파벳 순서로 모든 레코드 찾기
// root: 이미 구축된 BST 인덱스의 루트
// 반환: 알파벳 순서의 이름에서 레코드 ID로의 맵
function getAllRecordsInOrder(
root: IndexNode | null // BST는 이미 구조에 의해 정렬 순서를 유지
): Map<string, Array<number>> {
const orderedRecords = new Map<string, Array<number>>();
const stack: Array<IndexNode> = [];
let current = root;
while (current != null || stack.length > 0) {
// 가장 왼쪽 노드로 이동
while (current != null) {
stack.push(current);
current = current.left;
}
// 노드 처리 (정렬 순서)
const node = stack.pop();
if (node != null) {
orderedRecords.set(node.key, node.recordIds);
current = node.right;
}
}
return orderedRecords;
}
// 이름의 예제 인덱스 트리:
// "Charlie"
// / \
// "Alice" "David"
// \
// "Bob"
//
// 중위 순회는: Alice → Bob → Charlie → David (알파벳 순서!)후위 순회: 탐색 → 처리
패턴: 모든 자식을 탐색한 후 노드를 처리 사용 사례: 크기 계산, 트리 삭제, 후위 식 평가
// === 후위: 자식 후에 노드 처리 ===
function postorderIterative(root: TreeNode | null): Array<number> {
if (root == null) return [];
const result: Array<number> = [];
const stack: Array<{ node: TreeNode; visited: boolean }> = [
{ node: root, visited: false },
];
while (stack.length > 0) {
const entry = stack[stack.length - 1]; // 맨 위 엿보기
// 의사 결정 프레임워크: 이 노드의 자식을 이미 방문했는가?
if (!entry.visited) {
// 이 노드를 처음 봄 - 방문됨으로 표시하고 자식 추가
entry.visited = true;
// 자식 추가 (왼쪽이 먼저 처리되도록 오른쪽을 먼저)
if (entry.node.right) {
stack.push({ node: entry.node.right, visited: false });
}
if (entry.node.left) {
stack.push({ node: entry.node.left, visited: false });
}
} else {
// 이 노드를 두 번째로 봄 - 자식이 완료됨, 처리
stack.pop();
result.push(entry.node.val); // 자식 후에 처리
}
}
return result;
}
// 예제 트리: 1
// / \
// 2 3
// / \
// 4 5
// 후위: [4, 5, 2, 3, 1] (왼쪽 → 오른쪽 → 루트)실제 예제: 디렉터리 크기 계산
// 크기를 가진 파일 시스템 노드
class FileSystemNode {
name: string;
isFile: boolean;
size: number; // 파일의 경우: 실제 크기. 디렉터리의 경우: 자식에서 계산
children: Array<FileSystemNode>;
constructor(name: string, isFile: boolean, size: number = 0) {
this.name = name;
this.isFile = isFile;
this.size = size;
this.children = [];
}
}
// 각 디렉터리의 총 크기 계산 (자식을 먼저 처리해야 함!)
function calculateDirectorySizes(root: FileSystemNode): Map<string, number> {
const directorySizes = new Map<string, number>();
const stack: Array<{
node: FileSystemNode;
path: string;
visited: boolean;
}> = [{ node: root, path: root.name, visited: false }];
while (stack.length > 0) {
const entry = stack[stack.length - 1];
if (!entry.visited) {
// 첫 방문: 스택에 자식 추가
entry.visited = true;
if (!entry.node.isFile) {
// 처리를 위해 모든 자식 추가
for (const child of entry.node.children) {
stack.push({
node: child,
path: `${entry.path}/${child.name}`,
visited: false,
});
}
}
} else {
// 두 번째 방문: 자식이 처리됨, 이 노드의 크기 계산
stack.pop();
if (entry.node.isFile) {
// 파일: 크기만 사용
// 부모 디렉터리가 이것을 합산함
} else {
// 디렉터리: 모든 자식의 크기 합산
let totalSize = 0;
for (const child of entry.node.children) {
if (child.isFile) {
// 파일: 파일의 직접 크기 사용
totalSize += child.size;
} else {
// 하위 디렉터리: 이미 계산된 합계 검색
// 후위는 이 자식 디렉터리가 완전히 처리되었음을 보장
// 이전에 (부모 전에 스택에서 팝됨), 따라서 완전한
// 크기가 이미 맵에 저장됨. 이중 계산이 아닙니다 -
// 재계산 대신 사전 계산된 합계를 사용하고 있습니다.
const childPath = `${entry.path}/${child.name}`;
const childDirectoryTotal = directorySizes.get(childPath) || 0;
totalSize += childDirectoryTotal;
}
}
// 이 디렉터리의 총 크기를 맵에 저장
// (이 합계는 이 디렉터리가 자식으로 나타날 때 사용됨)
directorySizes.set(entry.path, totalSize);
entry.node.size = totalSize; // 노드 자체 업데이트
}
}
}
return directorySizes;
}
// 파일 시스템 예제:
// Root/
// ├── docs/ (30KB 합계)
// │ ├── file1.txt (10KB)
// │ └── file2.txt (20KB)
// └── images/ (150KB 합계)
// ├── pic1.jpg (100KB)
// └── pic2.jpg (50KB)
//
// 후위는 Root/의 크기 (180KB)를 계산하기 전에
// docs/와 images/의 크기를 계산함을 보장요약: 각 순회를 언제 사용하는가
| 순회 | 언제 처리하는가 | 사용 사례 | | ---------- | -------------------- | -------------------------------------------- | | 전위 | 자식 전 | 검색, 복사, 직렬화 | | 중위 | 왼쪽과 오른쪽 사이 | BST에서 정렬된 검색 | | 후위 | 모든 자식 후 | 크기 계산, 정리, 종속성 |
반복적 DFS의 아름다움은 스택을 명시적으로 관리함으로써 순회 순서를 완전히 제어할 수 있다는 것입니다 - 자식을 탐색하는 시점에 대해 노드를 처리하는 시점을 변경하기만 하면 됩니다!
의문 해소
일반적인 의문: "반복적 DFS가 재귀적 DFS가 할 수 있는 모든 것을 진정으로 처리할 수 있는가? 더 넓게 말하면, 반복이 모든 재귀 로직을 대체할 수 있는가, DFS뿐만 아니라? 아니면 재귀가 근본적으로 필요한 경우가 있는가?"
근본적인 동등성: 반복이 모든 재귀를 대체할 수 있는가?
예, 이론적으로 모든 재귀 알고리즘을 반복적으로 변환할 수 있습니다. 이것은 DFS에만 국한된 것이 아닙니다 - 컴퓨터 과학의 기본 원리입니다.
이것이 보편적으로 사실인 이유: 모든 재귀 알고리즘은 호출 스택을 사용합니다. 반복 버전은 대신 명시적 스택 데이터 구조를 사용하기만 하면 됩니다. 항상 자체 스택을 만들 수 있으므로 항상 재귀를 반복으로 대체할 수 있습니다.
이것은 모든 재귀 알고리즘에 적용됩니다:
- 트리/그래프 순회 (DFS, BFS 변형)
- 분할 정복 (퀵소트, 병합 정렬, 이진 검색)
- 백트래킹 (N-퀸, 스도쿠 솔버, 순열)
- 동적 프로그래밍 (하향식 재귀 또는 상향식 반복)
- 수학적 재귀 (피보나치, 팩토리얼, 하노이의 탑)
DFS의 경우, 동등성이 작동하는 이유는 다음과 같습니다:
재귀 호출을 할 때 시스템은 자동으로 두 가지를 수행합니다:
- 지역 변수를 저장 호출 스택에
- 돌아올 위치를 기억 호출이 완료될 때
반복적 DFS에서는 이 두 가지를 수동으로 수행합니다:
- 상태를 저장 명시적 스택에 (스택 항목에 변수 저장)
- 실행 흐름을 제어 루프와 스택 작업으로
예제를 통한 증명 - 재귀 함수와 그 반복적 동등물입니다:
// 재귀: 트리 높이 계산
function heightRecursive(node: TreeNode | null): number {
if (node == null) return 0;
// 재귀 호출은 이 계산을 호출 스택에 저장
const leftHeight = heightRecursive(node.left);
const rightHeight = heightRecursive(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
// 반복: 동일한 계산, 명시적 스택
function heightIterative(root: TreeNode | null): number {
if (root == null) return 0;
// 부분 결과를 저장해야 함 - 이것이 복잡하게 만드는 이유
type StackEntry = {
node: TreeNode;
phase: "initial" | "left_done" | "right_done";
leftHeight?: number; // 왼쪽 하위 트리의 결과 저장
rightHeight?: number; // 오른쪽 하위 트리의 결과 저장
};
const stack: Array<StackEntry> = [{ node: root, phase: "initial" }];
let finalHeight = 0;
while (stack.length > 0) {
const entry = stack[stack.length - 1]; // 엿보기
if (entry.phase === "initial") {
// 첫 방문 - 왼쪽 자식 탐색
entry.phase = "left_done";
if (entry.node.left) {
stack.push({ node: entry.node.left, phase: "initial" });
} else {
entry.leftHeight = 0; // 왼쪽 자식 없음 = 높이 0
}
} else if (entry.phase === "left_done") {
// 왼쪽 완료 - 결과 캡처하고 오른쪽 탐색
if (entry.node.left) {
// 왼쪽 자식의 결과를 스택에서 팝
const leftResult = stack.pop();
if (leftResult != null) {
entry.leftHeight = finalHeight; // 왼쪽의 계산된 높이 저장
}
}
entry.phase = "right_done";
if (entry.node.right) {
stack.push({ node: entry.node.right, phase: "initial" });
} else {
entry.rightHeight = 0;
}
} else {
// 두 자식 완료 - 이 노드의 높이 계산
if (entry.node.right) {
stack.pop(); // 오른쪽 자식 팝
entry.rightHeight = finalHeight;
}
const leftH = entry.leftHeight ?? 0;
const rightH = entry.rightHeight ?? 0;
finalHeight = Math.max(leftH, rightH) + 1;
stack.pop(); // 이 노드 팝
}
}
return finalHeight;
}핵심: 예, 모든 재귀적 DFS를 반복적으로 변환할 수 있습니다. 하지만 복잡성의 차이를 보십시오!
DFS를 넘어서: 반복으로 변환된 다른 재귀 알고리즘
이것이 DFS에만 국한되지 않음을 증명하기 위해, 다른 고전적인 재귀 알고리즘과 그 반복적 동등물을 보여줍니다:
예제 1: 퀵소트 (분할 정복)
// 재귀: 우아한 15줄
function quicksortRecursive(arr: Array<number>, low: number, high: number) {
if (low >= high) return;
const pivot = partition(arr, low, high);
quicksortRecursive(arr, low, pivot - 1); // 왼쪽 정렬
quicksortRecursive(arr, pivot + 1, high); // 오른쪽 정렬
}
// 반복: 범위를 추적하기 위해 명시적 스택 필요
function quicksortIterative(arr: Array<number>) {
const stack: Array<[number, number]> = [[0, arr.length - 1]];
while (stack.length > 0) {
const range = stack.pop();
if (range == null) continue;
const [low, high] = range;
if (low >= high) continue;
const pivot = partition(arr, low, high);
// 두 범위를 스택에 푸시 (재귀 호출 대체)
stack.push([low, pivot - 1]);
stack.push([pivot + 1, high]);
}
}예제 2: 피보나치 (수학적 재귀)
// 재귀: 자연스러운 수학적 정의
function fibRecursive(n: number): number {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
// 반복: 상향식 접근 (실제로 더 효율적!)
function fibIterative(n: number): number {
if (n <= 1) return n;
let prev = 0;
let curr = 1;
for (let i = 2; i <= n; i++) {
const next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}예제 3: 백트래킹 - 모든 순열 생성
// 재귀: 깔끔한 백트래킹 패턴
function permuteRecursive(nums: Array<number>): Array<Array<number>> {
const result: Array<Array<number>> = [];
function backtrack(current: Array<number>, remaining: Array<number>) {
if (remaining.length === 0) {
result.push([...current]);
return;
}
for (let i = 0; i < remaining.length; i++) {
backtrack(
[...current, remaining[i]],
[...remaining.slice(0, i), ...remaining.slice(i + 1)]
);
}
}
backtrack([], nums);
return result;
}
// 반복: 복잡한 상태 관리
function permuteIterative(nums: Array<number>): Array<Array<number>> {
const result: Array<Array<number>> = [];
const stack: Array<{
current: Array<number>;
remaining: Array<number>;
}> = [{ current: [], remaining: nums }];
while (stack.length > 0) {
const state = stack.pop();
if (state == null) continue;
if (state.remaining.length === 0) {
result.push(state.current);
continue;
}
// 모든 가능한 다음 상태 푸시
for (let i = state.remaining.length - 1; i >= 0; i--) {
stack.push({
current: [...state.current, state.remaining[i]],
remaining: [
...state.remaining.slice(0, i),
...state.remaining.slice(i + 1),
],
});
}
}
return result;
}주요 관찰: 모든 경우에 재귀를 반복으로 변환할 수 있지만, 재귀 버전이 일반적으로 더 깔끔하고 직관적입니다. 반복 버전은 재귀가 자동으로 처리하는 상태를 수동으로 관리해야 합니다.
각각을 언제 사용해야 하는가?
동등성이 반복이 항상 더 낫다는 것을 의미하지는 않습니다. 실용적인 의사 결정 프레임워크는 다음과 같습니다:
재귀적 DFS를 사용하는 경우:
- ✅ 자연스러운 적합 - 문제가 본질적으로 재귀적 (트리 연산, 분할 정복)
- ✅ 단순성이 중요 - 더 깔끔하고, 이해하기 쉽고, 유지 관리하기 쉬움
- ✅ 스택 오버플로 위험 없음 - 트리 깊이가 합리적 (일반적으로 1000 레벨 미만이 안전)
- ✅ 반환 값이 필요 - 하위 트리에서 결과를 수집하고 결합해야 함
- ✅ 표준 순회 - 재귀가 가장 명확한 기본 전/중/후위
예: 재귀가 여기서 완벽함
// 트리에서 최대값 찾기 - 재귀가 자연스럽게 깔끔함
function findMax(node: TreeNode | null): number {
if (node == null) return -Infinity;
return Math.max(node.val, findMax(node.left), findMax(node.right));
}
// 반복 버전은 복잡한 상태 추적이 필요 - 가치가 없음!반복적 DFS를 사용하는 경우:
- ✅ 스택 오버플로 위험 - 매우 깊은 트리 (수백만 노드, 수천 레벨)
- ✅ 일시 중지/재개 필요 - 일시 중지하고 나중에 재개해야 하는 장기 실행 검색
- ✅ 스택 검사 필요 - 현재 경로 또는 순회 상태를 확인해야 함
- ✅ 사용자 지정 제어 흐름 - 백트래킹, 하위 트리 건너뛰기 또는 실행 중 순회 수정 필요
- ✅ 메모리 제약 - 시스템 호출 스택이 제한되어 있지만 힙 메모리는 사용 가능
예: 반복이 여기서 필요함
// 일시 중지 가능한 검색 - 재귀로는 불가능
class PausableSearch {
private stack: Array<StackEntry>;
search(limit: number) {
while (this.stack.length > 0 && processed < limit) {
// 노드 처리...
// 여기서 일시 중지하고 나중에 재개할 수 있습니다!
}
}
}실제 경험 법칙
특정 이유가 없는 한 대부분의 알고리즘에 대해 재귀를 기본값으로 사용합니다:
- 95%의 문제 → 재귀 사용 (더 간단하고, 깔끔하고, 유지 관리하기 쉬움)
- 특별한 요구가 있는 5% → 반복 사용 (스택 오버플로 위험, 일시 중지/재개, 명시적 상태 검사)
재귀가 열등하지 않습니다 - 대부분의 재귀 문제에 대한 자연스럽고 선호되는 솔루션입니다. 반복 접근 방식은 재귀의 한계가 실제 문제가 될 때를 위한 강력한 도구이며, 항상 사용해야 하는 "더 나은" 접근 방식이 아닙니다.
왜 재귀가 일반적으로 선호되는가:
- 문제 구조와 일치 - 트리 순회, 분할 정복, 백트래킹은 본질적으로 재귀적 개념
- 자체 문서화 코드 - 재귀 코드는 종종 수학적 정의나 문제 설명처럼 읽힘
- 오류 발생 가능성 낮음 - 수동 스택 관리가 없다는 것은 버그가 적다는 것을 의미
- 컴파일러 최적화 - 현대 컴파일러는 꼬리 재귀 함수를 자동으로 최적화할 수 있음
반복이 필요해지는 경우:
- 스택 깊이 제한 - 시스템 호출 스택은 일반적으로 수천 프레임으로 제한됨
- 외부 제약 - 프로그램 재시작 간에 상태를 저장/복원해야 함
- 성능 중요 - 함수 호출 오버헤드 제거 (컴파일러가 종종 이를 수행하지만)
- 교육 목적 - 재귀가 내부적으로 무엇을 하는지 이해
왜 복잡성 차이가 있는가?
재귀 버전이 더 간단한 이유는 언어 런타임이 상태 관리를 처리하기 때문입니다:
- 호출 스택은 자동으로 지역 변수를 저장
- 반환 값은 자동으로 위로 흐름
- 실행은 자동으로 올바른 위치에서 재개
반복 버전은 이 모든 것을 수동으로 구현해야 합니다:
- 스택 항목에 변수를 명시적으로 저장
- 처리의 어느 단계에 있는지 수동으로 추적
- 각 단계 전환을 처리하는 코드 작성
하지만 반복이 더 깔끔하다면?
훌륭한 질문: "재귀의 주요 장점이 명확성이라면, 반복도 깔끔할 때 반복이 더 나은 것 아닌가?"
예, 절대적으로! 반복 솔루션이 똑같이 깔끔하고 직관적일 때, 다음과 같은 이유로 재귀보다 종종 더 좋습니다:
- ✅ 스택 오버플로 위험 없음
- ✅ 실행에 대한 명시적 제어
- ✅ 더 쉬운 디버깅 (스택을 직접 검사할 수 있음)
- ✅ 더 나은 성능 (함수 호출 오버헤드 없음)
반복이 자연스럽게 더 깔끔한 예: 피보나치
// 재귀: 수학적 정의와 일치하지만 지수 시간 복잡도
function fibRecursive(n: number): number {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2); // 같은 값을 재계산!
}
// 반복: 실제로 더 간단하고 더 효율적
function fibIterative(n: number): number {
if (n <= 1) return n;
let prev = 0,
curr = 1;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr]; // 깔끔한 한 줄 업데이트
}
return curr;
}이 경우 반복이 우수합니다 - 더 간단하고, 읽기 쉽고, 더 효율적입니다.
반복이 자연스럽게 깔끔한 다른 경우:
-
꼬리 재귀 함수 - 이것들은 단지 위장된 루프입니다:
// 꼬리 재귀: 마지막 연산이 재귀 호출 function sumRecursive(n: number, acc: number = 0): number { if (n === 0) return acc; return sumRecursive(n - 1, acc + n); // 꼬리 호출 } // 반복은 똑같이 명확하고 스택 프레임을 피함 function sumIterative(n: number): number { let sum = 0; for (let i = 1; i <= n; i++) { sum += i; } return sum; } -
상향식 동적 프로그래밍 - 반복이 더 자연스럽습니다:
// 기본 케이스에서 솔루션을 구축하는 것은 자연스럽게 반복적 function climbStairs(n: number): number { if (n <= 2) return n; let prev = 1, curr = 2; for (let i = 3; i <= n; i++) { [prev, curr] = [curr, prev + curr]; } return curr; } -
간단한 선형 순회 - 루프가 재귀보다 명확합니다:
// 배열 합계 - 반복이 더 자연스러움 function sumArray(arr: Array<number>): number { let sum = 0; for (const num of arr) { sum += num; } return sum; }
핵심 원칙: 특정 문제에 대해 더 깔끔한 것을 사용하십시오.
대부분의 재귀 문제 (트리, 분할 정복, 백트래킹)는 다음을 포함하기 때문에 재귀가 더 깔끔합니다:
- 여러 재귀 호출
- 하위 트리에서 반환 값 결합
- 자연스러운 계층 구조
하지만 반복이 똑같이 또는 더 직관적일 때 (꼬리 재귀, 선형 순회, 상향식 DP), 위의 이점을 위해 반복을 선호합니다.
결론:
- 반복이 모든 재귀를 대체할 수 있는가 (DFS뿐만 아니라)? 예, 이론적으로 모든 재귀 알고리즘을 반복적으로 변환할 수 있습니다.
- 항상 재귀 대신 반복을 사용해야 하는가? 아니요, 절대 아닙니다.
- 항상 반복 대신 재귀를 사용해야 하는가? 아니요, 절대 아닙니다.
- 실제 규칙: 특정 문제에 대해 더 깔끔하고 직관적인 접근 방식을 사용하십시오. 실제로 이것은 트리/그래프/백트래킹에는 재귀 (더 깔끔함), 꼬리 재귀 패턴/선형 순회/상향식 DP에는 반복 (똑같이 또는 더 명확함)을 의미합니다.