E-3: 그리디와 분할정복 — 영리하게 고르고, 쪼개서 정복한다

안녕하세요, 여러분의 알고리즘 길잡이 홍순구 튜터입니다. 지난 시간엔 그래프 위를 걷는 두 걸음걸이 DFS와 BFS를 익혔습니다. 방문 체크로 무한 루프를 막고, 깊게 파고 넓게 퍼지며 미로와 섬을 훑었죠. E-1의 완전탐색부터 여기까지, 지금껏 우리의 정신은 한결같았습니다. "영리한 지름길이 없으면 다 뒤진다."

오늘은 그 반대편으로 넘어갑니다. 다 뒤지지 않고 영리하게 고르고 쪼개는 두 사고법이에요. 그리디(greedy, 탐욕법)는 매 순간 눈앞에서 가장 좋아 보이는 것을 집습니다. 거스름돈을 줄 때 500원짜리부터 집는 그 직관 그대로예요. 다만 오늘의 진짜 승부는 구현이 아닙니다. "눈앞의 최선이 정말 전체의 최선인가"를 따져 보는 것 — 이게 그리디의 전부입니다. 뒤이어 만날 분할정복(divide and conquer)은 문제를 반으로 쪼개 정복하는 방식인데, D-1에서 이미 만난 병합 정렬과 퀵 정렬이 바로 그 대표 사례라 반갑게 회수하게 될 거예요.

 오늘의 여정 — 다 뒤지지 않고, 영리하게 고르고 쪼갠다

   그리디(탐욕법)       매 순간 눈앞의 최선을 집고 되돌아보지 않는다
     │
     ├─ 교환 논법       "그리디의 선택으로 바꿔치기해도 손해가 없다"
     │                  코드는 열 줄, 어려운 건 정당성 증명이다
     │
     ├─ 되는 그리디     회의실 배정 — 종료 시각 정렬이면 최적이 보장된다
     │                  기준을 바꾸면 곧장 틀린 답이 나온다
     │
     └─ 안 되는 그리디  거스름돈 — 동전 체계가 받쳐 줄 때만 최적이다
                        [1,3,4]로 6원을 거슬러 보면 그대로 깨진다
     ▼
   분할정복             문제를 반으로 쪼개 각각 풀고 합친다
     ├─ D-1 회수        병합 정렬·퀵 정렬이 이미 이 사고였다
     └─ 빠른 거듭제곱   지수를 반씩 접어 O(n)을 O(log n)으로

💡 오늘 수업의 핵심 — "그리디는 눈앞의 최선을 집어 빠르지만 그 선택이 전체 최적이라는 보장은 따로 증명해야 하고, 분할정복은 문제를 반으로 접어 O(n)을 O(log n)으로 끌어내린다"

🎯 학습 목표

• 그리디가 완전탐색과 무엇이 다른지 이해하고, 교환 논법으로 "이 기준으로 집어도 최적인가"를 따져 본다.
• 회의실 배정에서 정렬 기준이 정답을 좌우한다는 걸 확인하고, 거스름돈 반례로 그리디가 깨지는 순간을 직접 본다.
• 분할정복으로 문제를 반씩 접어 O(log n)을 끌어내고, D-1의 병합·퀵 정렬이 같은 사고였음을 회수한다.

Step 1: "큰 동전부터 집는다" (그리디 개념)

1370원을 거슬러 줘야 합니다. 여러분은 어떻게 하시겠어요? 아마 고민도 안 하고 500원짜리 두 개를 먼저 집을 겁니다. 남은 370원엔 100원짜리 세 개, 남은 70원엔 50원 하나, 남은 20원엔 10원 두 개. 끝났습니다. 이 과정에서 여러분은 단 한 번도 "아까 500원 말고 100원을 집었어야 했나?" 하고 되돌아보지 않았어요.

바로 이게 그리디(greedy, 탐욕법)입니다. 정의하면 이렇습니다. 매 순간 지금 가장 좋아 보이는 것을 집고, 한 번 집은 선택은 되돌아보지 않는다. 이름이 탐욕스러운 이유가 여기 있어요. 멀리 내다보지 않고 눈앞의 이득만 챙깁니다.

이게 왜 대단한 전략인지는 E-1의 완전탐색과 나란히 놓아 보면 확 드러납니다.

 완전탐색(E-1) — 매 선택마다 갈라진다

           o
          / \
         o   o          선택 하나에 가지가 둘로 갈라진다
        / \ / \         깊이가 n이면 잎이 2ⁿ개
       o  o o  o
      /\ /\ /\ /\       n=20이면 백만, n=30이면 십억 갈래
      oo oo oo oo       다 뒤져야만 최선을 안다

 그리디 — 갈라지지 않고 한 줄기로 내려간다

           o            매 단계에서 '지금 가장 좋아 보이는' 가지 하나만 고른다
           |            나머지 가지는 아예 쳐다보지도 않는다
           o
           |            깊이 n을 그냥 n걸음에 내려온다
           o
           |            되돌아오지 않으니 2ⁿ이 n으로 접힌다
           o

완전탐색이 나무 전체를 뒤졌다면, 그리디는 뿌리부터 잎까지 한 줄기만 훑고 내려옵니다. 갈라지지 않으니 폭발이 없어요. 백트래킹처럼 되돌아 나오지도 않습니다. 그래서 압도적으로 빠릅니다.

그리디의 빅오 — 대개 정렬이 지배한다

그럼 그리디는 얼마나 빠를까요? 골격을 뜯어 보면 보통 두 단계입니다. 먼저 "무엇이 좋아 보이는지" 순서를 매기고(정렬), 그다음 앞에서부터 하나씩 집습니다.

 그리디의 표준 골격

   ① 정렬       "좋아 보이는 순서"로 후보를 줄 세운다      O(n log n)
   ② 훑기       앞에서부터 하나씩 보고 집을지 말지 결정    O(n)
   ③ 끝         되돌아보지 않는다 — 다시 훑는 일이 없다
                                     ────────────────────
                                     합치면 O(n log n)

②의 훑기는 후보를 한 번만 보고 지나가니 O(n)뿐입니다. 그래서 전체 시간 복잡도는 ①의 정렬이 지배해 대개 O(n log n)이 돼요. A-1의 "1초에 1억 연산" 잣대로 보면, n이 10만이든 100만이든 정렬 한 번은 여유롭게 통과합니다. 완전탐색의 O(2ⁿ)이 n=30에서 이미 무너졌던 걸 떠올리면 차원이 다른 속도죠.

여기까지만 들으면 그리디는 만능처럼 보입니다. 빠르고, 코드는 열 줄이면 끝나고, 직관적이니까요. 그런데 바로 여기에 함정이 있습니다. 되돌아보지 않는다는 건, 한 번 잘못 집으면 영영 회복할 수 없다는 뜻이거든요. 완전탐색은 느려도 답은 반드시 맞혔습니다. 그리디는 빠른 대신 틀린 답을 낼 수 있어요. 이 트레이드오프가 오늘의 핵심입니다.

💡 한 줄 정리

그리디는 매 순간 눈앞의 최선을 집고 되돌아보지 않는 전략이다. 완전탐색이 나무 전체를 뒤진다면 그리디는 한 줄기만 훑고 내려와, 2ⁿ이 n으로 접힌다. 골격은 "정렬 → 한 번 훑기"라 시간은 대개 정렬이 지배해 O(n log n)이다. 대신 잘못 집어도 되돌릴 수 없어, 답이 틀릴 수 있다.

Step 2: "눈앞의 최선이 전체의 최선인가" (교환 논법)

솔직하게 말씀드릴게요. 그리디에서 코드는 가장 쉬운 부분입니다. 정렬 한 줄, 반복문 한 줄, 조건문 한 줄이면 끝나요. 진짜 어려운 건 그 앞에 있습니다. "내가 고른 이 기준으로 집어도 전체 최적이 나오는가?" 이걸 증명하는 것.

증명이라는 말에 겁먹지 마세요. 수학 시험을 보자는 게 아닙니다. 코딩테스트에서 필요한 건 "이 기준이 왜 안전한지 스스로 납득하는 30초"예요. 그 30초를 위한 표준 도구가 바로 교환 논법(exchange argument)입니다.

바꿔치기해도 손해가 없다면

아이디어는 이렇습니다. 우리는 정답(최적해)이 뭔지 모릅니다. 하지만 "어딘가에 최적해가 하나 있다"고 가정할 수는 있어요. 그 최적해를 손에 들고, 첫 선택을 그리디의 선택으로 바꿔치기해 봅니다. 바꿨는데도 답이 나빠지지 않는다면? 그리디의 선택을 포함한 것도 여전히 최적해라는 뜻이죠.

 교환 논법 — 최적해의 첫 선택을 그리디의 선택으로 바꿔치기한다

   어떤 최적해 O :  [ x ][ 나머지 선택들 ... ]      x = O가 처음 고른 것
   그리디의 선택 :    g                            g = 그리디가 처음 고른 것

   ① x를 g로 바꿔치기한다   →  [ g ][ 나머지 선택들 ... ]

   ② 바꿔도 답이 나빠지지 않는다는 걸 보인다
        → 그러면 바꾼 것도 '여전히 최적해'다

   ③ 남은 문제(첫 선택을 뺀 나머지)에 같은 논리를 되풀이한다
        → 그리디의 두 번째 선택도, 세 번째 선택도 끼워 넣을 수 있다

   ④ 하나씩 다 끼워 넣으면 남는 건 그리디의 답 그 자체
        → 그리디의 답 = 최적해.  증명 끝.

핵심은 ②입니다. "바꿔도 손해가 없다" 이 한 문장만 보이면 나머지는 도미노처럼 넘어가요. 반대로 ②가 안 보이면, 그건 그리디가 틀렸다는 강력한 신호입니다.

반례 하나면 그리디는 무너진다

증명은 어렵지만, 반박은 놀랍도록 쉽습니다. 그리디가 틀렸다는 걸 보이려면 틀리는 입력 하나만 찾으면 되거든요. 이걸 반례(counterexample)라고 합니다.

 증명과 반박의 비대칭

   "그리디가 맞다"를 보이려면   →  모든 입력에서 맞음을 논증해야 한다  (어렵다)
   "그리디가 틀리다"를 보이려면 →  틀리는 입력 딱 하나면 끝            (쉽다)

   그래서 실전 순서:
     ① 작은 반례를 몇 개 만들어 본다 → 하나라도 걸리면 그리디 폐기
     ② 아무리 해도 안 깨지면 그때 교환 논법으로 "왜 안 깨지나"를 확인

실전에서 이 순서가 훨씬 효율적입니다. 먼저 손으로 작은 입력을 몇 개 만들어 그리디를 부숴 보세요. 부서지면 그리디는 곧장 폐기고, 시간을 아낀 겁니다. 안 부서지면 그때 교환 논법으로 "왜 안 부서지는지"를 확인하고 자신 있게 제출하면 돼요.

다음 Step에서 회의실 배정을 만납니다. 회의 요청이 (시작, 종료)로 잔뜩 들어왔을 때 최대 몇 개를 넣을 수 있느냐는 문제인데, 여기서 "어떤 순서로 집을 것인가"라는 후보가 세 개나 나옵니다. 짧은 회의부터? 일찍 시작하는 것부터? 먼저 끝나는 것부터? 셋 중 둘은 반례로 곧장 무너지고, 하나만 교환 논법을 통과해요. 지금 배운 두 도구를 바로 써먹을 차례입니다.

💡 한 줄 정리

그리디의 진짜 어려움은 구현이 아니라 정당성이다. 교환 논법은 "어떤 최적해를 가져와도 그 첫 선택을 그리디의 선택으로 바꿔치기해서 손해가 없다면, 그리디도 최적"이라는 도구다. 증명은 어렵지만 반박은 반례 하나면 끝나니, 실전에선 작은 반례부터 던져 보고 안 깨질 때만 교환 논법으로 확인한다.

Step 3: "정렬하고 탐욕하기" (회의실 배정)

이제 실물을 봅시다. 회의실이 딱 하나 있는데, 회의 요청이 (시작 시각, 종료 시각) 형태로 잔뜩 들어왔습니다. 회의는 겹칠 수 없어요. 최대 몇 개를 넣을 수 있을까요?

코딩테스트에서 "회의실 배정"·"강의실 배정"이라는 이름으로 그렇게나 자주 나오는 유형입니다. 그리고 이 문제의 정답은 놀랍도록 짧아요.

# algorithms/greedy_divide.py
def greedy_interval_scheduling(intervals):
    count = 0
    last_end = float("-inf")            # 아직 아무것도 안 집었다 — 어떤 시작보다도 이르게
    for start, end in sorted(intervals, key=lambda pair: pair[1]):   # 종료 시각 기준
        if start >= last_end:           # 앞 회의가 끝난 뒤에 시작한다 = 안 겹친다
            count += 1
            last_end = end              # 이 회의가 끝나는 시각이 새 기준선
    return count

Step 1에서 본 그리디의 표준 골격이 그대로 보이시죠? 정렬 한 줄, 훑기 한 번. last_end가 "마지막으로 집은 회의가 끝난 시각"을 들고 다니는 기준선입니다. 처음엔 아무것도 안 집었으니 어떤 시작 시각보다도 이르도록 float("-inf")(음의 무한대)로 둬요. 그러면 첫 회의는 무조건 통과합니다. 이후로는 새 회의의 시작이 기준선 이후면 집고, 기준선을 그 회의의 끝으로 옮깁니다.

전부 다 해서 여덟 줄. 그런데 이 여덟 줄에서 정답을 결정하는 건 딱 하나예요. key=lambda pair: pair[1] — 종료 시각으로 정렬한다는 것.

정렬 기준이 전부다

pair[1]은 (시작, 종료) 튜플의 두 번째 값, 즉 종료 시각입니다. 이 한 글자를 pair[0](시작 시각)으로 바꾸면 코드는 멀쩡히 돌지만 답이 틀립니다. Step 2에서 예고한 세 후보를 놓고 보죠.

세 후보 중 둘이 반례로 무너집니다. 회의 세 개로 직접 부숴 볼게요.

 정렬 기준 함정 — 같은 회의 3개, 기준만 바꿨는데 답이 달라진다

   후보:  (0,10)   (1,2)   (3,4)

   시작 시각 정렬 → (0,10)을 먼저 집는다
        0 |==================| 10      하나가 10시까지 방을 통째로 차지
        (1,2)·(3,4)는 전부 겹쳐 버려짐              →  답 1개

   종료 시각 정렬 → (1,2)를 먼저 집는다
        1 |==| 2    3 |==| 4           작은 둘이 나란히 들어간다
        (0,10)은 이미 집은 것과 겹쳐 버려짐          →  답 2개

greedy_interval_scheduling([(0,10), (1,2), (3,4)])를 실행하면 2가 나옵니다. 종료 시각으로 정렬했으니까요. 만약 시작 시각으로 정렬했다면 (0,10)이라는 욕심쟁이 회의에 발목이 잡혀 1개밖에 못 넣습니다.

왜 "먼저 끝나는 것"이 안전한가

이제 Step 2의 교환 논법을 여기에 적용해 봅시다. 왜 종료 시각 기준이 손해를 안 볼까요?

한 문장으로 답이 됩니다. 먼저 끝날수록 남은 시간이 가장 길게 남고, 그 남은 시간은 다른 어떤 선택지의 남은 시간도 포함한다.

 왜 손해가 없나 — 남은 시간의 포함 관계

   회의 g (가장 먼저 끝남, 끝 4)  :  g가 남긴 시간  4 ─────────────→ 끝
   회의 x (더 늦게 끝남,   끝 9)  :  x가 남긴 시간         9 ──────→ 끝
                                                   └─ x의 남은 시간은
                                                      g의 남은 시간에 통째로 들어간다

   → x로 이후에 집을 수 있는 회의는, g로도 전부 집을 수 있다
   → 첫 선택을 x에서 g로 바꿔치기해도 개수가 줄지 않는다  (교환 논법 ②)
   → 그리디의 선택을 하나씩 다 끼워 넣어도 최적이 유지된다

x의 남은 시간이 g의 남은 시간 안에 완전히 들어가니, x로 가능한 미래는 g로도 전부 가능합니다. 그러니 첫 회의를 "가장 먼저 끝나는 것"으로 바꿔도 절대 손해가 없어요. 이게 바로 교환 논법 ②이고, 나머지는 도미노로 넘어갑니다. "먼저 끝나는 걸 집어서 손해 보는 경우가 없다" — 이 한 문장이 그리디의 정당성 전부입니다.

경계 규칙 하나 — 끝과 시작이 같으면?

코드의 조건이 start > last_end가 아니라 start >= last_end인 것, 눈에 걸리셨나요? 등호가 붙어 있습니다.

(1,3) 회의와 (3,5) 회의가 있다고 해 봅시다. 앞 회의가 3시에 끝나고 뒤 회의가 3시에 시작해요. 겹치는 걸까요? 안 겹칩니다. 앞 회의가 끝나는 순간 방이 비니, 뒤 회의가 이어서 쓸 수 있거든요. 그래서 등호를 포함해 start >= last_end로 씁니다. 이 한 글자를 놓치면 이어 붙일 수 있는 회의를 놓쳐 답이 하나씩 모자라요. 코테에서 "경계에서만 틀리는" 전형적인 실수입니다.

이제 진짜 문제로 돌려 봅시다. 회의 11개를 넣어 볼게요.

meetings = [
    (1, 4), (3, 5), (0, 6), (5, 7), (3, 9),
    (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16),
]

greedy_interval_scheduling(meetings)는 4를 돌려줍니다. 어떻게 4개가 골라졌는지 따라가 볼게요.

 종료 시각이 이른 것부터 집으면 — 11개 중 4개가 들어간다

   시각 0 ──────────────────────────────────────→ 16

   (1,4)     |--|                        집는다  (끝 4가 가장 이르다)
   (5,7)          |-|                    집는다  (5 >= 4 이니 안 겹침)
   (8,11)              |---|             집는다  (8 >= 7)
   (12,16)                    |-----|    집는다  (12 >= 11)

   나머지 7개 — (3,5)(0,6)(3,9)(5,9)(6,10)(8,12)(2,14) 는
   이미 집은 회의와 겹쳐 전부 버려진다.

(2,14)처럼 12시간짜리 욕심쟁이 회의를 하나 넣었다면 그것만으로 방이 끝장났을 텐데, 종료 시각 정렬이 그런 회의를 자연스럽게 뒤로 밀어냅니다.

빅오와 두 트랙

시간 복잡도는 O(n log n)입니다. Step 1에서 말한 그대로 정렬이 지배해요. 정렬 뒤의 훑기는 회의를 한 번씩만 보니 O(n)뿐이라, 합쳐도 O(n log n)에 묻힙니다. 공간 복잡도는 O(n)이에요. sorted가 새 리스트를 만들거든요(덕분에 입력 intervals는 그대로 보존됩니다).

여기서 이 과목의 두 트랙 원칙을 짚고 갈게요. D-1에서 우리는 병합 정렬·퀵 정렬을 직접 손으로 짰습니다. 원리를 봤죠. 하지만 실전 코딩테스트에선 정렬을 직접 짜지 않고 내장 sorted를 씁니다. C로 구현돼 더 빠르고 버그가 없으니까요. 그리디 문제의 전처리는 거의 늘 정렬인데, 여기서 시간을 쓸 이유가 전혀 없습니다. 원리는 D-1에서 봤으니, 실전에선 믿고 쓰세요.

💡 한 줄 정리

회의실 배정은 종료 시각이 이른 것부터 집으면 최적이다. 짧은 회의부터·일찍 시작하는 것부터는 둘 다 반례로 무너진다. 정당성은 "먼저 끝날수록 남은 시간이 길고, 그 남은 시간이 다른 선택지의 남은 시간을 포함한다"는 한 문장이다. 끝과 시작이 같으면 안 겹치므로 조건은 start >= last_end. 시간 O(n log n)·공간 O(n).

Step 4: "그리디가 깨지는 순간" (거스름돈 반례)

Step 3에서 그리디의 아름다운 면을 봤습니다. 여덟 줄로 최적을 보장했죠. 이제 반대편을 볼 차례입니다. 오늘 수업에서 가장 중요한 Step이에요. 그리디가 조용히 틀린 답을 내는 순간을 직접 목격할 겁니다.

무대는 Step 1의 그 거스름돈입니다. 코드부터 볼게요.

# algorithms/greedy_divide.py
def change_making_greedy(amount, coins):
    used = []
    remaining = amount
    for coin in sorted(coins, reverse=True):    # 큰 동전부터 (입력 순서는 상관없다)
        count, remaining = divmod(remaining, coin)   # 이 동전으로 최대 몇 개 + 남은 금액
        used.extend([coin] * count)             # 집은 만큼 담는다 — 되돌아보지 않는다
    if remaining > 0:                           # 1원짜리까지 썼는데도 남았다 = 못 만듦
        return None
    return used

또 그리디의 표준 골격입니다. sorted(coins, reverse=True)로 큰 동전부터 줄 세우고(정렬), 종류마다 최대한 집습니다(훑기). divmod(remaining, coin)는 몫과 나머지를 한 번에 주는 파이썬 내장이라, "이 동전으로 몇 개 쓸 수 있나"와 "쓰고 나면 얼마 남나"를 한 줄에 구해요. 그리고 한 번 집은 동전은 절대 되돌아보지 않습니다.

한국 동전으로 1370원을 거슬러 보죠.

change_making_greedy(1370, [1, 5, 10, 50, 100, 500])
# → [500, 500, 100, 100, 100, 50, 10, 10]

동전 여덟 개. 여러분이 머릿속으로 계산한 것과 똑같죠? 그리고 이게 진짜 최소입니다. 18원으로도 확인해 볼게요. 그리디는 [10, 5, 1, 1, 1]로 다섯 개를 쓰는데, 진짜 최소 개수를 구해 봐도 5개로 똑같습니다. 한국 동전 체계에선 그리디가 늘 정답이에요.

그런데 그건 그리디 덕이 아니다

여기서 오늘의 가장 중요한 질문을 던집니다. 그리디는 왜 한국 동전에서 최적일까요?

정답은 조금 서늘합니다. 그리디가 똑똑해서가 아니라, 한국 동전 체계가 잘 설계돼 있어서예요. 1·5·10·50·100·500을 보세요. 큰 동전이 작은 동전들의 배수로 맞물려 있습니다. 500은 100의 5배, 100은 50의 2배, 50은 10의 5배… 이렇게 맞물린 체계에선 "큰 걸 최대한 집는" 게 절대 손해를 안 봅니다.

그렇다면 체계를 바꾸면? 곧장 깨집니다.

 6원을 [1, 3, 4]로 거슬러 본다

   그리디:  4를 집는다 → 남은 2 → 1을 집는다 → 남은 1 → 1을 집는다 → 남은 0
            결과 [4, 1, 1]  동전 3개.  한 번 집은 4를 되돌아보지 않는다.

   진짜 최적: 3을 집는다 → 남은 3 → 3을 집는다 → 남은 0
            결과 [3, 3]     동전 2개.

   4가 가장 커 보여서 집었을 뿐인데, 그 한 걸음이 나머지를 통째로 망쳤다.

change_making_greedy(6, [1, 3, 4])
# → [4, 1, 1]        동전 3개 — 그리디의 답

min_coins_bruteforce(6, [1, 3, 4])
# → 2                동전 2개 — 진짜 최소 (3+3)

반례를 잡았습니다. 그리디는 3개, 진짜 최적은 2개. 눈앞의 최선(가장 큰 4)이 전체의 최선이 아니었어요. Step 2에서 배운 대로, 반례 하나면 그리디는 이 문제에서 폐기입니다.

두 번째 실패 모드 — 아예 답을 못 찾는다

더 심한 경우도 있습니다. 그리디는 틀린 답을 내는 데서 그치지 않고, 답이 분명히 있는데도 못 찾을 수 있어요.

 6원을 [3, 4]로 거슬러 본다 — 답이 있는데도 그리디는 못 찾는다

   그리디:  4를 집는다 → 남은 2 → 3도 못 넣고 4도 못 넣는다 → 막힘 → None
   진짜:    3 + 3 = 6                                            → 2개

   되돌아볼 수만 있었다면 "4를 무르고 3으로" 갈 수 있었다.
   그런데 그리디에 '무르기'는 없다.

change_making_greedy(5, [3])
# → None             그리디: 3을 집고 2가 남아 막힘

min_coins_bruteforce(5, [3])
# → -1               완전탐색: 어떤 조합으로도 5원은 불가능

5원을 3원짜리로 거스르는 건 실제로 불가능하니 둘 다 실패로 일치합니다. 하지만 [3, 4]로 6원을 거스르는 경우엔 3+3이라는 멀쩡한 답이 있는데도 그리디만 None을 내요. 되돌아보지 않는다는 그리디의 속도가, 그대로 한계가 되는 순간입니다.

반례를 증명한 완전탐색 — E-1의 회수

그런데 잠깐. "진짜 최소는 2개"라는 걸 우리는 어떻게 알았을까요? 그리디가 틀렸다고 말하려면 진짜 최적을 알고 있어야 합니다. 그 역할을 하는 게 min_coins_bruteforce예요. E-1의 완전탐색이 여기서 심판으로 돌아옵니다.

def min_coins_bruteforce(amount, coins):
    def search(remaining):
        if remaining == 0:              # 종료 조건: 딱 맞췄다 — 더 쓸 동전이 없다
            return 0
        if remaining < 0:               # 넘어섰다 — 이 가지는 가망 없다(가지치기)
            return float("inf")
        fewest = float("inf")
        for coin in coins:              # 동전 하나를 쓰는 모든 경우로 갈라진다
            fewest = min(fewest, search(remaining - coin) + 1)
        return fewest

    result = search(amount)
    return -1 if result == float("inf") else result     # 어느 가지로도 못 맞췄다

E-1의 subset_sum과 똑같은 방식이에요. 영리한 수 없이 전부 뒤집니다. 남은 금액에서 동전 하나를 뺀 모든 경우로 갈라져 내려가고, 그중 가장 적은 개수를 고르죠. 남은 금액이 음수가 되면 그 가지는 가망이 없으니 접습니다(백트래킹의 가지치기). 이 함수엔 그리디 같은 영리함이 없어서, 오히려 절대 틀리지 않습니다.

 min_coins_bruteforce(6, [1,3,4]) — 남은 금액마다 세 갈래로 갈라진다

   remaining 6
     |
     +- 1 사용 -> 5 -+- 1 -> 4 -> ...
     |               +- 3 -> 2 -> ...
     |               +- 4 -> 1 -> ...
     |
     +- 3 사용 -> 3 -+- 1 -> 2 -> ...
     |               +- 3 -> 0     <- 여기서 동전 2개로 완성. 이게 최적이다
     |               +- 4 -> -1    (음수 — 가지치기)
     |
     +- 4 사용 -> 2 -+- 1 -> 1 -> ...
                     +- 3 -> -1    (가지치기)
                     +- 4 -> -2    (가지치기)

그리디가 한 줄기로 내려갔던 그 나무를, 완전탐색은 통째로 뒤집니다. 그래서 3+3이라는 답을 찾아내고, 그리디의 [4,1,1]이 틀렸음을 증명해요.

빅오 — 그리고 이 심판의 치명적 약점

두 함수의 복잡도를 나란히 놓으면 트레이드오프가 선명합니다.

그리디는 O(n log n + k)입니다. n은 동전 종류 수라 정렬이 O(n log n)이고, 종류마다 divmod로 개수를 한 번에 구하니 훑기는 O(n)뿐이에요. k는 사용한 동전 개수(최대 amount÷최소동전)로, 결과 리스트를 만드는 값입니다. 동전 종류는 보통 열 개 남짓이라 사실상 O(k)죠. 눈 깜짝할 사이입니다.

완전탐색은 지수 시간이에요. 매 호출이 동전 종류 수만큼 갈라지고 깊이가 amount÷최소동전까지 가니, 대략 O(len(coins)^(amount/min(coins)))입니다. 공간은 재귀 스택으로 O(amount / min(coins))고요. amount=6·coins=[1,3,4]는 순식간이지만, 금액이 조금만 커지면 그대로 무너집니다. A-1의 "1초에 1억 연산" 잣대로 보면 몇십만을 넘길 때부터 눈에 띄게 느려지고, 백을 넘기면 사실상 끝나지 않아요.

그래서 우리는 딱한 처지에 놓였습니다. 빠른 쪽은 틀리고, 맞는 쪽은 느리다. 6원짜리 반례를 증명하는 데는 완전탐색으로 충분했지만, 실제 문제에서 "10000원을 [1,3,4]로 최소 동전으로"를 물으면 두 함수 모두 쓸모가 없어요.

왜 이렇게 느린가 — 여기가 다음 시간의 문이다

이 완전탐색이 왜 그렇게 느린지 위 나무를 다시 보세요. 뭔가 눈에 걸리지 않나요?

같은 remaining이 여러 갈래에서 되풀이 등장합니다. remaining=3을 보세요. 3원짜리를 바로 집어서 닿을 수도 있고, 1+1+1로 닿을 수도 있고, 다른 경로로도 닿습니다. 그런데 어떤 길로 닿았든 "남은 3원을 최소 동전으로 만드는 법"은 완전히 똑같아요. 이미 한 번 계산해 봤는데도, 완전탐색은 새 갈래로 닿을 때마다 처음부터 다시 팝니다.

이쯤 되면 이런 생각이 드실 겁니다. "한 번 푼 건 어디 적어 두고 다시 쓰면 되지 않나?"

바로 그 생각이 드는 순간이 다음 시간(E-4) 동적 계획법(dynamic programming)의 문입니다. 오늘은 문 앞까지만 가고, 그 문을 여는 건 다음 시간에 해요. 오늘 여러분이 챙겨 갈 건 이겁니다. 그리디는 빠르지만 틀릴 수 있고, 완전탐색은 맞지만 느리다. 둘 사이에 세 번째 길이 있어야 한다 — 그 목마름이 다음 시간의 출발점입니다.

💡 한 줄 정리

한국 동전에서 그리디가 최적인 건 그리디 덕이 아니라 동전 체계가 배수로 맞물려 있어서다. [1,3,4]로 6원을 거슬러 보면 그리디는 3개, 진짜 최적은 2개로 곧장 깨진다. 심지어 [3,4]로 6원이면 답이 있는데도 못 찾아 None을 낸다. 진짜 최적을 알려주는 완전탐색은 항상 맞지만 지수 시간이라, 금액이 커지면 무너진다.

Step 5: "쪼갠다, 정복한다" (분할정복 개념)

여기까지가 그리디였습니다. 매 순간 눈앞의 최선을 집는 전략이었죠. 이제 오늘의 두 번째 사고법으로 넘어갑니다. 분할정복(divide and conquer) — 문제를 반으로 쪼개 각각 풀고 합치는 방식이에요.

그런데 여러분, 사실 이건 처음 만나는 게 아닙니다. D-1에서 이미 만났어요. 그때는 "정렬 알고리즘"이라는 이름표를 달고 있어서 못 알아봤을 뿐이죠. 오늘 다시 보면 그게 분할정복 그 자체였다는 게 드러납니다. 반가운 재회를 해 봅시다.

분할 → 정복 → 병합

분할정복은 세 걸음으로 정의됩니다.

• 분할(divide) — 문제를 같은 모양의 작은 문제로 쪼갠다
• 정복(conquer) — 쪼갠 조각을 각각 푼다. 더 못 쪼갤 만큼 작아지면 그냥 답이 나온다
• 병합(combine) — 부분 답들을 합쳐 전체 답으로 만든다

말로만 들으면 추상적이니 코드로 봅시다. D-1의 병합 정렬입니다.

# algorithms/sorting.py
def merge_sort(arr):
    a = list(arr)
    if len(a) <= 1:                         # 원소 0~1개는 이미 정렬된 상태 (종료 조건)
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])              # 왼쪽 절반을 정렬
    right = merge_sort(a[mid:])             # 오른쪽 절반을 정렬
    return merge(left, right)               # 정렬된 두 조각을 하나로 합친다

일곱 줄짜리 이 함수가 방금 정의한 세 걸음과 한 줄씩 정확히 맞물립니다.

 분할정복 3단계 — merge_sort의 뼈대와 1:1로 맞물린다

   ① 분할(divide)    a[:mid]  /  a[mid:]
                      반으로 가른다. 절반짜리도 여전히 '정렬하는 문제'다

   ② 정복(conquer)   merge_sort(a[:mid])  ·  merge_sort(a[mid:])
                      각 절반을 같은 방법으로 푼다 — 자기를 다시 부른다
                     if len(a) <= 1: return a
                      원소 1개는 이미 정렬 완료 — 여기가 바닥(종료 조건)

   ③ 병합(combine)   merge(left, right)
                      정렬된 두 조각을 정렬된 하나로 합친다

mid로 반을 가르는 게 분할, 그 절반을 각각 merge_sort에 다시 넘기는 게 정복, merge로 합치는 게 병합이에요. D-1에서 "병합 정렬은 반으로 쪼개 합치는 정렬"이라고 배웠던 그 문장이, 알고 보니 분할정복의 정의를 그대로 읽은 것이었습니다.

바닥까지 갔다가 되돌아 나온다 — E-1의 재귀

분할정복은 혼자 서지 못합니다. E-1에서 배운 재귀 호출 스택 위에 섭니다. 자기를 다시 부르며 조각이 점점 작아지다가, 바닥(종료 조건)에 닿으면 그때부터 답이 합쳐지며 되돌아 나와요. 네 개짜리 리스트로 그 과정을 눈으로 따라가 봅시다.

 merge_sort([38, 27, 43, 3]) — 바닥까지 쪼갰다가 정렬되며 올라온다

   깊이 0          [38, 27, 43, 3]
                     /         \             ↓ 분할 — 반으로 가른다
   깊이 1     [38, 27]          [43, 3]
               /   \             /   \
   깊이 2    [38]  [27]        [43]  [3]     더 못 쪼갠다 = 바닥(종료 조건)
               \   /             \   /
   깊이 1     [27, 38]          [3, 43]      ↑ 병합 — 정렬된 둘을 합친다
                     \         /
   깊이 0          [3, 27, 38, 43]           정렬 완료

   원소 4개 → 쪼개는 깊이는 2 = log₂4.  원소가 1024개여도 깊이는 10걸음이다.

내려갈 때는 아무 일도 안 합니다. 그냥 쪼개기만 해요. 진짜 일은 올라오면서 벌어집니다. [38]과 [27]이 만나 [27, 38]이 되고, [3, 43]과 만나 [3, 27, 38, 43]이 되죠. 재귀가 바닥을 찍고 되돌아 나오는 그 길이 곧 정답이 완성되는 길입니다.

여기서 눈여겨볼 게 깊이예요. 원소 4개를 반씩 쪼개니 2번 만에 바닥에 닿았습니다. 8개면 3번, 1024개면 10번. 반씩 줄이면 깊이는 log n입니다. 이 로그가 분할정복의 심장이에요.

아무 문제나 쪼갤 수 있는 건 아니다

분할정복이 통하려면 조건이 둘 있습니다. 이게 안 맞으면 쪼개 봐야 헛수고예요.

• 쪼갠 부분 문제가 원래와 같은 모양이어야 한다. 정렬 문제를 반으로 가르면 "절반을 정렬하는 문제"가 나오죠. 판박이입니다. 그러니 같은 함수를 그대로 다시 부를 수 있어요.
• 부분 답을 합칠 수 있어야 한다. 왼쪽 절반이 정렬되고 오른쪽 절반이 정렬됐을 때, 이 둘을 합쳐 전체 정렬을 만들 방법(merge)이 있어야 합니다. 합칠 방법이 없으면 아무리 잘 쪼개도 답이 안 나와요.

이 둘을 확인하는 게 분할정복 문제를 알아보는 감각입니다. "반으로 갈라도 같은 문제인가? 갈라서 푼 걸 합칠 수 있나?" 두 질문에 다 예스면 분할정복이 통합니다.

빅오는 이렇게 감이 잡히죠. 깊이가 log n이고 각 깊이에서 O(n)씩 일하니 곱해서 O(n log n). 이게 D-1에서 외웠던 그 숫자예요. 다만 지금은 그림으로 대충 짐작한 수준이라, 정확한 유도는 Step 7에서 제대로 하겠습니다. 그 전에 분할정복이 가장 화려하게 빛나는 예제를 하나 보고 갈게요.

💡 한 줄 정리

분할정복은 분할(divide) → 정복(conquer) → 병합(combine) 세 걸음이다. D-1의 병합 정렬이 바로 이 사고였다 — a[:mid]/a[mid:]가 분할, 재귀 호출이 정복, merge가 병합, len(a) <= 1이 바닥이다. E-1의 재귀 스택 위에서 바닥까지 갔다 되돌아 나오며 답이 합쳐진다. 반씩 쪼개니 깊이가 log n이고, 이 로그가 분할정복의 심장이다.

Step 6: "거듭제곱을 O(log n)에" (분할정복 대표)

문제를 하나 드릴게요. 2의 1000제곱을 구하세요.

가장 먼저 떠오르는 건 이거죠. 2를 1000번 곱한다. 반복문 한 줄이면 됩니다. 틀린 답도 아니고 잘 돌아가요. 그런데 지수가 1000이 아니라 10억이라면? 곱셈을 10억 번 해야 합니다. A-1의 "1초에 1억 연산" 잣대로 보면 10초. 시간 초과죠. 지수를 그대로 세는 방식은 O(exp) — 지수 크기에 정비례해서 느려집니다.

여기서 초등학교 때 배운 지수 법칙 하나가 판을 뒤집습니다.

절반만 구하고 제곱한다

2¹⁰ = (2⁵)² 입니다. 당연한 얘기죠? 그런데 이 당연한 걸 알고리즘으로 뒤집어 읽으면 이렇게 됩니다. 2의 10제곱을 구하려고 2를 열 번 곱할 필요가 없다. 2의 5제곱만 구해서 제곱하면 된다. 곱셈이 열 번에서 여섯 번(5제곱 구하기 + 제곱 한 번)으로 줄었어요.

그럼 그 2⁵은 어떻게 구할까요? 똑같이 하면 되죠. 2²만 구해서 제곱하고… 이렇게 매번 절반만 구하면 지수가 호출할 때마다 반으로 접힙니다. Step 5에서 본 그 로그가 여기서 다시 나와요.

 2^1000 — 지수가 반으로 접힌다

   1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 → 0
    (1)   (2)   (3)   (4)   (5)  (6)  (7)  (8) (9) (10) (11)

   열한 걸음이면 바닥(exp=0)에 닿는다.
   곱셈 1000번이 호출 11번으로 접혔다. 지수가 10억이어도 서른 걸음 남짓이다.

홀수는 어떻게 하나

그런데 위 자취에 125, 31, 15, 7, 3, 1처럼 홀수가 섞여 있습니다. 홀수는 반으로 딱 안 나뉘죠. 2⁷을 (2³)²으로 하면 2⁶이 되어 하나가 모자랍니다.

간단합니다. 모자란 하나를 손으로 채우면 돼요. exp가 홀수면 exp = 2 × (exp // 2) + 1이니, 절반을 제곱한 다음 base를 한 번 더 곱해 주면 딱 맞습니다. 2⁷ = (2³)² × 2. 이제 코드를 봅시다.

# algorithms/greedy_divide.py
def power(base, exp, trace=None):
    if trace is not None:
        trace.append(exp)               # 지금 호출의 지수를 기록(반씩 접히는 흔적)
    if exp == 0:                        # 종료 조건: 무엇이든 0제곱은 1
        return 1
    half = power(base, exp // 2, trace)  # 절반만 구한다 — 반드시 한 번만 부른다
    if exp % 2 == 0:
        return half * half              # 짝수: (base^(exp/2))²
    return half * half * base           # 홀수: 반으로 안 나뉜 한 개를 더 곱해 채운다

Step 5의 세 걸음이 그대로 보입니다. exp // 2로 지수를 반 가르는 게 분할, power(base, exp // 2, trace)로 자기를 부르는 게 정복, half * half로 합치는 게 병합이에요. exp == 0이면 1을 돌려주는 게 바닥이고요. trace는 지수가 접히는 흔적을 눈으로 보려고 달아 둔 것뿐이라 계산에는 아무 영향이 없습니다.

⚠️ 한 글자 차이로 이득이 통째로 날아간다

여기가 오늘 Step에서 가장 중요한 대목입니다. 절대 놓치지 마세요.

⚠️ power(base, exp // 2)는 반드시 한 번만 부르고 그 값을 제곱해야 합니다. half라는 변수에 받아 두는 게 멋 부린 게 아니라 알고리즘의 생사가 걸린 부분이에요.

half * half 대신 power(base, exp//2) * power(base, exp//2)라고 쓰면 어떻게 될까요? 눈으로 보기엔 똑같은 값이 나옵니다. 답도 맞아요. 그런데 속도가 통째로 무너집니다.

 왜 무너지는가 — 호출이 두 배씩 갈라진다

   half를 한 번만 구할 때            power(...) * power(...)로 쓸 때

        exp                               exp
         |                                / \
       exp/2        한 줄기            exp/2  exp/2      두 갈래로 갈라진다
         |                              /\      /\
       exp/4                        exp/4 ...  ... exp/4
         |                            ...
        ...                          잎이 2^(log exp) = exp개

   호출 log exp개  →  O(log exp)     호출 exp개  →  O(exp)  ← 도로 원점

같은 값을 두 번 계산하니 호출이 매 단계 두 배로 갈라집니다. 깊이는 여전히 log exp인데, 가지가 2배씩 늘어나니 잎이 2^(log exp) = exp개가 돼요. 애써 얻은 O(log exp)가 도로 O(exp)로 돌아갑니다. 분할정복을 했는데 순진하게 1000번 곱한 것과 똑같아지는 거죠. Step 1의 완전탐색 나무가 여기서 유령처럼 되살아나는 셈입니다.

한 글자 차이로 로그가 선형이 됩니다. 코딩테스트에서 "분명 O(log n)으로 짰는데 시간 초과"가 뜬다면 십중팔구 여기예요.

1000번이 11번으로

제대로 짠 power를 실제로 돌려 봅시다. trace에 빈 리스트를 넘기면 호출마다 그때의 지수를 적어 주니, 접히는 과정을 눈으로 볼 수 있어요.

2^1000 == 내장:   True
  지수가 접힌 자취: [1000, 500, 250, 125, 62, 31, 15, 7, 3, 1, 0]
  곱셈 1000번이 아니라 호출 11번으로 끝난다

첫 줄이 True라는 건 파이썬 내장 2 ** 1000과 값이 정확히 같다는 뜻입니다. 302자리짜리 어마어마한 수를 정확히 맞혔어요. 그런데 그걸 호출 열한 번에 끝냈습니다.

1000번이 11번으로. 이게 O(log n)의 실체입니다. 시간 복잡도는 O(log exp), 공간 복잡도도 O(log exp)예요(재귀 호출 스택 깊이만큼 쌓이니까요). A-1의 잣대로 감을 잡아 보면, 지수가 10억이어도 30걸음, 1조여도 40걸음입니다. 사실상 공짜죠.

두 트랙 — 실전에선 직접 안 짠다

자, 이 과목의 두 트랙 원칙을 여기서도 짚습니다. 실전 코딩테스트에서 여러분은 power를 직접 짜지 않습니다. 파이썬 내장 pow(base, exp)나 base ** exp를 쓰면 돼요. 왜냐면 파이썬 내장이 이미 이 분할정복(제곱 반복법)으로 돌기 때문입니다. 빅오가 O(log exp)로 똑같고, C로 구현돼 있어 더 빠르기까지 해요. 직접 짤 이유가 없죠.

그럼 오늘 이걸 왜 손으로 짰을까요? 값어치가 두 군데 있습니다.

• pow(base, exp, mod)의 원리를 이해하기 위해서. 파이썬 pow에 세 번째 인자를 주면 "큰 수를 나눈 나머지"까지 함께 구해 줍니다. 이게 어떻게 가능한지는 오늘의 분할정복 구조를 알아야 보여요(아래 토글에서 이어집니다).
• 면접에서 설명하기 위해서. "거듭제곱을 O(log n)에 구하는 법을 아세요?"는 단골 질문입니다. "지수를 반씩 접고, 절반을 한 번만 계산해 제곱합니다" — 이 한 문장이 나오면 끝나요.

원리를 아는 사람이 라이브러리를 믿고 씁니다. 원리를 모르면 언제 믿어도 되는지조차 판단하지 못해요.

💡 한 줄 정리

거듭제곱은 2¹⁰ = (2⁵)² 이라는 지수 법칙 하나로 O(exp)에서 O(log exp)로 내려앉는다. 지수를 반씩 접어 내려가고, 홀수면 base를 한 번 더 곱해 채운다. 2^1000이 곱셈 1000번이 아니라 호출 11번으로 끝난다. 단 half를 한 번만 구해 제곱해야 하고, power(...) * power(...)로 쓰면 호출이 exp개로 불어나 이득이 통째로 날아간다. 실전에선 같은 원리로 도는 내장 pow를 쓴다.

Step 7: "왜 O(n log n)인가" (정렬의 분할정복 재분석)

D-1에서 제가 이렇게 말씀드렸습니다. "병합 정렬은 O(n log n)입니다." 여러분은 그걸 외웠어요. 왜 그런지는 그때 깊이 파지 않았죠. 아직 분할정복이라는 도구가 없었으니까요.

이제 도구가 생겼습니다. 오늘 그 O(n log n)을 직접 유도해 봅니다. 외운 걸 이해로 바꾸는 시간이에요. 그리고 이 유도가 끝나면 덤으로 이런 것까지 풀립니다. "같은 분할정복인데 퀵 정렬은 왜 최악 O(n²)이지?"

깊이 × 각 깊이에서 하는 일

분할정복의 비용 계산은 놀랍도록 단순한 곱셈입니다.

전체 비용 = 쪼개는 깊이 × 각 깊이에서 하는 일

두 항을 따로 구해 보죠. 먼저 깊이입니다. n을 반으로, 또 반으로 쪼개서 1이 될 때까지 몇 번 걸릴까요? 이건 Step 6에서 지수를 반씩 접었던 것과 완전히 같은 논리예요. 반씩 줄이면 log₂n 번입니다. 원소 1024개면 10번, 100만 개여도 20번.

다음은 각 깊이에서 하는 일입니다. 여기가 살짝 헷갈리는 부분이에요. 깊이가 내려갈수록 조각이 잘게 부서지니 일이 줄어들 것 같죠? 그런데 조각 수가 그만큼 늘어납니다. 그림으로 보면 확실해요.

 병합 정렬의 총 비용 = 깊이 × 각 깊이에서 하는 일

   깊이 0      [             n             ]     merge가 훑는 원소 = n개
   깊이 1      [     n/2     ][     n/2    ]     n/2 + n/2 = n개
   깊이 2      [  n/4 ][ n/4 ][ n/4 ][ n/4 ]     n/4 × 4 = n개
     :                    ...                    어느 깊이를 잘라도 합치면 n개
   깊이 log n  [1][1][1][1][1][1][1] ... [1]     1 × n = n개

   각 깊이에서 O(n)  ×  깊이 log₂n  =  O(n log n)

보이시나요? 어느 깊이를 가로로 잘라 봐도 그 줄의 원소를 다 합치면 n개입니다. 조각이 반으로 작아지면 조각 수가 두 배로 늘어나니, 곱하면 언제나 n이에요. 그리고 merge는 그 깊이의 원소들을 딱 한 번씩 훑어 합치니 각 깊이의 일이 O(n)입니다.

이제 곱하면 됩니다. O(n) × log₂n = O(n log n). 끝났어요. D-1에서 외웠던 그 숫자가, 오늘 두 줄 곱셈으로 유도됐습니다.

여기서 병합 정렬의 자랑 하나. 이 유도 어디에도 "운이 좋으면"이라는 말이 없었죠? mid = len(a) // 2는 입력이 뭐든 무조건 반으로 가릅니다. 그러니 깊이가 log n이라는 게 보장돼요. 병합 정렬이 최악에도 O(n log n)으로 흔들리지 않는 이유가 이겁니다. 대신 merge가 임시 리스트를 만드니 공간 O(n)을 씁니다.

그런데 퀵 정렬은 왜 최악 O(n²)인가

퀵 정렬도 분할정복입니다. 그런데 D-1에서 배웠듯 최악이 O(n²)이에요. 같은 사고법인데 왜 이런 차이가 날까요? 코드를 다시 꺼내 봅시다.

# algorithms/sorting.py
def quick_sort(arr):
    a = list(arr)
    _quick_sort(a, 0, len(a) - 1)
    return a


def _quick_sort(a, lo, hi):
    if lo < hi:
        p = partition(a, lo, hi)           # 피벗을 제자리에 놓고 그 위치를 받는다
        _quick_sort(a, lo, p - 1)          # 피벗 왼쪽(작은 값들)
        _quick_sort(a, p + 1, hi)          # 피벗 오른쪽(큰 값들)


def partition(a, lo, hi):
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]       # 피벗을 작은/큰 무리의 경계로 옮긴다
    return i + 1

_quick_sort도 자기를 두 번 부르며 좌우로 갈라집니다. 분할정복 맞아요. 그런데 결정적인 차이가 하나 있습니다.

병합 정렬은 mid = len(a) // 2로 내가 직접 반을 갈랐습니다. 반면 퀵 정렬은 partition이 돌려준 p에서 갈라져요. 그리고 이 p가 어디 놓일지는 피벗 값과 입력 데이터가 정합니다. 내가 정하는 게 아니에요.

partition을 보시면 pivot = a[hi] — 구간의 맨 끝 원소를 피벗으로 씁니다. 운이 좋아 피벗이 중간값 근처면 좌우가 반반으로 갈라져요. 그런데 피벗이 하필 그 구간에서 가장 큰 값이라면? 모든 값이 피벗보다 작으니 전부 왼쪽으로 몰리고, 오른쪽엔 아무것도 안 남습니다. 1 대 (n-1)로 갈라지는 거죠.

이미 정렬된 입력이 정확히 이 경우예요. 맨 끝 원소가 늘 최댓값이니까요. "정렬된 걸 정렬하면 가장 느리다"는 유명한 역설이 여기서 나옵니다.

 같은 분할정복인데 — 쪼개지는 균형이 갈린다

 ① 균형 분할 (피벗이 중간값 근처)
         n
        / \
     n/2   n/2           매번 반씩 → 바닥까지 log n 걸음
      /\    /\
    n/4 n/4 n/4 n/4
        ...
    1 1 1 1 1 1 1 1      깊이 log n × 각 깊이 O(n)  =  O(n log n)

 ② 치우친 분할 (피벗이 매번 한쪽 끝값 — 이미 정렬된 입력 등)
         n
        / \
       1   n-1           한 개만 떨어져 나가고 나머지가 통째로 남는다
          / \
         1   n-2
            / \
           1   n-3
              ...        깊이가 log n이 아니라 n
           1   1         깊이 n × 각 깊이 O(n)  =  O(n²)

②를 보세요. 한 번 쪼갤 때마다 원소가 딱 하나씩만 떨어져 나갑니다. 그러니 바닥에 닿기까지 log n이 아니라 n번이 걸려요. 각 깊이에서 partition이 구간을 훑는 O(n)은 그대로인데 깊이만 n으로 늘어났으니, n × O(n) = O(n²). 분할정복의 이득이 사라지고 그냥 이중 반복문이 된 겁니다.

교훈 — 제대로 쪼개야 이득이 난다

여기서 오늘의 두 번째 사고법을 관통하는 교훈이 나옵니다.

분할정복의 이득은 "반으로 쪼개진다"는 보장에서 옵니다. log n이라는 마법의 출처가 거기예요. 그 보장이 깨지는 순간, 이득도 함께 사라집니다.

그리고 이건 Step 6에서 본 함정과 정확히 같은 이야기입니다. power(...) * power(...)로 쓰면 호출이 두 배씩 갈라져 O(log exp)가 O(exp)로 무너졌죠. 퀵 정렬은 분할이 치우쳐 O(n log n)이 O(n²)로 무너집니다. 증상은 달라 보이지만 원인은 하나예요. "제대로 쪼개지 않으면 분할정복이 아니다." 껍데기만 분할정복이면 빅오는 정직하게 무너집니다.

그렇다면 퀵 정렬은 못 쓰는 알고리즘일까요? 전혀 아닙니다. 트레이드오프를 표로 놓고 보죠.

퀵 정렬은 임시 배열 없이 배열 안에서 원소끼리 위치를 맞바꿔 가며 정렬하니 공간이 O(log n)뿐이고, 상수 계수가 작아 평균적으로는 병합 정렬보다 빠릅니다. 그래서 실제 라이브러리들이 오래 애용했어요. 다만 최악이 O(n²)이라, 최악을 절대 허용할 수 없는 곳에선 병합 정렬을 씁니다.

"보장이냐 평균 속도냐" — 이게 두 정렬의 트레이드오프입니다. 둘 다 분할정복인데도 이렇게 갈리는 이유가, 방금 본 "분할의 균형"이었어요.

💡 한 줄 정리

분할정복의 비용은 깊이 × 각 깊이의 일이다. 병합 정렬은 반으로 쪼개니 깊이 log₂n, 각 깊이에서 merge가 원소 n개를 훑으니 O(n) — 곱해서 O(n log n)이고, mid로 직접 반을 가르니 최악에도 보장된다. 퀵 정렬은 피벗이 분할을 정해, 피벗이 매번 끝값이면(이미 정렬된 입력) 깊이가 n이 되어 O(n²)로 무너진다. 이득은 균형 있게 쪼개진다는 보장에서 온다.

Step 8: "그리디냐 분할정복이냐" (유형 판별 정리)

오늘 두 사고법을 다 익혔으니, 마지막으로 "어떤 문제에 무엇을 꺼낼까"를 정리합시다. 코딩테스트에서 문제를 만났을 때 가장 먼저 던질 질문이 바로 이거예요.

두 사고법은 애초에 겨루는 관계가 아닙니다. 쓰이는 데가 다르거든요. 그리디는 여러 후보 중에서 고르는 문제에, 분할정복은 문제를 쪼갤 수 있는 문제에 통합니다. 신호로 정리하면 이렇습니다.

그리디는 반례 하나면 곧장 폐기입니다. 그러니 코드를 짜기 전에 작은 입력을 몇 개 던져 보세요(Step 2). 안 깨지면 "왜 손해를 안 보지?"를 한 문장으로 말해 보고, 그 문장이 나오면 자신 있게 짜면 됩니다.

분할정복은 두 질문으로 판정합니다. "반으로 갈라도 같은 문제인가? 갈라서 푼 걸 합칠 수 있나?" 둘 다 예스면 통해요. 그리고 짤 때는 Step 6·7의 교훈 — 제대로, 균형 있게 쪼개졌는지 — 를 확인하시고요.

그리디 vs 동적 계획법 — 한 줄만

여기서 다음 시간을 향한 문 하나를 열어 두겠습니다. 딱 한 줄만요.

그리디는 한 번 고르면 되돌아보지 않고, 동적 계획법(DP)은 모든 선택지를 따져 보되 겹치는 계산을 기억해 재활용합니다.

Step 4의 거스름돈이 정확히 그 경계였어요. 동전 체계가 받쳐 주면(한국 동전) 그리디로 충분하고, 안 받쳐 주면([1,3,4]) 그리디가 틀린 답을 냅니다. 그럼 [1,3,4]는 어떻게 풀어야 할까요? 그게 다음 시간의 주제입니다. 오늘은 이 한 줄만 남기고 넘길게요.

분할정복 vs 동적 계획법 — 이것도 한 줄

한 줄 더 있습니다. 분할정복과 DP도 얼핏 닮았거든요. 둘 다 문제를 쪼개니까요.

차이는 쪼갠 조각이 겹치느냐입니다.

병합 정렬의 왼쪽 절반과 오른쪽 절반을 떠올려 보세요. 서로 전혀 안 겹칩니다. 왼쪽을 정렬한 결과가 오른쪽 정렬에 쓰일 일이 없어요. 그러니 기억해 둘 값어치도 없습니다. 반면 Step 4의 거스름돈 나무에서는 remaining=3이 여러 갈래에서 되풀이 등장했죠. 겹치는 겁니다. 겹치면 비로소 "한 번 푼 걸 적어 두고 다시 쓸" 값어치가 생겨요.

조각이 안 겹치면 분할정복, 겹치면 그때부터 다음 시간의 이야기입니다.

코테에선 이렇게 나온다

오늘 배운 두 사고법이 코딩테스트에서 어떤 이름표를 달고 나오는지 짝지어 둘게요.

오늘 짠 네 함수 — greedy_interval_scheduling, change_making_greedy, min_coins_bruteforce, power — 가 이 유형들의 뼈대입니다. 코드베이스 algorithms/greedy_divide.py에 전부 들어 있으니, 문제를 만나면 이 골격을 꺼내 변형해 쓰세요.

💡 한 줄 정리

고르는 문제면 그리디, 쪼갤 수 있는 문제면 분할정복이다. 그리디는 "이 기준으로 집어도 최적인가"를 반례로 먼저 때려 보고, 분할정복은 "반으로 갈라도 같은 문제인가·합칠 수 있나"로 판정한다. 그리디는 되돌아보지 않고 DP는 겹치는 계산을 기억한다는 것, 분할정복은 조각이 안 겹치고 DP는 겹친다는 것 — 이 두 줄이 다음 시간으로 가는 문이다.

마무리

오늘은 "다 뒤진다"는 완전탐색의 반대편으로 넘어와, 영리하게 고르고 쪼개는 두 사고법을 익혔습니다. 그리디로 회의실을 배정하며 정렬 기준 하나가 정답을 좌우하는 걸 봤고, 거스름돈 반례로 그리디가 조용히 틀리는 순간을 목격했어요. 분할정복으로는 D-1의 병합 정렬을 다시 만나 그게 애초에 분할정복이었음을 확인했고, 거듭제곱에서 1000번을 11번으로 접었습니다.

오늘 배운 핵심 세 가지

• 💡 하나 — 그리디는 매 순간의 최선을 집고 되돌아보지 않는다. 갈라지지 않고 한 줄기로 내려오니 2ⁿ이 n으로 접혀 빠르다(정렬이 지배해 대개 O(n log n)). 대신 그 선택이 전체 최적이라는 보장은 따로 증명해야 한다. 도구는 교환 논법이고, 반박은 반례 하나면 끝나니 실전에선 작은 반례부터 던져 본다.
• 💡 둘 — 분할정복은 반으로 쪼개 정복하고 합친다. D-1의 병합 정렬·퀵 정렬이 이미 이 사고였고, 거듭제곱은 곱셈 1000번을 호출 11번으로 접었다. 비용은 깊이 × 각 깊이의 일이라 O(n log n)·O(log n)이 유도된다. 그 이득은 오직 균형 있게 쪼개진다는 보장에서 오고, 보장이 깨지면(치우친 피벗·중복 호출) 이득도 통째로 사라진다.
• 💡 셋 — 그리디는 빠르지만 틀릴 수 있고, 완전탐색은 맞지만 느리다. [1,3,4]로 6원을 거스르는 문제 앞에서 두 사고법이 나란히 무너졌다. 하나는 3개라는 틀린 답을, 하나는 지수 시간을 냈다. 둘 사이에 세 번째 길이 필요하다.

돌아보면 오늘의 한 줄기는 "영리하게 고른다(그리디) → 영리하게 쪼갠다(분할정복) → 그런데 둘 다 안 통하는 문제가 있다"였어요. E-1의 완전탐색부터 여기까지, 우리는 도구를 하나씩 늘려 왔습니다. 그리고 마지막 Step에서 마주친 그 빈틈이, 정확히 다음 시간의 출발점입니다.

다음 시간 예고

다음 시간(E-4)엔 "문제를 푸는 다섯 사고법"의 마지막, 동적 계획법(dynamic programming, DP) 기초를 만납니다. 출발점은 오늘 Step 4에서 본 그 장면이에요. 거스름돈 완전탐색 나무에서 같은 남은 금액이 여러 갈래에서 되풀이 계산되던 것 — 이걸 중복 부분 문제(overlapping subproblems)라고 부릅니다. 겹치는 조각이 있다는 건, 한 번 푼 걸 다시 풀고 있다는 뜻이죠.

그래서 하는 일은 딱 하나입니다. "한 번 푼 건 적어 두고 다시 쓴다." 이 단순한 생각에 이름이 두 개 붙어요. 위에서 내려오며 필요할 때 계산하고 답을 적어 두는 메모이제이션(memoization, top-down), 아래 작은 문제부터 표를 차곡차곡 채워 올라가는 타뷸레이션(tabulation, bottom-up). 둘은 같은 생각의 두 방향입니다.

다만 DP의 진짜 관문은 따로 있어요. 점화식 세우기입니다. "지금 문제의 답을 더 작은 문제의 답으로 어떻게 표현할 것인가" — 이 한 줄만 세우면 코드는 저절로 나오고, 못 세우면 아무것도 못 합니다. 그래서 피보나치·계단 오르기·타일링 같은 대표 문제로 점화식 세우는 법을 하나씩 익힐 거예요.

그 대가는 놀랍습니다. 지수 시간이 다항 시간으로 내려앉아요. 오늘 손도 못 대던 거스름돈이 눈 깜짝할 사이에 풀립니다. 마지막으로 한 문장만 쥐고 가세요. 그리디는 매 순간의 최적을 믿고, DP는 전체 최적을 계산한다. 오늘 그리디가 왜 틀렸는지 아셨으니, 다음 시간엔 틀리지 않는 법을 배웁니다.

과제

오늘 배운 그리디와 분할정복을 손에 붙이는 문제들입니다. 코드베이스 algorithms/greedy_divide.py의 함수를 가져다 쓰거나 직접 짜서 풀어 보세요. 각 문제의 시간·공간 복잡도를 빅오로 함께 적는 걸 잊지 마세요.

[기초] 곱하기 혹은 더하기

숫자로만 이루어진 문자열 s가 주어질 때, 이웃한 두 숫자 사이마다 × 또는 +를 하나씩 넣어 만들 수 있는 가장 큰 수를 구하는 max_result(s)를 작성하세요. 단 일반적인 연산 순서는 무시하고 왼쪽에서 오른쪽으로 순서대로 계산합니다. 예를 들어 max_result("02984")는 576(0+2 → ×9 → ×8 → ×4), max_result("567")은 210(5×6 → ×7), max_result("0")은 0입니다.

• 두 수를 곱하는 게 늘 이득일까요? 0이나 1이 끼면 어떻게 되는지 손으로 계산해 보세요.
• 매 숫자에서 "지금 곱할까 더할까"만 결정하고 되돌아보지 않으면 그리디입니다. 이 기준이 왜 최적인지 Step 2의 교환 논법으로 한 문장 말해 보세요.
• 시간·공간 복잡도를 빅오로 적으세요. 정렬이 필요 없는 그리디라 Step 1의 O(n log n) 골격과 다르다는 게 힌트입니다.

[응용] 구명보트

사람들의 몸무게 목록 people과 보트 한 대가 견디는 무게 limit이 주어집니다. 보트 한 대에는 최대 두 명까지 탈 수 있고, 두 명이 함께 타려면 몸무게 합이 limit 이하여야 합니다. 모두를 태우는 데 필요한 최소 보트 수를 구하는 min_boats(people, limit)을 작성하세요. 예를 들어 min_boats([70, 50, 80, 50], 100)은 3, min_boats([70, 80, 50], 100)도 3, min_boats([40, 50, 60, 90], 100)은 3입니다.

• 정렬해 놓고 가장 가벼운 사람과 가장 무거운 사람을 짝지어 보세요. D-4의 투 포인터가 그대로 돌아옵니다(양 끝에서 좁혀 오기).
• 가장 무거운 사람은 어차피 혼자 타거나 가장 가벼운 사람과만 탈 수 있습니다. 그렇다면 "가장 무거운 사람부터 처리한다"가 왜 손해를 안 보는지 교환 논법으로 따져 보세요.
• 정렬 O(n log n)에 투 포인터 O(n)이면 전체는 얼마인가요? 공간은요?

[심화] 색종이 만들기

grid는 0(흰색)과 1(파란색)으로 채워진 2ⁿ × 2ⁿ 정사각형 격자입니다(2×2, 4×4, 8×8 …). 이 종이를 다음 규칙으로 자릅니다. 격자 전체가 한 색이면 자르지 않고 그대로 한 장. 아니면 정확히 4등분해 각 조각에 같은 규칙을 되풀이합니다. 최종적으로 나오는 흰 종이 수와 파란 종이 수를 튜플 (흰색, 파란색)으로 돌려주는 count_papers(grid)를 작성하세요. 예를 들어 count_papers([[1, 1], [1, 1]])은 (0, 1)이고(전부 파란색이라 자르지 않고 한 장), count_papers([[0, 1], [1, 0]])은 (2, 2)입니다(색이 섞여 4등분 — 1×1 네 장).

• Step 5의 분할정복 세 걸음을 그대로 얹으세요. "한 색인가?"가 종료 조건, "4등분해 각각 세기"가 분할과 정복, "네 조각의 답을 더하기"가 병합입니다.
• 격자를 4등분할 때 새 리스트를 만들지 말고 좌표 범위(시작 행·시작 열·한 변 길이)를 재귀로 넘기면 훨씬 깔끔합니다. E-2의 격자 좌표 감각이 여기서 쓰여요.
• 병합 정렬은 반으로 쪼갰지만 이건 넷으로 쪼갭니다. 그래도 분할정복일까요? 시간 복잡도를 빅오로 적고, 왜 그렇게 나오는지 Step 7의 "깊이 × 각 깊이의 일"로 설명해 보세요.

생각해볼 주제

1. 코딩테스트 현장에서 그리디를 언제 믿을 것인가

오늘 그리디의 정당성을 교환 논법으로 따져 봤지만, 실제 시험장에선 증명에 쓸 시간이 없습니다. 그런데 확신 없이 짰다가 "일부 케이스 실패"를 받으면 시간 초과보다 훨씬 잡기 어렵죠. 제한 시간 안에서 "이 그리디를 믿고 짤지, 안전한 완전탐색으로 갈지"를 무엇으로 판단하시겠어요? 입력 크기 n이 이 판단에 어떻게 끼어드는지 함께 엮어 정리해 보세요.

2. 같은 분할정복인데 왜 어떤 건 무너지나

오늘 분할정복의 이득이 "균형 있게 쪼개진다는 보장"에서 온다는 걸 두 번 봤습니다. 퀵 정렬은 피벗이 치우치면 O(n²)로 무너졌고, 거듭제곱은 절반을 두 번 부르면 O(log n)이 O(n)으로 무너졌죠. 이 두 붕괴는 겉보기엔 달라 보이는데, 뿌리가 같은 걸까요 다른 걸까요? 그리고 실무의 정렬 라이브러리는 이 붕괴를 어떻게 막고 있을지도 함께 생각해 보세요.

3. 직접 짤 것인가, 내장을 쓸 것인가

오늘 power를 손으로 짰지만 파이썬엔 이미 pow와 **가 있고, 이들도 같은 분할정복으로 돌아 빅오가 같은 데다 C로 구현돼 더 빠릅니다. 회의실 배정의 정렬도 내장 sorted에 맡겼고요. 그렇다면 직접 구현을 배우는 값어치는 어디에 있을까요? 실전에서 내장을 믿고 쓸 때와 직접 짜야 할 때를 무엇으로 가를지 정리해 보세요.