시작하며 — 알고리즘, 들어보셨죠? ㅎㅎ

릴스를 보다 보면 신기하게도 내가 좋아할 것 같은 영상이 계속 나옵니다.
그게 바로 알고리즘이에요.
AI가 "이 사람은 이걸 좋아하겠다"는 순서를 정해서 콘텐츠를 보여주는 거죠.

그런데 그 알고리즘, 어떻게 만들어질까요?
그 기초 중의 기초가 바로 오늘 배울 스택, 큐, 재귀입니다.

AI 기초수학 3편을 함께 했다면 이제 알고리즘 차례입니다. ㅎㅎ
행렬, 확률을 알았으니 이번엔 컴퓨터가 문제를 어떤 순서로 푸는지 알 차례예요.

---

스택이란 뭔가요?

스택은 "나중에 넣은 것이 먼저 나오는" 후입선출(LIFO) 자료구조예요. 브라우저 뒤로가기, 실행 취소 기능이 대표적인 예시이고, 재귀 호출의 내부 동작도 사실 스택으로 이루어져 있습니다.

웹서핑을 하다가 뒤로가기를 누르면 정확히 이전 페이지로 돌아가죠.
어떻게 순서를 기억할까요? 바로 스택(Stack) 덕분입니다.

스택은 후입선출(LIFO — Last In, First Out) 구조입니다.
책을 쌓아두고 위에서부터 꺼내는 것과 똑같아요.
마지막에 넣은 게 가장 먼저 나옵니다.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty(): return None
        return self.items.pop()

    def peek(self):
        if self.is_empty(): return None
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0


# 브라우저 뒤로가기 시뮬레이션
browser = Stack()
pages = ["google.com", "youtube.com", "heukseom.com"]

print("=== 페이지 방문 ===")
for page in pages:
    browser.push(page)
    print(f"  방문: {page}  →  현재 스택: {browser.items}")

print(f"\n현재 페이지: {browser.peek()}")

print("\n=== 뒤로가기 ===")
for _ in range(2):
    back = browser.pop()
    print(f"  뒤로가기: {back}  →  현재 페이지: {browser.peek()}")

push로 쌓고, pop으로 꺼내면 방문 역순으로 돌아간다

텍스트로 보니 감이 오시죠? 이걸 시각화하면 더 직관적으로 보입니다.

push 할수록 위로 쌓이고, pop은 항상 TOP에서만 — LIFO 구조가 한눈에 보인다

---

큐는 스택이랑 뭐가 다른가요?

카페에서 먼저 온 손님이 먼저 음료를 받죠.
유튜브 재생목록도 앞에 추가한 영상부터 재생됩니다.
이게 큐(Queue)입니다.

큐는 선입선출(FIFO — First In, First Out) 구조입니다.
먼저 들어온 게 먼저 나가요. 스택과 정반대예요.

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty(): return None
        return self.items.popleft()

    def front(self):
        if self.is_empty(): return None
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0


# 카페 주문 시뮬레이션
cafe = Queue()
orders = ["아메리카노", "라떼", "녹차라떼"]

print("=== 주문 접수 ===")
for order in orders:
    cafe.enqueue(order)
    print(f"  주문: {order}  →  대기열: {list(cafe.items)}")

print(f"\n다음 음료: {cafe.front()}")

print("\n=== 음료 제조 완료 ===")
while not cafe.is_empty():
    done = cafe.dequeue()
    print(f"  완료: {done}  →  남은 대기: {list(cafe.items)}")

enqueue로 뒤에 추가, dequeue로 앞에서 꺼낸다 — 먼저 온 손님이 먼저 나간다

IN은 뒤에서, OUT은 앞에서 — 줄서기와 완전히 같은 구조

---

재귀란 뭔가요?

탐색기에서 "전체 검색"을 하면 폴더 안에 폴더가 있어도 끝까지 뒤집니다.
어떻게 할까요? 바로 재귀(Recursion)입니다.
함수가 자기 자신을 다시 호출하는 방식이에요.

팩토리얼로 먼저 감을 잡아봅시다.
4! = 4 × 3 × 2 × 1 = 24 — 이걸 재귀로 표현하면?

def factorial(n, depth=0):
    indent = "  " * depth
    print(f"{indent}factorial({n}) 호출")
    if n <= 1:
        print(f"{indent}→ 반환: 1")
        return 1
    result = n * factorial(n - 1, depth + 1)
    print(f"{indent}→ {n} × factorial({n-1}) = {result}")
    return result


print("=== 팩토리얼 재귀 호출 과정 (n=4) ===\n")
answer = factorial(4)
print(f"\n최종 결과: 4! = {answer}")

factorial(4)가 factorial(3)을 부르고, 또 factorial(2)를 부른다 — 깊이 들어갔다가 올라오는 구조

재귀에는 반드시 두 가지가 있어야 합니다.
① 기저 조건(Base Case) — 언제 멈출지
② 재귀 호출 — 자기 자신을 더 작은 문제로 부르기
이걸 호출 트리로 그려보면 훨씬 명확하게 보입니다.

왼쪽은 깊이 들어가는 호출, 오른쪽은 값을 들고 올라오는 반환 — 재귀의 두 방향

---

하노이 탑은 재귀로 어떻게 풀리나요?

재귀 알고리즘의 대표 문제가 바로 하노이 탑입니다.
규칙은 간단해요.

기둥이 3개(A, B, C) 있고, A에 원판 n개가 작은 게 위에 오도록 쌓여 있습니다.
모든 원판을 C로 옮기되:
① 한 번에 원판 1개만 이동
② 큰 원판이 작은 원판 위에 올라갈 수 없음

def hanoi(n, from_peg, to_peg, aux_peg, step=[0]):
    if n == 1:
        step[0] += 1
        print(f"  [{step[0]:2d}단계] 원판 1 : {from_peg} → {to_peg}")
        return
    hanoi(n - 1, from_peg, aux_peg, to_peg, step)
    step[0] += 1
    print(f"  [{step[0]:2d}단계] 원판 {n} : {from_peg} → {to_peg}")
    hanoi(n - 1, aux_peg, to_peg, from_peg, step)


print("=== 하노이 탑 (원판 3개) ===\n")
hanoi(3, "A", "C", "B")
print(f"\n총 이동 횟수: {2**3 - 1}번  (공식: 2ⁿ - 1)")

원판 3개 → 7단계. 코드는 10줄인데 모든 경우를 자동으로 풀어낸다

원판이 1개 늘어날 때마다 이동 횟수가 어떻게 변할까요?
2ⁿ-1 공식인데, 직접 그려보면 그 무서움이 실감납니다. ㅎㅎ

원판 1개 늘 때마다 이동 횟수가 2배 — 지수적 증가(Exponential Growth)

---

스택과 재귀는 어떤 관계인가요?

사실 재귀와 스택은 같은 겁니다.
파이썬이 재귀 함수를 실행할 때, 내부적으로 콜 스택(Call Stack)을 쌓아요.
함수를 호출할 때마다 스택에 push, 반환할 때마다 pop.

그래서 다음 편에서 배울 DFS(깊이 우선 탐색)이 스택으로 구현되는 겁니다.
"깊이 파고든다" = 스택에 계속 push하면서 들어가고, 막히면 pop해서 돌아오는 거예요.
오늘 배운 큐는 BFS(너비 우선 탐색)에 그대로 쓰이고요.

---

정리

• 스택(LIFO): 마지막에 넣은 게 먼저 나온다 — 브라우저 뒤로가기, 실행취소(Ctrl+Z)
• 큐(FIFO): 먼저 넣은 게 먼저 나온다 — 카페 주문, 유튜브 재생목록
• 재귀: 함수가 자기 자신을 호출 — 기저 조건 필수, 하노이 탑이 대표 예시
• 재귀의 이동 횟수 2ⁿ-1 — 원판 1개 늘 때마다 2배씩 폭발한다
• 스택 = 재귀 콜스택의 실체 — DFS는 스택, BFS는 큐로 구현된다

다음 편에서는 DFS / BFS — 카카오맵이 최단경로를 찾는 원리를 함께 알아봅니다.
오늘 배운 스택과 큐가 거기 그대로 쓰입니다. ㅎㅎ