정렬 문제 풀이 | 코딩 테스트 정렬 패턴 완벽 정리 | 핵심 개념과 실전 활용
이 글의 핵심
코딩 테스트에서 정렬은 문제 해결의 첫 단계인 경우가 많습니다. Python의 sort·key 활용에 더해, Lomuto·Hoare 파티션 비교, 머지소트 보조 공간·안정성, 힙 빌드 O(n) 분석, 카운팅 정렬의 안정 배치, 스위프라인·좌표 압축 등 패턴, 그리고 DB·시스템 실무 정렬까지 한 흐름으로 정리합니다.
시리즈 안내
들어가며
코딩 테스트에서 정렬은 문제 해결의 첫 단계인 경우가 많습니다. 후보를 점수·시간 순으로 줄이거나, 그리디·이진 탐색 전에 순서를 맞출 때 sort와 key만으로 조건을 표현하는 경우가 많습니다.
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
1. 기본 정렬
Python 정렬
같은 리스트를 제자리에서 정렬(sort)할지, 새 리스트를 받을지(sorted)는 원본을 유지해야 하는지에 따라 고르시면 됩니다.
# 오름차순
arr = [5, 2, 8, 1, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]
# 내림차순
arr.sort(reverse=True)
print(arr) # [9, 8, 5, 2, 1]
# 새 리스트 반환
arr = [5, 2, 8, 1, 9]
sorted_arr = sorted(arr)
print(arr) # [5, 2, 8, 1, 9] (원본 유지)
print(sorted_arr) # [1, 2, 5, 8, 9]시간 복잡도
sort(),sorted(): O(n log n) (Timsort)- 안정 정렬 보장
2. 커스텀 정렬
key 함수
# 절댓값 기준 정렬
arr = [-5, -2, 1, 3, -8]
arr.sort(key=abs)
print(arr) # [1, -2, 3, -5, -8]
# 문자열 길이 기준
words = ["apple", "pie", "banana"]
words.sort(key=len)
print(words) # ["pie", "apple", "banana"]
# 튜플 정렬 (첫 번째 요소 기준)
students = [(85, "Alice"), (90, "Bob"), (80, "Charlie")]
students.sort()
print(students)
# [(80, 'Charlie'), (85, 'Alice'), (90, 'Bob')]다중 조건 정렬
# 점수 내림차순, 이름 오름차순
students = [
("Alice", 85),
("Bob", 90),
("Charlie", 85),
("David", 90)
]
students.sort(key=lambda x: (-x[1], x[0]))
print(students)
# [('Bob', 90), ('David', 90), ('Alice', 85), ('Charlie', 85)]
# 나이 오름차순, 이름 내림차순
people = [
("Alice", 30),
("Bob", 25),
("Charlie", 30),
]
people.sort(key=lambda x: (x[1], -ord(x[0][0])))cmp_to_key
from functools import cmp_to_key
def compare(x, y):
if x > y:
return 1
elif x < y:
return -1
else:
return 0
arr = [5, 2, 8, 1]
arr.sort(key=cmp_to_key(compare))
print(arr) # [1, 2, 5, 8]3. 정렬 알고리즘 심화: 구현 관점
코딩 테스트에서는 보통 라이브러리 정렬을 쓰지만, 면접·설계·성능 튜닝에서는 “왜 O(n log n)인지”, “언제 깨지는지”를 묻는 경우가 많습니다. 아래는 고전 알고리즘 네 가지를 동작의 핵심만 짚은 정리입니다.
3.1 퀵소트: 파티션 내부와 피벗 선택
퀵소트(Quicksort)는 피벗(pivot) 한 개를 기준으로 배열을 작은 값 / 큰 값 두 구간으로 나누는 파티션(partition) 을 재귀적으로 반복합니다. 평균 시간 복잡도는 O(n log n), 피벗이 매번 한쪽 끝으로 치우치면 최악 O(n²) 입니다.
Lomuto 파티션은 보통 피벗을 맨 끝에 두고, i는 “피벗보다 작은 구간의 끝”, j는 스캔 인덱스로 두어 한 번의 선형 스캔으로 구간을 나눕니다. Hoare 파티션은 양쪽에서 좁혀 오며 교환하는 방식으로, 교환 횟수·캐시 특성에서 차이가 날 수 있습니다.
피벗 선택 전략은 최악 경우 완화에 직결됩니다.
- 첫/끝 요소: 구현은 단순하나, 이미 정렬된 입력에서 한쪽으로만 분할되어 O(n²) 에 가깝게 붕괴할 수 있습니다.
- 무작위 피벗: 기대적으로 균형 분할에 가까워져 평균적으로 O(n log n)에 수렴합니다.
- median-of-three(첫·중간·끝 중 중앙값): 실무 구현에서 흔히 쓰이는 타협입니다.
동일 키가 많을 때는 3-way 파티션(Dutch National Flag)으로 “작음 / 같음 / 큼” 세 구간으로 나누면 불필요한 재귀를 줄일 수 있습니다.
def lomuto_partition(arr: list, low: int, high: int) -> int:
"""피벗은 arr[high]. 반환값은 피벗의 최종 인덱스."""
pivot = arr[high]
i = low
for j in range(low, high):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[high] = arr[high], arr[i]
return i
def quicksort_inplace(arr: list, low: int = 0, high=None) -> None:
if high is None:
high = len(arr) - 1
if low >= high:
return
p = lomuto_partition(arr, low, high)
quicksort_inplace(arr, low, p - 1)
quicksort_inplace(arr, p + 1, high)위 lomuto_partition은 안정 정렬이 아닙니다. 교환 과정에서 동일 키의 상대 순서가 바뀔 수 있습니다. 코딩 테스트용 구현을 직접 쓸 때는 스택 오버플로, 이미 정렬된 입력, 중복 많은 입력 세 가지를 특히 점검하는 것이 좋습니다.
Hoare 파티션: 양쪽에서 좁혀 오며 분할
Hoare 파티션은 피벗(보통 arr[low])을 기준으로 왼쪽 포인터 i는 피벗보다 크거나 같은 값을, 오른쪽 j는 피벗보다 작거나 같은 값을 찾아가다가 서로 교환합니다. i와 j가 교차하면 한 번의 분할이 끝납니다. 이때 피벗이 최종 위치에 놓인다는 보장은 없습니다. 대신 왼쪽 구간의 모든 원소 ≤ 오른쪽 구간의 모든 원소라는 불변식이 성립하고, 재귀는 보통 [low, j]와 [j+1, high]처럼 겹치지 않게 나눕니다.
def hoare_partition(arr: list, low: int, high: int) -> int:
"""피벗은 arr[low]. 반환값 j: [low, j]와 [j+1, high]로 재귀."""
pivot = arr[low]
i, j = low - 1, high + 1
while True:
while True:
i += 1
if arr[i] >= pivot:
break
while True:
j -= 1
if arr[j] <= pivot:
break
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
def quicksort_hoare(arr: list, low: int = 0, high=None) -> None:
if high is None:
high = len(arr) - 1
if low >= high:
return
p = hoare_partition(arr, low, high)
quicksort_hoare(arr, low, p)
quicksort_hoare(arr, p + 1, high)Lomuto vs Hoare를 면접·구현 관점에서 정리하면 다음과 같습니다.
| 항목 | Lomuto | Hoare |
|---|---|---|
| 피벗 최종 위치 | 파티션 끝에 확정 (p가 피벗 인덱스) | 일반적으로 확정되지 않음 |
| 분할 균형 | 피벗이 한쪽 끝이면 불균형 위험 | 평균적으로 조금 더 균형인 경우가 많음 |
| 교환 횟수 | 동일 키가 많으면 불필요 교환이 잦을 수 있음 | 교환 횟수가 적은 편으로 알려짐 |
| 재귀 범위 | quicksort(low, p-1), (p+1, high)로 단순 | [low, p], [p+1, high] 등 경계 오프바이원에 유의 |
| 파티션 후 | 한쪽에 피벗 하나가 고정 | 두 구간 모두 비어 있지 않게 분할(전형적 구현) |
동일 키가 매우 많을 때는 앞서 언급한 3-way 파티션과 함께, Lomuto의 <= 비교와 스캔 순서가 성능·교환 횟수에 미치는 영향을 설명할 수 있으면 설득력이 높습니다.
3.2 머지소트: 안정성 분석
안정 정렬(stable sort) 이란, 정렬 키가 같은 원소들의 입력에서의 상대 순서가 출력에서도 유지되는 성질입니다.
머지소트(Mergesort)는 배열을 반으로 나누어 각각 정렬한 뒤 병합(merge) 할 때, 왼쪽 절반에서 가져온 원소를 오른쪽과 키가 같을 때 우선 하면 됩니다. 즉, 병합 단계에서 left[i] <= right[j]일 때 왼쪽을 먼저 넣는 규칙 하나로 안정성이 보장됩니다. 반대로 오른쪽을 먼저 넣으면 동일 키의 상대 순서가 뒤바뀔 수 있습니다.
증명의 직관: 동일 키 a와 b(입력에서 a가 앞)가 서로 다른 절반에 있다고 해도, 병합 시 항상 “왼쪽 절반의 원소를 먼저” 소진하는 규칙이면 a가 b보다 먼저 출력 구간에 놓입니다. 키가 다른 쌍에 대해서는 비교 결과가 순서를 결정하고, 키가 같은 쌍만 위 규칙이 tie-breaker 역할을 합니다.
시간은 항상 O(n log n) 이고, 단점은 O(n) 보조 공간이 필요하다는 점입니다. Python의 list.sort()는 Timsort로 안정 정렬이며, 멀티 패스 정렬(키가 여러 단계일 때)을 설계할 때 “한 번의 안정 정렬로 단계별 조건을 쌓는” 패턴과 잘 맞습니다.
보조 공간 최적화: 완전 제자리(in-place) 머지의 현실
표준 머지소트는 길이 n인 임시 배열에 병합 결과를 쓰므로 Ω(n) 보조 공간이 하한입니다. “O(1) 보조 공간으로 병합”을 목표로 하는 in-place merge 알고리즘들은 이론·연구 주제로 오래되었으나, 비교 횟수·캐시·구현 복잡도 때문에 범용 라이브러리의 기본 머지에는 잘 쓰이지 않습니다.
실무·교과서에서 자주 등장하는 완화책은 다음과 같습니다.
- 버퍼 크기 줄이기: 예를 들어 짧은 구간만 임시 배열에 복사하고 나머지는 회전·블록 교환 등으로 맞추는 block merge 계열(구현 난이도 높음).
- 연결 리스트: 노드를 끊어 붙이는 방식이면 추가 포인터만으로 병합 가능하지만, 배열 기반 정렬과는 문제 설정이 다릅니다.
- 바텀업(bottom-up) 머지: 재귀 스택 대신 같은 임시 버퍼를 레벨마다 재사용하면, “스택 공간”은 줄일 수 있으나 입력 크기만큼의 버퍼 자체는 그대로인 경우가 일반적입니다.
정리하면, 코딩 테스트·대부분의 서비스 코드에서는 O(n) 보조 공간 머지를 전제로 한 표준 머지소트가 이해·검증이 쉽고, “공간 O(1)”은 문제에서 명시적으로 요구할 때만 in-place 병합·힙소트·라이브러리의 다른 전략을 비교하는 것이 합리적입니다.
3.3 힙소트: 힙 속성 유지
이진 힙(binary heap) 은 완전 이진 트리로 표현하며, 최대 힙에서는 각 노드의 값이 자식 값보다 크거나 같다는 힙 속성(heap property) 을 유지합니다. 배열 인덱스로는 노드 i의 자식이 2i+1, 2i+2(0-based)입니다.
힙소트(Heapsort)는 (1) 배열을 최대 힙으로 빌드하고, (2) 루트(최댓값)를 끝과 바꾼 뒤 힙 크기를 줄이고 아래로 내려가며(sift-down / heapify) 힙 속성을 복구하는 과정을 반복합니다. sift-down 한 번은 트리 높이에 비례해 O(log n) 이고, 이 추출·복구를 n-1번 반복하므로 정렬 단계 전체는 O(n log n) 입니다. 제자리(in-place) 정렬이라 보조 배열이 거의 필요 없다는 장점이 있습니다.
빌드(heapify)가 O(n)인 이유: 높이 합 논증
초심자에게 흔한 오해는 “n/2개 노드에서 각각 sift-down 하니 O(n log n) 아닌가?” 하는 것입니다. 결론만 말하면 전체 빌드는 O(n) 입니다.
완전 이진 트리에서 높이 h인 레벨(말단에 가까운 쪽) 에 있는 노드 수는 대략 O(n / 2^(h+1)) 수준이고, 그 노드 하나의 sift-down 비용은 O(h) 입니다. 전체 비용은 높이에 대해 합산하면 대략
[ \sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot O(h) = O(n) ]
(많은 노드는 낮은 높이, 높은 노드는 소수이기 때문입니다.) 반면 정렬 단계에서 루트를 n-1번 뽑을 때마다 sift-down은 매번 O(log n) 이므로 O(n log n) 이 됩니다. 즉 힙 구축은 선형, 추출·복구 반복이 n log n 이라고 기억하면 면접 답변이 깔끔합니다.
def _sift_down(arr: list, n: int, i: int) -> None:
"""구간 [0, n)을 힙으로 볼 때 i에서 아래로 힙 속성 복구."""
while True:
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest == i:
return
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
def heapsort(arr: list) -> None:
n = len(arr)
# 아래 인덱스부터 sift-down → O(n) 빌드
for i in range(n // 2 - 1, -1, -1):
_sift_down(arr, n, i)
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
_sift_down(arr, end, 0)힙소트는 일반적으로 안정 정렬이 아닙니다(교환으로 동일 키 순서가 바뀔 수 있음). 최악 시간 O(n log n) 이라는 점은 퀵소트와 대비될 때 자주 언급됩니다.
3.4 카운팅 정렬: 빈도와 위치(버킷 분배)
카운팅 정렬(Counting sort) 은 키가 작은 정수 범위에 속할 때, 각 값의 개수를 세고, 누적 합으로 출력 위치를 정한 뒤 한 번에 옮겨 넣습니다. 여기서 “버킷”은 흔히 값 → 해당 값이 들어갈 구간의 다음 빈 슬롯을 가리키는 위치 배열로 구현합니다.
단계는 (1) count[v]에 빈도 누적, (2) count를 접두 합(prefix sum) 으로 바꿔 “끝 위치”를 잡고, (3) 입력을 역순으로 스캔하며 안정적으로 출력 배열에 놓는 방식이 대표적입니다. 키 범위를 k라 하면 시간·공간은 O(n + k) 입니다. k >> n이면 비실용적입니다.
def counting_sort_stable(arr: list[int], k: int) -> list[int]:
"""arr 원소는 0 이상 k 미만 정수라고 가정."""
count = [0] * k
for x in arr:
count[x] += 1
for i in range(1, k):
count[i] += count[i - 1]
out = [0] * len(arr)
for x in reversed(arr):
count[x] -= 1
out[count[x]] = x
return out안정성: 접두 합 이후에 왜 입력을 역순으로 넣는가
카운팅 정렬이 안정하려면, 같은 키를 가진 원소들이 입력에서의 상대 순서가 출력에서도 유지되어야 합니다. 접두 합으로 count[v]를 바꾼 뒤의 의미는 “값 v를 넣을 때 사용할 다음 인덱스(또는 구간 끝)”입니다. 이때 입력을 앞에서부터 넣으면, 뒤에 있던 동일 키가 앞선 원소보다 먼저 출력 슬롯을 차지해 상대 순서가 뒤집힐 수 있습니다. 역순 스캔은 “같은 키 중 나중에 등장한 원소가 더 앞쪽 슬롯을 쓰도록” 맞춰, 결과적으로 입력 순서가 보존되게 합니다.
비안정 변형으로 앞에서부터 채우는 구현도 만들 수 있으나, 그 경우 인덱스를 왼쪽 끝부터 쓰는 규칙과 키 분포를 정확히 맞춰야 하며, 교과서·면접에서 말하는 “표준 안정 카운팅 정렬”은 위처럼 누적 위치 + 역방향 배치 조합이 대표적입니다. 기수 정렬이 낮은 자릿수부터 안정 정렬을 반복해도 전체 순서가 맞는 이유도, 매 단계의 부분 정렬이 안정해야 하기 때문입니다.
기수 정렬(Radix sort) 은 자릿수별로 위와 같은 안정한 부분 정렬(종종 카운팅 정렬)을 반복해 큰 정수 범위를 다루는 방식으로 확장됩니다. “버킷 분배”를 인덱스 버킷으로 보면, 카운팅 정렬은 가장 단순한 형태의 분배·수집이라고 이해할 수 있습니다.
4. 실전 문제
문제 1: 가장 큰 수
def largest_number(nums):
"""
숫자를 이어 붙여 가장 큰 수
[3, 30, 34, 5, 9] → "9534330"
"""
from functools import cmp_to_key
def compare(x, y):
if x + y > y + x:
return -1
elif x + y < y + x:
return 1
else:
return 0
nums_str = list(map(str, nums))
nums_str.sort(key=cmp_to_key(compare))
result = ''.join(nums_str)
return '0' if result[0] == '0' else result
print(largest_number([3, 30, 34, 5, 9])) # "9534330"
print(largest_number([0, 0, 0])) # "0"문제 2: H-Index
def h_index(citations):
"""
h번 이상 인용된 논문이 h편 이상
[3, 0, 6, 1, 5] → 3
"""
citations.sort(reverse=True)
h = 0
for i, citation in enumerate(citations):
if citation >= i + 1:
h = i + 1
else:
break
return h
print(h_index([3, 0, 6, 1, 5])) # 3
print(h_index([10, 8, 5, 4, 3])) # 4문제 3: 구간 합치기
def merge_intervals(intervals):
"""
겹치는 구간 합치기
[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
"""
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
last = merged[-1]
if current[0] <= last[1]:
merged[-1] = [last[0], max(last[1], current[1])]
else:
merged.append(current)
return merged
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(merge_intervals(intervals))
# [[1, 6], [8, 10], [15, 18]]문제 4: 회의실 배정
def max_meetings(meetings):
"""
겹치지 않는 최대 회의 수
[(1, 4), (3, 5), (0, 6), (5, 7)] → 3
"""
meetings.sort(key=lambda x: x[1])
count = 0
last_end = 0
for start, end in meetings:
if start >= last_end:
count += 1
last_end = end
return count
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)]
print(max_meetings(meetings)) # 45. 정렬 활용 패턴
패턴 1: 정렬 + 투 포인터
def two_sum_sorted(arr, target):
"""
정렬 후 투 포인터로 합 찾기
"""
arr.sort()
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [arr[left], arr[right]]
elif current_sum < target:
left += 1
else:
right -= 1
return None
print(two_sum_sorted([2, 7, 11, 15], 9)) # [2, 7]패턴 2: 정렬 + 이진 탐색
from bisect import bisect_left
def count_smaller(arr, target):
"""
정렬 후 이진 탐색
"""
arr.sort()
idx = bisect_left(arr, target)
return idx
arr = [5, 2, 8, 1, 9]
print(count_smaller(arr, 6)) # 3 (1, 2, 5)패턴 3: 정렬 + 그리디
def assign_cookies(children, cookies):
"""
아이들에게 쿠키 배정 (최대 만족)
"""
children.sort()
cookies.sort()
i = j = 0
while i < len(children) and j < len(cookies):
if cookies[j] >= children[i]:
i += 1
j += 1
return i
children = [1, 2, 3]
cookies = [1, 1]
print(assign_cookies(children, cookies)) # 1패턴 4: 정렬 + 스위프라인(이벤트 순서)
구간·직사각형·스케줄 겹침 등에서 시작/끝 이벤트를 시간 순으로 처리할 때, 먼저 좌표 또는 시간으로 정렬해 스캔 순서를 고정합니다. 전형적으로 (위치, 종류) 튜플을 쓰며, 같은 좌표에서는 닫힘보다 열림 등 문제가 요구하는 태이브레이크를 둡니다.
# 예: 구간 [l, r]을 이벤트로 펼친 뒤 정렬해 겹침 깊이 스캔(경계 처리는 문제 정의에 맞게 조정)
def max_overlap_depth(intervals):
events = []
for l, r in intervals:
events.append((l, 1)) # 시작
events.append((r, -1)) # 끝
# 같은 좌표에서는 두 번째 값 -1(끝)이 1(시작)보다 앞서 오도록 기본 튜플 정렬 사용
events.sort()
depth = best = 0
for _, delta in events:
depth += delta
best = max(best, depth)
return best패턴 5: 좌표 압축 후 카운팅·순위
값의 범위는 크지만 서로 다른 값의 개수는 작을 때, 정렬로 순위 맵을 만든 뒤 0 .. m-1 키로 바꿔 세그먼트 트리·BIT·카운팅 정렬에 넣는 패턴이 흔합니다.
def compress(values):
uniq = sorted(set(values))
return {v: i for i, v in enumerate(uniq)}패턴 6: 정렬 기준을 “한 번에” — 파이썬 키 vs 비교기
key=lambda x: (x.a, -x.b)처럼 튜플 키로 대부분의 다중 조건을 표현하고, 전역 순서가 임의일 때만 cmp_to_key를 씁니다. 비교 함수는 대칭성·추이성 실수가 나오기 쉬우므로, 가능하면 키 튜플로 환원하는 편이 안전합니다.
패턴 7: 정렬 후 동일 그룹 묶기(itertools.groupby)
연속한 동일 키만 묶이므로, 반드시 먼저 정렬합니다. “전체에서 같은 값끼리”가 아니라 인접 그룹이라는 점에 주의합니다.
from itertools import groupby
items = [(1, "a"), (1, "b"), (2, "c")]
items.sort(key=lambda x: x[0])
for k, g in groupby(items, key=lambda x: x[0]):
print(k, list(g))패턴 8: 부분 순위만 필요할 때 — 전체 정렬 대신 힙/Quickselect
상위 k개 또는 k번째만 필요하면 O(n log n) 전체 정렬 대신 크기 k 최소 힙이나 Quickselect(평균 O(n)) 가 유리한 경우가 많습니다. 다만 Quickselect는 최악 O(n²) 이 될 수 있어, 라이브러리·랜덤 피벗·introspection 조합 등 문제 제약을 확인합니다.
6. 프로덕션 정렬 패턴
애플리케이션 코드에서 sort() 호출 한 줄 뒤에는 언어런타임, 데이터베이스, 스토리지·인덱스가 각각 다른 정렬 전략을 씁니다. 실무에서는 “알고리즘 이름”보다 데이터 크기, 키 타입, 안정성, 메모리, 디스크, 이미 정렬된 구간 활용이 결정을 나눕니다.
언어 런타임
- Python
list.sort/ Timsort: 실제 데이터에 이미 정렬된 구간(run) 이 많다는 가정에서 잘 동작하며, 안정 정렬입니다. 대부분의 코딩 테스트·서비스 코드에서는 직접 퀵소트를 구현하지 않는 것이 유지보수·정확성 면에서 이득입니다. - C++
std::sort: 일반적으로 introsort(퀵소트 + 힙소트로 최악 완화) 계열이며,std::stable_sort는 안정 정렬이 필요할 때 별도로 선택합니다. - Java
Arrays.sort: primitive와Object에 따라 알고리즘이 달라질 수 있어, 문서를 확인하는 것이 안전합니다.
데이터베이스와 쿼리
ORDER BY: 실행 계획에서 인덱스 스캔으로 정렬을 피하거나, 메모리 정렬 + 디스크 스필로 처리합니다. 대용량이면 “애플리케이션에서 전부 정렬”이 아니라 DB에 맡기고 LIMIT·인덱스로 줄이는 쪽이 맞는 경우가 많습니다.- 복합 정렬:
(a DESC, b ASC)는 코딩 테스트의 튜플key와 같은 다중 키 문제이며, 안정 정렬 + 단일 키 정렬을 여러 번 적용하는 트릭과 이론적으로 연결됩니다.
대용량·외부 정렬
- 메모리에 다 들어가지 않으면 외부 정렬(external sort) (예: 런을 나눠 정렬 후 k-way merge)가 사용됩니다. 로그·ETL·온디스크 인덱스 빌드에서 흔한 패턴입니다.
언제 특수 정렬을 고려할까
- 키가 좁은 범위의 정수이면 카운팅·기수 정렬이 O(n)에 가깝게 이길 수 있습니다.
- 부분 정렬(상위 k개만 필요)이면 전체 정렬 대신 힙이나 quickselect가 더 낫습니다.
- 안정성이 필요하면(동일 키의 입력 순서 유지) 머지소트·Timsort 계열을 선택합니다.
실무 체크리스트
- 정렬이 병목인가? 프로파일링 전에
key함수가 무거운지(객체 속성 접근 반복)부터 확인합니다. - 이미 정렬된 입력이 많은가? Timsort류는 이득이고, 역순에 가까운 입력은 구현에 따라 덜 유리할 수 있습니다.
- 최악 시간이 중요한가? 퀵소트 단독 구현은 피하고, 라이브러리·introsort·힙소트 등 최악 보장을 확인합니다.
- 중복·타이가 많은가? 3-way 파티션, 다중 키 설계, 안정 정렬 필요 여부를 검토합니다.
실전 팁
정렬 디버깅
def debug_sort(arr, key=None):
"""정렬 과정 출력"""
print("원본:", arr)
sorted_arr = sorted(arr, key=key)
print("정렬:", sorted_arr)
return sorted_arr
students = [("Alice", 85), ("Bob", 90), ("Charlie", 80)]
debug_sort(students, key=lambda x: x[1])정렬 시간 측정
import time
arr = list(range(100000, 0, -1))
start = time.time()
arr.sort()
end = time.time()
print(f"정렬 시간: {(end - start) * 1000:.2f}ms")정리
핵심 요약
- Python 정렬: sort(), sorted(), key 함수
- 커스텀 정렬: lambda, cmp_to_key
- 다중 조건: 튜플 반환 (조건1, 조건2)
- 알고리즘 내부: 퀵소트(Lomuto·Hoare·피벗·최악 O(n²)), 머지소트(병합 규칙·보조 공간 Ω(n)), 힙소트(빌드 O(n)·정렬 O(n log n)·sift-down), 카운팅 정렬(O(n+k)·역순 배치로 안정성)
- 활용 패턴: 투 포인터, 이진 탐색, 그리디, 스위프라인, 좌표 압축, groupby, 부분 순위(힙·Quickselect)
- 프로덕션: DB·런타임·외부 정렬·부분 정렬(힙)과의 역할 분담
- 시간 복잡도: 일반적으로 비교 기반 정렬은 O(n log n); 제약이 있으면 O(n) 특수 정렬 가능
추천 문제
백준:
- 1427번: 소트인사이드
- 11650번: 좌표 정렬하기
- 1931번: 회의실 배정 프로그래머스:
- 가장 큰 수
- H-Index LeetCode:
- 56. Merge Intervals
- 435. Non-overlapping Intervals
다음 단계
관련 글
- 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
- 정렬 알고리즘 | 버블, 선택, 삽입 정렬 완벽 정리
- 이진 탐색 | O(log n) 탐색 알고리즘 완벽 정리
- DP 실전 문제 | 코딩 테스트 DP 문제 풀이 전략
- C++ 알고리즘 문제풀이 | 코딩테스트 필수 문제 10선
심화 부록: 구현·운영 관점
이 부록은 앞선 본문에서 다룬 주제(「정렬 문제 풀이 | 코딩 테스트 정렬 패턴 완벽 정리」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.
내부 동작과 핵심 메커니즘
flowchart TD A[입력·요청·이벤트] --> B[파싱·검증·디코딩] B --> C[핵심 연산·상태 전이] C --> D[부작용: I/O·네트워크·동시성] D --> E[결과·관측·저장]
sequenceDiagram participant C as 클라이언트/호출자 participant B as 경계(런타임·게이트웨이·프로세스) participant D as 의존성(API·DB·큐·파일) C->>B: 요청/이벤트 B->>D: 조회·쓰기·RPC D-->>B: 지연·부분 실패·재시도 가능 B-->>C: 응답 또는 오류(코드·상관 ID)
- 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
- 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
- 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
- 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.
프로덕션 운영 패턴
| 영역 | 운영 관점 질문 |
|---|---|
| 관측성 | 요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가 |
| 안전성 | 입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가 |
| 신뢰성 | 재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가 |
| 성능 | 캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가 |
| 배포 | 롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가 |
| 용량 | 피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가 |
스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.
확장 예시: 엔드투엔드 미니 시나리오
앞선 본문 주제(「정렬 문제 풀이 | 코딩 테스트 정렬 패턴 완벽 정리」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.
- 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
- 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
- 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
- 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
- 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.
handle(request):
ctx = newCorrelationId()
validated = validateSchema(request)
authorize(validated, ctx)
result = domainCore(validated)
persistOrEmit(result, idempotentKey)
recordMetrics(ctx, latency, outcome)
return result문제 해결(Troubleshooting)
| 증상 | 가능 원인 | 조치 |
|---|---|---|
| 간헐적 실패 | 레이스, 타임아웃, 외부 의존성, DNS | 최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검 |
| 성능 저하 | N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스 | 프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거 |
| 메모리 증가 | 캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납 | 상한·TTL·힙/FD 스냅샷 비교 |
| 빌드·배포만 실패 | 환경 변수, 권한, 플랫폼 차이, lockfile | CI 로그와 로컬 diff, 런타임·이미지 버전 핀 |
| 설정 불일치 | 프로필·시크릿·기본값, 리전 | 스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화 |
| 데이터 불일치 | 비멱등 재시도, 부분 쓰기, 캐시 무효화 누락 | 멱등 키·아웃박스·트랜잭션 경계 재검토 |
권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.
배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. 코딩 테스트 정렬 문제 풀이, 커스텀 key, 퀵·머지·힙·카운팅 정렬의 내부 동작과 프로덕션 정렬 패턴까지 정리합니다. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
이 글에서 다루는 키워드 (관련 검색어)
알고리즘, 정렬, 문제풀이, 코딩테스트, Python, sort 등으로 검색하시면 이 글이 도움이 됩니다.