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

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

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

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

---

스택 — 브라우저 뒤로가기 버튼

웹서핑을 하다가 뒤로가기를 누르면 정확히 이전 페이지로 돌아가죠.
어떻게 순서를 기억할까요? 바로 스택(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 — 카카오맵이 최단경로를 찾는 원리를 함께 알아봅니다.
오늘 배운 스택과 큐가 거기 그대로 쓰입니다. ㅎㅎ