알고리즘

재귀, 스택(Stack), 큐(Queue), 깊이 우선 탐색(DFS)

컴퓨터 과학에서는 재귀(Recursion), 스택(Stack), 큐(Queue)가 기본적인 자료 구조입니다. 또한, 깊이 우선 탐색(DFS)과 같은 알고리즘에 사용됩니다. 이 글에서는 다음 개념을 설명합니다.

• 재귀 개념과 예제
• 스택(Stack)과 연산
• 큐(Queue)와 스택과의 차이점
• DFS에서 스택이 어떻게 사용되는지

---

1. 재귀 (Recursion)

재귀란?

재귀는 함수가 자기 자신을 호출하여 문제를 해결하는 기법입니다. 기본적으로:

• 기저 조건(Base Case): 재귀 호출을 중단하는 조건
• 재귀 호출(Recursive Case): 함수가 자기 자신을 호출

예제: 팩토리얼 계산

팩토리얼의 정의:

n! = n × (n-1) × (n-2) × ... × 1

팩토리얼을 C++로 구현하면:

int factorial(int n) {

    if (n == 0) return 1; 

    return n * factorial(n - 1);

}

---

2. 스택(Stack): 후입선출(LIFO)

스택이란?

스택은 LIFO(Last In, First Out, 후입선출) 원칙을 따르는 자료구조입니다. 즉, 마지막에 추가된 요소가 가장 먼저 제거됩니다.

주요 연산:

• push(x) – 요소를 스택의 맨 위에 추가
• pop() – 맨 위 요소 제거
• top() – 맨 위 요소 확인 (제거하지 않음)

C++ 예제:

#include <stack>

#include <iostream>

using namespace std;

int main() {

    stack<int> s;

    s.push(1);

    s.push(2);

    s.push(3);

    cout << s.top() << endl; // 3

    s.pop();

    cout << s.top() << endl; // 2

    return 0;

}

---

3. 큐(Queue): 선입선출(FIFO)

큐란?

큐는 FIFO(First In, First Out, 선입선출) 원칙을 따릅니다. 즉, 먼저 추가된 요소가 가장 먼저 제거됩니다.

주요 연산:

• push(x) – 요소를 큐의 끝에 추가
• pop() – 앞쪽 요소 제거
• front() – 앞쪽 요소 확인 (제거하지 않음)

C++ 예제:

#include <queue>

#include <iostream>

using namespace std;

int main() {

    queue<int> q;

    q.push(1);

    q.push(2);

    q.push(3);

    cout << q.front() << endl; // 1

    q.pop();

    cout << q.front() << endl; // 2

    return 0;

}

스택과 큐 비교

특징	스택 (LIFO)	큐 (FIFO)
요소 추가	push(x) (맨 위에 추가)	push(x) (맨 뒤에 추가)
요소 제거	pop() (맨 위 제거)	pop() (맨 앞 제거)
처리 순서	나중에 들어온 것이 먼저 나감	먼저 들어온 것이 먼저 나감

---

4. 깊이 우선 탐색(DFS)

DFS란?

깊이 우선 탐색(Depth-First Search, DFS)은 그래프 탐색 알고리즘으로, 한 경로를 끝까지 탐색한 후 다른 경로를 탐색합니다.

DFS 탐색 예시

        1

       / \

      2   7

     / \   \

    3   6   11

   / \   \

  4   5   8

         / \

        9   10

C++ DFS 구현:

void dfs(int node) {

    visited[node] = true;

    for (int neighbor : adj[node]) {

        if (!visited[neighbor]) {

            dfs(neighbor);

        }

    }

}

---

결론

• 재귀는 문제를 작은 단위로 쪼개서 해결
• 스택은 LIFO 방식으로 동작
• 큐는 FIFO 방식으로 동작
• DFS는 스택을 사용하여 그래프 탐색 수행

이 개념들은 알고리즘 및 자료 구조에서 매우 중요합니다. 직접 구현해 보세요!