알고리즘은 가격표 붙은 레시피야

"정답은 문 안으로 들여보내 줘. 비용은 네가 머물러도 되는지를 결정하고."

뭐가 알고리즘이 되게 하나

알고리즘은 레시피야: 입력을 출력으로 바꾸는 유한한 잘 정의된 단계 목록. "유한" 이 중요해 — 안 끝나는 레시피는 레시피가 아니라 가스레인지 화재야. "잘 정의됨" 도 중요해 — "간 맞을 만큼 소금" 은 사람 요리사한텐 되지만 기계한텐 쓸모없어, 기계는 "소금 4그램" 이 필요하거든. 모든 단계가 모호하지 않고 실제로 끝낼 수 있어야 해.

이게 지루한 절반이야. 중요한 절반은 이거: 똑같이 정답인 출력을, 가격표가 완전히 다른 레시피들이 만들어낼 수 있어.

레시피 둘, 같은 요리, 다른 계산서

1부터 n까지 모든 수의 합을 원한다고 해. 레시피 A: 0에서 시작해 1 더하고 2 더하고 3 더하고… n 더해. n = 1,000,000 이면 백만 번 덧셈이야. 레시피 B: 수들이 짝지어진다는 걸 눈치채 (1 + n, 2 + n−1, …) 답은 그냥 n * (n + 1) / 2 — n 이 아무리 커도 세 번 연산. 둘 다 동일한 정답을 내. 하나는 백만 단계, 하나는 세 단계.

아홉 살 가우스는 반 친구들이 손으로 레시피 A 를 갈아넣는 동안 레시피 B 를 몇 초 만에 봤다고 해. 천재라서가 아니야 — 당연한 레시피랑 싼 레시피는 보통 같은 레시피가 아니라는 걸 본 거야. 그 눈을 훈련하는 게 이 퀘스트의 목적이야.

두 알고리즘은 똑같이 정답이면서 똑같이 감당 가능하진 않을 수 있어. 정답은 필수고, 비용은 그걸 규모에서 쓸 수 있게 만드는 거야.

왜 '규모에서' 가 이야기 전부인가

n = 10 이면 누가 신경 써 — 둘 다 눈 깜짝하기 전에 끝나. 비용 차이는 입력이 커질 때만 비명을 질러. 네 노트북의 테스트 100줄에선 날쌔다가 프로덕션의 1억 줄에서 죽는 프로그램은 틀린 게 아니었어. 비쌌던 거고, 청구서가 날아올 때까지 아무도 그 값을 안 쟀던 거야. 다음 트랙 Complexity 가 그 가격표를 출시 전에 읽는 도구를 줘.

피파의 고백

난 테스트 통과하는 순간 함수를 "완료" 라고 선언하곤 했어. 아빠의 질문은 매번 똑같았어: "좋아 — 그럼 입력이 천 배 커지면 어떻게 돼?" 절반은 나도 몰랐어, 본 적이 없었으니까. 정답은 날 끝난 기분이 들게 했어; 아빠는 끝났다는 게 정답 더하기 내가 실제로 방어할 수 있는 비용이란 걸 가르쳤어.

Code

백만 단계 vs 세 단계·python

# 같은 정답. 완전히 다른 두 가격표.

def sum_loop(n: int) -> int:
    """레시피 A: 하나씩 더해. n 단계."""
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

def sum_formula(n: int) -> int:
    """레시피 B: 가우스의 짝짓기. 영원히 3 단계."""
    return n * (n + 1) // 2

for n in (10, 1_000_000):
    assert sum_loop(n) == sum_formula(n)   # 동일한 답
    print(n, sum_formula(n))

# sum_loop(1_000_000) 은 백만 번 덧셈을 했어.
# sum_formula(1_000_000) 은 곱 한 번, 합 한 번, 나눗셈 한 번.
# 같은 출력. 계산서는 같지 않아.

Exercise

매일 돌리는 진짜 알고리즘을 적어봐 — 아침 루틴, 출퇴근, 커피 내리는 법 — 잘 정의된 단계 번호 목록으로. 그다음 제일 오래 걸리는 단계 하나에 동그라미 쳐. 입력이 두 배가 되면 (설거지 두 배, 거리 두 배) 어떤 단계가 그대로고 어떤 게 터져?

Hint

모든 항목을 건드리는 단계 (접시 하나하나 닦기) 는 입력 크기에 따라 터지고, 한 번만 일어나는 단계 (주전자 켜기) 는 안 그래. 그 차이가 복잡도의 씨앗이야.

뭐가 알고리즘이 되게 하나

레시피 둘, 같은 요리, 다른 계산서

왜 '규모에서' 가 이야기 전부인가

피파의 고백

Code

External links

Exercise

Progress

댓글 0