Ch 4. 정렬과 탐색 (Sorting and Searching)

← 수업 목록

Ch 4. 정렬과 탐색 (Sorting and Searching)

수업 목표

본 수업은 문제 해결(PS)의 두 핵심 기둥인 정렬(Sorting)과 이분 탐색(Binary Search), 그리고 매 순간 최선의 선택을 내리는 탐욕법(Greedy)과 투 포인터(Two Pointers) 기법을 습득하는 것을 목표로 합니다. - C++의 std::sort 및 비교 함수 방식을 파이썬의 key=lambda 다중 조건 정렬로 변환하는 기법을 이해합니다. - 투 포인터 및 슬라이딩 윈도우 기법을 통해 리스트 병합과 구간 매칭 문제를 선형 시간 $O(N)$에 해결합니다. - bisect 모듈을 활용하여 C++의 lower_bound / upper_bound 연산을 고속으로 시뮬레이션합니다. - 파이썬에서 std::multiset 부재로 인해 발생하는 TLE 문제를 Union-Find 경로 압축을 통한 가상 삭제로 우회합니다. - 탐욕적 선택 속성(Greedy Choice Property)을 이해하고, 이분 탐색과 결합한 타워 스케줄링 및 오프라인 쿼리를 설계합니다.

학습 동기부여

알고리즘 문제 해결에서 시간 복잡도 개선의 핵심은 '데이터의 정렬 상태(질서)'와 '탐욕적 선택의 최적성'입니다. 정렬된 배열에서는 단 단 $O(\log N)$만에 원하는 원소를 찾을 수 있고, 양 끝에서 좁혀오는 포인터나 지금 가장 최적인 선택을 내리는 탐욕법을 통해 복잡한 시뮬레이션을 단순화할 수 있습니다. C++의 강력한 표준 라이브러리(std::multiset 등)가 파이썬에 없어 직면하는 한계를 알고리즘적 우회법(Union-Find 부모 압축, 오프라인 쿼리)으로 돌파하는 과정에서 파이썬 고속화의 정수를 맛보게 될 것입니다.

도입 스토리

전화번호부 책에서 이름을 찾거나, 양 끝단에서 어깨를 맞대며 가방을 나누는 상황을 떠올려 봅시다. 정렬되어 있지 않다면 전수 조사를 해야 하지만, 정렬되어 있다면 이분 탐색과 투 포인터로 순식간에 답을 찾을 수 있습니다. 또한 빌딩을 최소 개수로 쌓기 위해 가장 빡빡한 타워를 고르는 탐욕법이나, 설치 순서를 뒤집어 구간을 병합하는 오프라인 쿼리까지, 정렬과 탐색이 만들어내는 극적인 성능 변화를 경험해 봅니다.

1. C++ 정렬의 파이썬 이관 및 다중 조건 정렬

C++에서 연산자 오버로딩이나 비교 함수(cmp)를 작성해 커스텀 정렬을 했다면, 파이썬에서는 list.sort() 혹은 sorted() 내부에 key=lambda 구문을 사용하여 매우 직관적으로 작성할 수 있습니다. 파이썬의 정렬(Timsort)은 기본적으로 안정 정렬(Stable Sort)을 보장합니다.

# C++:
# struct Point { int x, y; };
# bool cmp(Point a, Point b) {
#     if (a.x == b.x) return a.y > b.y; // x가 같으면 y 기준 내림차순
#     return a.x < b.x;                 // 기본은 x 기준 오름차순
# }
# sort(pts.begin(), pts.end(), cmp);

# 파이썬으로 이관 시:
# x를 오름차순(x[0]), y를 내림차순(-x[1])으로 정렬
pts.sort(key=lambda p: (p[0], -p[1]))

2. 정렬된 두 리스트의 병합 & 투 포인터

CP-Python 4.1절에서 강조하는 핵심 기법은 이미 정렬된 리스트를 결합할 때의 성능 향상입니다. 두 리스트가 이미 정렬되어 있다면, 처음부터 한 원소씩 비교하며 앞으로 전진하는 두 개의 포인터(Two Pointers)를 두어 $O(N + M)$의 선형 시간에 두 리스트를 병합할 수 있습니다.
이 기법은 8013번: 아파트 문제에서 오차 범위 $K$ 이내의 신청자와 아파트를 매칭할 때와 8014번: 페리스 바퀴에서 제한 무게 $X$ 이하로 아이들을 짝지어 태울 때, 양쪽 끝단 포인터를 좁혀 들어오는 선형 그리디 스케줄링으로 자연스럽게 연결됩니다.

# 8014번: 페리스 바퀴 (아이들을 곤돌라에 최소 개수로 태우기)
# 몸무게 배열 p를 정렬 후, 가장 가벼운 아이와 가장 무거운 아이를 매칭
p.sort()
left = 0
right = len(p) - 1
gondolas = 0

while left <= right:
    if left == right:
        gondolas += 1
        break
    if p[left] + p[right] <= x:
        # 두 명을 한 곤돌라에 태울 수 있는 경우
        left += 1
        right -= 1
    else:
        # 가장 무거운 아이만 혼자 탑승
        right -= 1
    gondolas += 1

3. 이분 탐색 기초와 bisect 모듈

이분 탐색은 정렬된 배열에서 탐색 범위를 절반씩 줄여 나가며 특정 값을 찾는 알고리즘입니다. 파이썬에서는 bisect 모듈을 활용하여 C++의 std::lower_bound와 std::upper_bound 연산을 고속으로 수행할 수 있습니다. - bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 값 x를 삽입할 수 있는 가장 왼쪽 인덱스를 반환합니다. (C++의 lower_bound와 동등) - bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 값 x를 삽입할 수 있는 가장 오른쪽 인덱스를 반환합니다. (C++의 upper_bound와 동등)

import sys
from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 5, 8]
# 4가 처음으로 나타나는 인덱스를 구함
idx_left = bisect_left(a, 4)   # 결과: 2
# 4보다 큰 원소가 처음으로 나타나는 인덱스를 구함
idx_right = bisect_right(a, 4) # 결과: 4

4. 파이썬의 BST 부재 한계 극복: 콘서트 티켓

8018번: 콘서트 티켓 문제에서는 이미 팔린 티켓을 배열에서 지우면서 다음 고객을 처리해야 합니다. C++에서는 std::multiset을 사용하면 삽입/삭제/탐색을 모두 $O(\log N)$에 완료할 수 있어 손쉽게 해결되지만, 파이썬에서는 리스트에서 특정 인덱스의 값을 지우면(pop()) 뒤의 데이터가 이동하는 $O(N)$의 시간 복잡도 병목이 생깁니다.
이를 극복하기 위해 서로소 집합(Disjoint Set, Union-Find)의 부모 가리키기 규칙과 경로 압축을 사용합니다. 각 티켓의 인덱스를 원소로 하는 Disjoint Set을 구성하여, 특정 티켓이 판매되었을 때 그 부모(parent)가 바로 왼쪽의 살아있는 티켓 인덱스를 가리키도록 설정하면, 이분 탐색과 병행하여 가상의 원소 삭제 처리를 $O((N+M) \log N)$에 고속으로 시뮬레이션할 수 있습니다.

# 8018번 핵심 우회 로직
# parent[i]는 i 이하에서 아직 사용 가능한 가장 큰 티켓 인덱스
parent = list(range(n + 1))

def find(i):
    if i < 0: return -1
    path = []
    curr = i
    while curr != -1 and parent[curr] != curr:
        path.append(curr)
        curr = parent[curr]
    for node in path:
        parent[node] = curr
    return curr

# 고객 제시 가격 customer_price 이하인 최적의 티켓 사용
idx = bisect_right(h, customer_price) - 1
real_idx = find(idx)
if real_idx >= 0:
    # 티켓 매칭 및 사용 완료 처리 (부모를 왼쪽 인덱스로 갱신)
    parent[real_idx] = find(real_idx - 1)

5. k-Sum 및 중간 합(Meet-in-the-middle)

8020번: 합이 0인 4개의 값 문제는 4개의 리스트 $A, B, C, D$의 합이 0이 되는 조합의 수롤 찾는 문제입니다. 4중 반복문 $O(N^4)$는 $N=1000$일 때 무조건 시간 초과입니다.
이를 해결하기 위해 식을 $A[i] + B[j] = -(C[k] + D[l])$로 재구성합니다. 1. $A, B$의 조합 합 $N^2$개를 저장하는 리스트와 $C, D$의 조합 합 $N^2$개를 저장하는 리스트를 각각 생성하고 오름차순 정렬합니다. 2. 두 정렬 리스트에 대해 투 포인터를 활용하여 두 리스트의 합이 0이 되는 쌍을 한 번에 세어 줍니다. 이 기법은 시간 복잡도를 $O(N^2 \log N)$으로 줄여 파이썬에서도 단 0.5초 만에 $10^6$개의 조합을 돌파하여 정답을 판정받을 수 있게 합니다.

6. 이분 탐색과 그리디의 결합 — 타워 스케줄링

블록을 차례대로 쌓을 때, 현재 블록을 기존의 타워 중 크기가 현재 블록보다 큰 타워 중 '가장 크기가 작은 타워'의 맨 위에 올리는 것이 탐욕법 관점에서 항상 최적입니다. 만약 그런 타워가 없다면 새로운 타워를 만듭니다. 타워 맨 위 블록의 크기를 정렬된 상태로 유지하며 이분 탐색(bisect_right)으로 갱신 위치를 찾습니다.

# 8021번: 타워 — bisect_right를 활용한 O(N log N) 그리디
import sys
import bisect
input = sys.stdin.readline

n = int(input())
k = list(map(int, input().split()))

towers = []
for val in k:
    # val보다 엄격히 큰 원소 중 가장 왼쪽에 위치한 값의 인덱스 탐색
    idx = bisect.bisect_right(towers, val)
    if idx < len(towers):
        towers[idx] = val  # 기존 타워의 상단 값 업데이트
    else:
        towers.append(val)  # 새 타워 생성

print(len(towers))

7. 역순 처리를 통한 구간 최적화 — 오프라인 쿼리

파이썬에는 C++의 std::set과 같은 균형 이진 탐색 트리가 내장되어 있지 않아, 실시간으로 원소를 삽입하면서 최대 구간을 구하는 연산은 느릴 수 있습니다. 대신 쿼리를 모두 받은 후 역순으로 신호등을 하나씩 '제거'하며 연결 리스트를 이용해 인접한 구간을 병합하는 오프라인 쿼리 기법을 적용하면 연산량을 $O(N \log N)$으로 대폭 낮출 수 있습니다.

# 8022번: 트래픽 라이트 — 오프라인 쿼리 + 연결 리스트 병합
import sys
input = sys.stdin.readline

x, n = map(int, input().split())
p = list(map(int, input().split()))

sorted_p = sorted(p)
pos_map = {val: idx for idx, val in enumerate(sorted_p)}

# 0과 x를 포함한 좌표 리스트
coords = [0] + sorted_p + [x]
nxt = list(range(1, n + 2))
prv = list(range(-1, n + 1))

# 모든 신호등이 설치되었을 때의 최대 구간 구하기
max_gap = 0
for i in range(len(coords) - 1):
    max_gap = max(max_gap, coords[i+1] - coords[i])

ans_rev = []
# 마지막 설치된 신호등부터 역순으로 제거하며 구간 병합
for val in reversed(p):
    ans_rev.append(max_gap)
    idx = pos_map[val] + 1
    p_prev = prv[idx]
    p_next = nxt[idx]
    
    new_gap = coords[p_next] - coords[p_prev]
    max_gap = max(max_gap, new_gap)
    
    # 링크 업데이트
    nxt[p_prev] = p_next
    prv[p_next] = p_prev

print(*(reversed(ans_rev)))

8. 슬라이딩 윈도우와 중복 없는 가장 긴 부분 수열

8020번: 플레이리스트 문제는 중복 없이 가장 길게 연속해서 재생할 수 있는 고유 곡의 길이를 찾는 문제입니다. 이 기법은 두 포인터를 두고 딕셔너리(dict)를 활용해 각 곡의 마지막 등장 위치를 실전으로 기록하면서 left 포인터를 당기는 슬라이딩 윈도우 방식으로 $O(N)$에 해결할 수 있습니다.

# 8020번: 플레이리스트 — dict로 슬라이딩 윈도우 구현
import sys
input = sys.stdin.readline

n = int(input())
playlist = list(map(int, input().split()))

last_seen = {}
left = 0
ans = 0

for right, song_id in enumerate(playlist):
    if song_id in last_seen and last_seen[song_id] >= left:
        left = last_seen[song_id] + 1
    last_seen[song_id] = right
    ans = max(ans, right - left + 1)

print(ans)

자주 하는 실수 & 오류 예방

- bisect 인덱스 범위 초과 검사 누락: bisect_right가 반환하는 인덱스는 대상 배열의 길이에 해당하는 $N$까지 가능합니다. 따라서 탐색 결과의 유효성 검사(idx < 0 또는 idx >= N)를 사전에 거치지 않고 배열의 값에 직접 접근하면 IndexError가 빈번하게 발생합니다. - 리스트 pop(index) 남발: 대용량 데이터를 처리하면서 빈번한 삭제가 발생할 때 정렬된 리스트를 `pop(idx)` 하거나 `remove()` 하면 심각한 병목이 일어납니다. Union-Find를 통한 가상 삭제나 세그먼트 트리 등을 활용해야 합니다. - 정수 나눗셈 연산자(//) 미사용: 파이썬의 / 연산은 무조건 실수형 결과를 내므로, 이분 탐색의 중앙값 mid = (left + right) // 2 계산 시 반드시 정수 나눗셈(//)을 사용하여 자료형 일관성을 보장하십시오.

핵심 정리

구분	기법/함수	시간 복잡도	핵심 용도 및 특징
다중 정렬	lambda 활용 정렬	$O(N \log N)$	다중 비교 조건(튜플)을 주어 파이썬의 Timsort를 다목적으로 활용
이분 탐색	bisect_left / right	$O(\log N)$	C++의 lower_bound / upper_bound와 1:1 매칭되는 삽입 인덱스 획득
가상 삭제	Union-Find 경로 압축	$O(lpha(N))$	리스트 삭제 TLE($O(N)$)를 가상으로 연결하여 무력화 및 속도 향상
중간 합	Meet-in-the-middle	$O(N^2 \log N)$	식을 절반으로 쪼개어 탐색 공간을 극적으로 최적화하는 설계 기법
탐욕법	그리디 스케줄링	$O(N \log N)$	타워 쌓기 등 매 순간 최선의 아슬아슬한 공간을 찾아 할당
역순 처리	오프라인 쿼리	$O(N \log N)$	뒤집어 연결 리스트 병합을 수행하여 삽입 TLE를 무력화

실습 문제

번호	문제 제목	출처	난이도	핵심 알고리즘 / 기법
8013	아파트	CSES	보통	정렬 후 투 포인터 그리디 매칭
8014	페리스 바퀴	CSES	쉬움	정렬 후 양방향 투 포인터 매칭
8018	콘서트 티켓	CSES	어려움	이분 탐색 + Union-Find 가상 삭제
8019	두 수의 합	CSES	쉬움	정렬 후 투 포인터 or 해시맵 탐색
8020	합이 0인 4개의 값	POJ	보통	Meet-in-the-middle 조합 합 탐색
8018	식당 손님	CSES	쉬움	스윕 라인 (입장 +1, 퇴장 -1)
8019	영화 감독	CSES	보통	Greedy 활동 선택 (종료시간 기준 정렬)
8020	플레이리스트	CSES	보통	슬라이딩 윈도우 + 해시맵 중복 방지
8021	타워	CSES	보통	이분 탐색(bisect_right) 기반 그리디
8022	트래픽 라이트	CSES	어려움	오프라인 쿼리 + 양방향 연결 리스트 병합