D-2: 정렬 ② 선형·내장 정렬 — 비교를 버리고, 실전 내장 정렬로

안녕하세요, 홍순구 튜터입니다. 지난 시간에 우리는 비교 기반 정렬 여섯 가지를 손으로 짰습니다. 버블·선택·삽입의 O(n²)를 병합·퀵·힙의 O(n log n)까지 끌어내렸죠. 그리고 마지막에 벽을 하나 만났습니다. 원소끼리 비교만 해서는 아무리 잘해도 O(n log n)이 한계라는 것, "비교의 벽"이었어요.

오늘은 그 벽을 넘습니다. 방법은 뜻밖에 단순해요. 비교를 아예 하지 않으면 됩니다. 값을 세거나 자릿수로 나누면, 원소끼리 크고 작음을 한 번도 따지지 않고 O(n)에 정렬할 수 있어요. 그게 오늘의 두 주인공, 계수 정렬과 기수 정렬입니다. 대신 공짜는 아니라서, 값이 정수이고 범위가 좁아야 한다는 조건이 붙습니다.

정렬의 원리를 다 봤으니, 오늘 후반부에서는 실전으로 넘어갑니다. 코딩테스트에서 실제로 쓰는 파이썬 내장 정렬(sorted·list.sort)을 제대로 익히고, 정렬 기준을 마음대로 바꾸는 key와 여러 기준을 한 번에 거는 튜플 정렬까지 손에 넣습니다. 마지막엔 "언제 직접 짜고 언제 내장을 쓰나"를 정리해요.

 오늘의 여정 — 정렬 ②, 비교를 버리고 실전으로

   ① 비교의 벽을 넘는다   계수 정렬(값을 센다) · 기수 정렬(자릿수로 나눈다) → O(n)
   ② 안정성 다시 보기     같은 값의 순서를 지킨다 → 다중키 정렬의 토대
   ③ 실전 내장 정렬       sorted · list.sort · key · 튜플 · 직접 vs 내장 판단

💡 오늘 수업의 핵심 — "비교를 버려 O(n)에 정렬하는 계수·기수를 이해하고, 실전 내장 정렬을 key·튜플로 자유자재로 커스텀한다"

🎯 학습 목표

• 계수·기수 정렬로 비교의 벽 O(n log n)을 넘어 O(n)에 정렬하는 원리와 그 조건(정수·좁은 범위)을 이해한다.
• 안정 정렬이 왜 다중키 정렬의 토대인지 알고, 파이썬 내장 sorted·list.sort의 차이를 구분한다.
• key 함수와 튜플로 정렬 기준을 자유롭게 바꾸고, 언제 직접 짜고 언제 내장을 쓸지 판단한다.

Step 1: "값을 세어 줄 세운다 — 계수 정렬"

지난 시간의 여섯 정렬은 전부 "누가 더 큰가"를 비교했습니다. 그 비교 때문에 O(n log n)이라는 벽에 막혔죠. 그럼 비교를 안 하고 어떻게 순서를 정할까요? 발상을 바꿔 봅시다. 크기를 견주는 대신, 각 값이 몇 번 나왔는지 세기만 하는 겁니다.

예를 들어 [2, 5, 2, 1, 0, 3, 2, 1]을 정렬한다고 해 봅시다. 값이 0부터 5까지니까, 칸이 여섯 개인 개수 배열을 만들어 각 값이 몇 번 나오는지 세요. 다 세고 나면, 작은 값부터 센 개수만큼 다시 펼치기만 하면 정렬이 끝납니다. 계수 정렬(counting sort)이에요.

# algorithms/sorting.py
def counting_sort(arr):
    a = list(arr)
    if not a:
        return a
    lo, hi = min(a), max(a)
    k = hi - lo + 1                         # 값의 범위: 개수 배열의 칸 수
    count = [0] * k
    for x in a:
        count[x - lo] += 1                  # 최솟값을 0번 칸으로 당겨 값을 칸에 센다
    out = []
    for i in range(k):                      # 작은 값(0번 칸)부터 개수만큼 펼친다
        out.extend([i + lo] * count[i])
    return out

count[x - lo]에서 - lo가 눈에 띄죠? 최솟값을 0번 칸에 맞추려는 겁니다. 값이 음수여도(예를 들어 최솟값이 -3이면) 그만큼 당겨서 0번 칸부터 채워요. 실제로 도는 과정을 그림으로 보면 단번에 이해됩니다.

 counting_sort([2, 5, 2, 1, 0, 3, 2, 1])  — 값을 세고, 작은 값부터 펼친다

   값:     0   1   2   3   4   5
   개수:   1   2   3   1   0   1      ← 2가 세 번, 1이 두 번, 4는 0번
           └ 작은 값부터 개수만큼 펼치면 ┘
   결과:  [0, 1, 1, 2, 2, 2, 3, 5]

원소끼리 크고 작음을 단 한 번도 비교하지 않았어요. 그냥 세고 펼쳤을 뿐입니다. 이게 비교의 벽을 넘는 열쇠예요.

빅오를 따져 봅시다. 값을 세는 데 O(n), 칸을 훑으며 펼치는 데 O(n + k)입니다. 여기서 k는 값의 범위(최댓값 - 최솟값 + 1)예요. 전체는 O(n + k), 공간도 개수 배열 때문에 O(n + k)입니다.

그런데 바로 여기에 함정이 있습니다. k가 값의 범위라는 것. 값이 0부터 10억까지 벌어지면, 개수 배열이 10억 칸이 필요해요. n이 아무리 작아도 k가 커지면 O(n + k)가 통째로 무너집니다. 그래서 계수 정렬은 "값이 정수이고, 그 범위가 좁을 때"만 빛나요.

"1초 ≈ 1억 연산" 잣대로 감을 잡아 봅시다. n이 100만 개인데 값이 0~1,000 사이라면, O(n + k)는 약 100만 연산이라 순식간입니다. 같은 걸 비교 정렬로 하면 O(n log n)이라 약 2,000만 연산이에요. 조건만 맞으면 계수 정렬이 확실히 빠릅니다.

🎯 코테에서는 값의 범위가 문제에 정해져 있을 때 계수 정렬이 강합니다. 나이(0~120), 점수(0~100), 알파벳(26칸)처럼요. "값이 작은 정수"라는 힌트가 보이면 O(n) 정렬을 떠올려 보세요. 물론 실전 코드는 대개 sorted() 한 줄이지만, "이 입력이면 O(n)도 가능하다"는 판단이 서는 게 중요합니다.

💡 한 줄 정리

계수 정렬은 값을 세어 O(n + k)에 정렬하며, 비교를 한 번도 하지 않는 대신 값이 정수이고 범위(k)가 좁아야 한다.

Step 2: "자릿수로 나눠 O(n) — 기수 정렬"

계수 정렬의 약점을 다시 봅시다. 값의 범위 k가 크면 무너진다고 했죠. 그럼 [170, 45, 802, 24, 2]처럼 값이 크게 벌어지면 계수 정렬을 포기해야 할까요? 방법이 있습니다. 값을 통째로 세는 대신, 자릿수 하나씩 나눠서 정렬하는 거예요. 기수 정렬(radix sort)입니다.

핵심 아이디어는 이렇습니다. 먼저 1의 자릿수만 보고 정렬하고, 그다음 10의 자릿수로 정렬하고, 또 100의 자릿수로 정렬해요. 낮은 자릿수부터 올라갑니다(LSD, 최하위 자리부터). 각 자릿수의 값은 늘 0~9라서, 자릿수 하나를 정렬하는 데는 칸이 열 개인 계수 정렬이면 충분해요.

# algorithms/sorting.py
def radix_sort(arr):
    a = list(arr)
    if not a:
        return a
    if min(a) < 0:                          # 음수는 자릿값 개념이 흔들려 이 구현 밖이다
        raise ValueError("radix_sort는 음이 아닌 정수만 지원한다")
    max_val = max(a)
    exp = 1                                 # 지금 보는 자릿수의 자릿값(1·10·100…)
    while max_val // exp > 0:               # 가장 긴 수의 자릿수만큼 반복
        a = _counting_sort_by_digit(a, exp)
        exp *= 10
    return a

exp가 지금 보는 자릿수를 가리킵니다. 1이면 1의 자릿수, 10이면 10의 자릿수예요. (x // exp) % 10으로 그 자릿수의 값(0~9)을 뽑아내죠. 가장 큰 수의 자릿수만큼 반복하면 끝입니다. 각 단계에서 자릿수 하나로 정렬하는 부품이 아래의 _counting_sort_by_digit이에요.

def _counting_sort_by_digit(a, exp):
    n = len(a)
    out = [0] * n
    count = [0] * 10                        # 자릿값은 0~9 열 칸
    for x in a:
        count[(x // exp) % 10] += 1         # 이 자릿수의 값이 몇 번 나오나
    for d in range(1, 10):
        count[d] += count[d - 1]            # 누적합 → 각 자릿값이 끝나는 위치
    for x in reversed(a):                   # 뒤에서부터 놓아 안정성을 지킨다
        d = (x // exp) % 10
        count[d] -= 1
        out[count[d]] = x
    return out

여기서 결정적인 줄이 for x in reversed(a), 입력을 뒤에서부터 훑는 부분입니다. 왜 굳이 뒤에서부터일까요? 같은 자릿값을 가진 원소들의 원래 순서를 지키기 위해서예요. 앞 단계에서 이미 맞춰 둔 순서가 흐트러지지 않아야 다음 자릿수 정렬이 그 위에 쌓입니다. 이걸 안정 정렬이라고 부르는데, 다음 Step에서 제대로 짚겠습니다.

[170, 45, 75, 90, 802, 24, 2, 66]이 자릿수를 하나씩 올라가며 정렬되는 과정을 따라가 봅시다.

 radix_sort([170, 45, 75, 90, 802, 24, 2, 66])  — 낮은 자릿수부터 안정 정렬 반복

   1의 자리로:   170, 90, 802, 2, 24, 45, 75, 66
   10의 자리로:  802, 2, 24, 45, 66, 170, 75, 90
   100의 자리로:  2, 24, 45, 66, 75, 90, 170, 802   ← 완성

1의 자릿수로 정렬한 결과가 10의 자릿수 정렬의 입력이 되고, 그게 다시 100의 자릿수 정렬로 이어집니다. 마지막 자릿수까지 끝나면 전체가 정렬돼요. 신기하죠? 큰 수를 통째로 비교하지 않고, 자릿수 하나씩만 봤을 뿐인데요.

빅오는 O(d · (n + k))입니다. d는 가장 긴 수의 자릿수, k는 10(자릿값의 가짓수)이에요. d가 상수처럼 작으면 사실상 O(n)에 가깝습니다. 공간은 O(n)이고요.

🎯 코테에서는 기수 정렬을 직접 짜라는 문제는 드뭅니다. 대부분 sorted()로 충분해요. 하지만 "값의 범위는 아주 큰데 자릿수는 적은 정수를 대량으로 정렬"하는 특수 상황에서 O(n)의 가능성을 아는 것, 그리고 면접에서 "비교 없이 O(n) 정렬이 어떻게 가능한가"를 설명하는 것에서 이 원리가 힘을 발휘합니다.

💡 한 줄 정리

기수 정렬은 낮은 자릿수부터 안정 계수 정렬을 자릿수만큼 반복해 O(d · (n + k))에 정렬하며, 각 단계의 안정성이 앞 자리 순서를 지켜 준다.

Step 3: "안정성, 다시 보기 — 순서가 유지돼야 하는 이유"

방금 기수 정렬이 "각 단계가 안정적이어야 앞 자리 순서가 유지된다"에 기대고 있었죠. 이 안정성(stable), 지난 시간에 정렬을 보는 세 잣대 중 하나로 만났습니다. 오늘은 그걸 실전 관점에서 한 번 더 파고들어요. 왜냐하면 안정성이 곧 뒤에서 배울 다중키 정렬의 토대이기 때문입니다.

안정 정렬이란, 값이 같은 원소들의 원래 순서가 정렬 뒤에도 지켜지는 정렬입니다. 이게 왜 실전에서 중요할까요? 핵심은 안정 정렬이면 "기준을 여러 번 이어서 걸 수 있다"는 데 있어요. 먼저 2차 기준으로 정렬해 두고, 그다음 1차 기준으로 안정 정렬하면, 1차가 같을 때 2차 순서가 그대로 남습니다.

 안정 정렬이면 '이어서 정렬'이 된다 — 먼저 이름순, 그다음 점수순(안정)

   ① 이름순 정렬:  (가영,90) (나래,80) (다온,90) (라온,80)
   ② 점수순 안정:  (나래,80) (라온,80) (가영,90) (다온,90)
                   └ 80 동점: 나래 → 라온 (①의 이름순이 그대로 유지)

②에서 점수 80이 같은 나래와 라온을 보세요. ①에서 이름순으로 나래가 라온보다 앞이었는데, 점수순으로 다시 정렬한 뒤에도 그 순서가 지켜졌습니다. 안정 정렬이니까요. 만약 불안정 정렬이었다면 이 순서가 뒤집힐 수 있어, 두 단계로 나눠 푸는 방법 자체가 통하지 않아요.

다행히 파이썬 내장 정렬은 안정 정렬입니다. 그래서 "점수순으로 정렬하되 같은 점수는 먼저 등록한 사람이 위로" 같은 요구를 공짜로 만족시켜요. 이 성질이 다음 Step들에서 key와 튜플로 여러 기준을 거는 밑바탕이 됩니다.

🎯 코테에서는 "정렬한 뒤 동점은 이렇게 처리하라"는 조건이 붙는 문제가 정말 많습니다. 나이순으로 정렬하되 같은 나이는 이름순, 점수순이되 동점은 먼저 낸 사람 우선 같은 식이죠. 안정성을 알면 이런 문제를 "2차 기준 먼저, 1차 기준 나중"의 다단계로 풀 수 있고, 다음 Step에서 볼 튜플 key로는 한 줄에 끝냅니다.

💡 한 줄 정리

안정 정렬은 같은 값의 원래 순서를 지켜, 기준을 여러 번 이어서 거는 다중키 정렬의 토대가 되며, 파이썬 sorted는 안정 정렬이다.

Step 4: "실전 정렬 — sorted vs list.sort"

여기까지 정렬의 원리를 손으로 다 봤습니다. 이제 실전입니다. 코딩테스트에서 정렬은 직접 짜는 게 아니라 파이썬 내장 정렬 한 줄로 끝내요. 그런데 이 내장 정렬이 두 가지 형태로 있습니다. sorted()와 list.sort(), 이 둘의 차이를 정확히 알아야 실수를 안 합니다.

xs = [5, 2, 9, 1]

ys = sorted(xs)      # 새 리스트를 만들어 반환한다 (원본은 그대로)
# ys → [1, 2, 5, 9]
# xs → [5, 2, 9, 1]  (건드리지 않음)

xs.sort()            # 원본을 그 자리에서 바꾼다 (반환값은 None)
# xs → [1, 2, 5, 9]

sorted(xs)는 정렬된 새 리스트를 돌려주고 원본 xs는 그대로 둡니다. 반대로 xs.sort()는 원본 xs를 직접 정렬하고, 반환값은 None이에요. 이 반환값 차이에서 초보자가 자주 걸리는 함정이 하나 있습니다.

xs = [5, 2, 9, 1]
xs = xs.sort()       # ⚠️ 함정! sort()는 None을 반환한다
# xs → None  (정렬 결과가 아니라 None이 담긴다)

list.sort()의 결과를 다시 변수에 담으면 None이 들어가 버려요. 원본을 정렬하고 싶으면 xs.sort()만 쓰고, 정렬된 결과를 받고 싶으면 sorted(xs)를 써야 합니다. 내림차순이 필요하면 둘 다 reverse=True를 붙이면 돼요.

sorted(xs, reverse=True)   # 큰 값부터 → [9, 5, 2, 1]

이 내장 정렬의 이름은 Timsort입니다. 지난 시간에 짠 삽입 정렬과 병합 정렬을 영리하게 섞은 하이브리드예요. 작은 조각이나 거의 정렬된 부분은 삽입 정렬로 빠르게 처리하고, 큰 흐름은 병합 정렬로 합칩니다. 그래서 안정 정렬이면서 최악에도 O(n log n)을 보장하고, C로 구현돼 우리가 짠 파이썬 코드보다 훨씬 빠르고 버그도 없어요. 지난 시간에 짠 여섯 정렬은 원리를 보려는 것이었고, 실전은 이 한 줄입니다.

💡 한 줄 정리

sorted()는 새 정렬 리스트를 돌려주고 list.sort()는 원본을 제자리에서 정렬하며(반환값 None), 둘 다 안정 정렬 Timsort로 최악에도 O(n log n)을 보장한다.

Step 5: "정렬 기준을 바꾼다 — key 함수"

지금까지는 값 자체의 크기로 정렬했습니다. 그런데 "숫자 크기 말고 다른 기준으로 줄 세우고 싶다"면 어떻게 할까요? 문자열을 길이순으로, 숫자를 절댓값순으로 정렬하는 것처럼요. 이럴 때 key 파라미터를 씁니다. 각 원소에서 "정렬에 쓸 기준값"을 뽑아내는 함수예요.

words = ["ccc", "a", "bb"]
sorted(words, key=len)           # 길이순 → ['a', 'bb', 'ccc']

nums = [-5, 2, -1, 3]
sorted(nums, key=abs)            # 절댓값순 → [-1, 2, 3, -5]

sorted(nums, key=lambda x: -x)   # 내림차순(람다) → [3, 2, -1, -5]

key=len은 각 문자열을 길이로 바꿔 그 길이로 정렬합니다. key=abs는 각 숫자를 절댓값으로 바꿔 비교하고요. 복잡한 기준이면 lambda로 그 자리에서 함수를 만들어 넘기면 됩니다. key=lambda x: -x는 각 값에 음수를 붙여 큰 값이 작아 보이게 만드니, 결과가 내림차순이 돼요.

여기서 딱 하나만 정확히 기억하세요. key는 "비교 함수"가 아니라 "변환 함수"입니다. 두 원소를 받아 누가 큰지 답하는 게 아니라, 원소 하나를 받아 그 원소의 기준값 하나를 돌려줘요. 파이썬이 각 원소에 key를 한 번씩 적용해 기준값을 뽑고, 그 기준값들로 정렬합니다. 원소 자체는 바뀌지 않고, 뽑은 기준값은 비교에만 쓰여요.

🎯 코테에서는 커스텀 정렬이 key 한 줄로 끝납니다. "문자열을 길이순으로", "좌표를 y값 기준으로", "이름의 마지막 글자순으로" 같은 요구가 나오면 key=lambda를 떠올리세요. 정렬 로직을 직접 짜지 말고, 기준값만 뽑아 주면 나머지는 Timsort가 다 합니다.

💡 한 줄 정리

key는 각 원소에서 정렬 기준값을 뽑는 변환 함수로, len·abs·lambda로 원하는 기준을 한 줄에 건다.

Step 6: "여러 기준을 한 번에 — 튜플 다중키 정렬"

기준이 하나로 부족할 때가 있습니다. "나이순으로 정렬하되 같은 나이는 이름순"처럼 기준이 여러 개인 경우죠. Step 3에서 안정 정렬로 다단계를 돌리는 방법을 봤는데, 더 간결한 길이 있습니다. key가 튜플을 돌려주게 하면 돼요.

people = [("minji", 30), ("jaehoon", 25), ("seungwoo", 30), ("aeri", 25)]
sorted(people, key=lambda p: (p[1], p[0]))
# → [('aeri', 25), ('jaehoon', 25), ('minji', 30), ('seungwoo', 30)]
#    나이(p[1]) 오름차순, 나이가 같으면 이름(p[0]) 오름차순

key가 (나이, 이름) 튜플을 돌려줍니다. 파이썬은 튜플을 비교할 때 앞 원소부터 차례로 견줘요. 먼저 나이로 비교하고, 나이가 같으면 그때 이름으로 비교합니다. 그래서 25살인 aeri와 jaehoon이 이름순(aeri 먼저)으로 정렬됐어요. 튜플 하나로 다중키 정렬이 끝난 겁니다.

그런데 "점수는 내림차순인데 이름은 오름차순"처럼 방향이 섞이면 어떻게 할까요? 숫자라면 음수를 붙이는 트릭을 씁니다.

scores = [("kim", 90), ("lee", 90), ("park", 80)]
sorted(scores, key=lambda p: (-p[1], p[0]))
# → [('kim', 90), ('lee', 90), ('park', 80)]
#    점수(-p[1]) 내림차순, 점수가 같으면 이름(p[0]) 오름차순

-p[1]로 점수에 음수를 붙이면 큰 점수가 작아 보여 내림차순이 되고, 이름 p[0]은 그대로 두어 오름차순입니다. 90점인 kim과 lee가 점수 동점이라 이름순(kim 먼저)으로 정렬됐죠. 하나의 튜플 안에서 오름과 내림을 섞은 거예요.

다만 이 음수 트릭은 숫자에만 통합니다. 문자열은 음수를 붙일 수 없어요. 문자열 기준을 내림차순으로 섞어야 한다면 Step 3에서 본 안정 정렬 다단계로 돌아가거나, reverse=True로 전체 방향을 뒤집는 방법을 씁니다.

🎯 코테에서는 "여러 조건으로 정렬하라"가 튜플 key의 단골 무대입니다. 나이순·이름순 정렬, 좌표를 x 먼저 y 나중으로 정렬, 빈도순 정렬 같은 문제가 key=lambda x: (기준1, 기준2) 한 줄로 끝나요. 방향이 섞이면 숫자엔 음수 트릭, 문자엔 다단계를 떠올리면 됩니다.

💡 한 줄 정리

key가 튜플을 돌려주면 앞 기준부터 차례로 비교해 다중키 정렬이 되고, 숫자는 음수를 붙여 오름차순과 내림차순을 한 튜플에 섞는다.

Step 7: "직접 짤까, 내장을 쓸까 — 정렬 선택 정리"

두 시간에 걸쳐 정렬을 여덟 가지나 봤습니다(비교 정렬 여섯 + 선형 정렬 둘). 그리고 실전 내장 정렬과 key·튜플까지 익혔죠. 이제 정리할 질문 하나가 남았어요. "그래서 실제 문제에선 뭘 써야 하나?"입니다. 이 과목이 내내 강조하는 두 트랙, 직접 구현과 내장 활용의 결론을 내 봅시다.

결론부터 말하면, 실전에서는 거의 항상 내장 정렬을 씁니다. 계수·기수를 직접 짜는 건 예외적인 경우예요. 상황별로 무엇을 고를지 표로 정리했습니다.

핵심은 "원리는 알되, 도구는 내장을 쓴다"입니다. 계수·기수 정렬을 손으로 짜 본 이유는 두 가지예요. 첫째, "비교 없이 O(n)이 가능하다"는 판단이 서야 입력을 보고 최적의 접근을 고를 수 있어요. 둘째, 면접에서 "정렬의 하한이 왜 O(n log n)이고 그걸 어떻게 넘느냐"를 물으면 원리를 아는 사람만 답할 수 있습니다. 하지만 실제 코드는 검증되고 빠른 sorted() 한 줄이 정답이에요.

지금까지 배운 정렬 전체의 빅오를 한 장으로 정리하면 이렇습니다.

 정렬 빅오 한눈에 — 비교 정렬(D-1)의 벽과 선형 정렬(D-2)

   비교 정렬 (병합·퀵·힙)   O(n log n)      ← 비교의 하한, 실전 sorted가 여기
   계수 정렬                O(n + k)        ← 값이 정수·범위 좁을 때
   기수 정렬                O(d · (n + k))  ← 자릿수가 적을 때

정렬은 그 자체로 끝이 아니라, 다음 알고리즘의 발판이라고 지난 시간에 말씀드렸죠. 정렬된 배열이 있으면 무엇을 할 수 있을까요? 다음 시간(D-3)에 그 첫 번째 무기를 꺼냅니다. 절반씩 좁혀 O(log n)에 찾는 이진 탐색이에요. 뒤섞인 배열에서 값을 찾으면 O(n)이지만, 정렬해 두면 O(log n)에 찾습니다. "일단 정렬해 놓으면 풀린다"는 코테의 격언이 왜 나왔는지, 다음 시간에 몸으로 느끼게 될 거예요.

💡 한 줄 정리

실전 정렬은 sorted() 한 줄이 기본이고, key·튜플로 커스텀하며, 값이 정수이고 범위가 좁을 때만 계수·기수를 직접 고려한다.

마무리

오늘은 지난 시간에 만난 "비교의 벽"을 실제로 넘었습니다. 비교를 버리고 값을 세거나 자릿수로 나눠 O(n)에 정렬하는 계수·기수를 손으로 짰고, 실전으로 넘어와 내장 정렬을 key·튜플로 자유자재로 다루는 데까지 왔어요.

오늘 배운 핵심 세 가지

• 💡 하나 — 비교를 버리면 O(n)이 가능하다. 계수 정렬은 값을 세고, 기수 정렬은 자릿수로 나눈다. 대신 값이 정수이고 범위가 좁아야 한다는 조건이 붙는다.
• 💡 둘 — 안정성은 다중키 정렬의 토대다. 같은 값의 원래 순서를 지키는 안정 정렬이라야 기준을 여러 번 이어서 걸 수 있고, 파이썬 sorted는 안정 정렬이다.
• 💡 셋 — 실전은 내장 정렬이다. sorted·list.sort에 key와 튜플을 얹어 커스텀하고, 계수·기수는 원리를 알되 특수 상황에서만 직접 짠다.

다음 시간 예고

오늘 "정렬은 다음 알고리즘의 발판"이라는 말을 다시 했습니다. 다음 시간(D-3)엔 그 발판 위에 첫 무기를 올립니다. 정렬된 배열을 절반씩 좁혀 O(log n)에 찾는 이진 탐색이에요. 나아가 "답 자체를 이분한다"는 매개변수 탐색까지 나아가, 최적화 문제를 결정 문제로 바꾸는 발상을 배웁니다. 오늘 "정렬해 두면 뭐가 좋은가"의 답을 다음 시간에 확실히 보게 될 거예요.

과제

오늘 배운 계수 정렬의 발상과 내장 정렬의 key·튜플을 다지는 문제들입니다. 코드베이스 algorithms/sorting.py의 함수를 쓰거나, 내장 sorted()를 직접 활용해 풀어 보세요.

[기초] 가장 많이 나온 값 찾기

0 이상의 정수 리스트 nums가 주어질 때, 가장 많이 등장한 값을 반환하는 most_frequent(nums)를 작성하세요. 만약 가장 많이 나온 값이 여럿이면(빈도가 같으면) 그중 가장 작은 값을 반환합니다. 예를 들어 most_frequent([1, 3, 1, 3, 1])은 세 번 나온 1을 반환하고, most_frequent([4, 4, 1, 1])은 빈도가 같으므로 더 작은 1을 반환합니다.

• 계수 정렬처럼 개수 배열에 값을 세기만 하면 비교 없이 최빈값이 보입니다. 정렬조차 필요 없어요.
• 시간·공간 복잡도를 빅오로 적고, 왜 그런지 한 줄로 설명하세요.

[응용] 나이순, 같으면 이름순 정렬

(이름, 나이) 튜플의 리스트 people이 주어질 때, 나이 오름차순으로 정렬하되 나이가 같으면 이름 오름차순으로 정렬한 리스트를 반환하는 sort_people(people)을 작성하세요. 예를 들어 [("minji", 30), ("jaehoon", 25), ("seungwoo", 30), ("aeri", 25)]는 [("aeri", 25), ("jaehoon", 25), ("minji", 30), ("seungwoo", 30)]이 됩니다.

• 튜플 key 하나로 다중키 정렬이 끝납니다. 어떤 기준을 앞에 둘지 생각해 보세요.
• 나이와 이름이 모두 같은 두 사람이 있다면, 원래 순서가 지켜지는지도 확인해 보세요(안정 정렬).

[심화] 빈도순 정렬

정수 리스트 nums를 등장 빈도가 높은 값부터 정렬하되, 빈도가 같으면 값이 작은 순으로 정렬한 리스트를 반환하는 sort_by_frequency(nums)를 작성하세요. 각 값은 등장한 횟수만큼 결과에 나와야 합니다. 예를 들어 [2, 3, 1, 3, 2]는 2와 3이 각 두 번, 1이 한 번이므로 [2, 2, 3, 3, 1]이 됩니다.

• 먼저 각 값의 빈도를 세고(Counter가 편합니다), 튜플 key로 "빈도 내림차순, 값 오름차순"을 한 번에 거세요.
• 빈도를 내림차순으로 걸려면 숫자에 어떤 트릭을 쓰면 될지 Step 6을 떠올려 보세요.

생각해볼 주제

1. 계수 정렬이 O(n)인데 왜 항상 쓰지 않을까?

계수 정렬은 비교 정렬의 벽 O(n log n)을 넘어 O(n)에 정렬합니다. 빅오만 보면 언제나 계수 정렬이 이겨야 할 것 같은데, 실전 코드는 대부분 O(n log n)인 sorted()를 씁니다. 무엇이 계수 정렬의 발목을 잡는지, 어떤 조건이 갖춰져야 계수 정렬이 실제로 유리한지 정리해 보세요. "빅오가 작다고 항상 빠른 건 아니다"라는 감각이 목표입니다.

2. 파이썬 정렬은 왜 안정 정렬을 기본으로 골랐을까?

파이썬의 sorted와 list.sort는 안정 정렬(Timsort)입니다. 반면 어떤 언어의 기본 정렬은 불안정한 퀵 계열이에요. 안정 정렬을 기본으로 삼으면 무엇을 얻고 무엇을 잃을까요? 안정성이 실전에서 어떤 문제를 공짜로 풀어 주는지, 그리고 그 대가는 없는지 생각해 보세요.

3. 튜플 key 한 방과 안정 정렬 다단계, 언제 무엇을 쓸까?

다중키 정렬을 두 가지 방법으로 배웠습니다. 하나는 key에 튜플을 넘겨 한 번에 거는 것, 다른 하나는 2차 기준부터 순서대로 안정 정렬을 여러 번 돌리는 것이에요. 두 방법이 각각 어떤 상황에서 더 낫고, 특히 "오름차순과 내림차순이 섞인 다중키"에서 어떤 함정이 있는지 따져 보세요.