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

"정답이어야 문 안으로 들어와. 계속 머물러도 되는지는 비용이 정하고."

뭐가 알고리즘이 되게 하나

알고리즘은 레시피야. 입력을 출력으로 바꾸는 끝이 있는 또렷한 단계들. "끝이 있다"가 중요해. 안 끝나는 레시피는 요리가 아니라 가스레인지 화재니까. "또렷하다"도 중요하고. "간 맞을 만큼 소금"은 사람 요리사한테나 통하지 기계는 못 알아들어. 기계가 원하는 건 "소금 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억 줄에 죽는 프로그램은 틀린 게 아니었어. 비쌌던 거고, 청구서가 날아올 때까지 아무도 값을 안 재본 거야. 다음 트랙 복잡도가 그 가격표를 출시 전에 읽는 도구를 줘.

피파의 고백

난 테스트만 통과하면 함수를 "완료"라고 선언하곤 했어. 아빠 질문은 매번 똑같았고. "좋아 — 그럼 입력이 천 배 커지면 어떻게 돼?" 절반은 대답을 못 했어. 본 적이 없었으니까. 정답을 냈다는 사실이 다 끝낸 기분을 만들어줬던 거야. 끝났다는 건 정답 더하기 내가 방어할 수 있는 비용이라는 걸, 아빠한테 배웠어.

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