정렬과 탐색: 고전 알고리즘 다시 보기

선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬을 직접 짜서 무작위, 정렬됨, 거꾸로 된 입력마다 비교 횟수를 세고, 입력에 따라 달라지는 최선과 최악을 확인해요. 파이썬 sorted가 이미 정렬된 1,000개를 999번 비교로 끝내는 이유와 비교 정렬의 한계 log₂(n!), 같은 값의 순서를 지키는 안정 정렬, 비교 없이 세기만 하는 계수 정렬을 다뤄요. 탐색에서는 bisect로 개수와 범위를 찾고, 처음 고장 난 커밋을 10번 만에 찾는 이진 탐색 응용과 무한 반복에 빠지는 경계 실수까지 짚어요.

중급강의 4 / 6약 16분

해시 테이블은 같은 것 찾기에 강하지만 순서에는 약했어요. 순서를 만드는 일, 정렬은 컴퓨터 과학에서 가장 많이 연구된 문제 중 하나예요. 정렬해 두면 이진 탐색, 이웃끼리 비교하는 중복 찾기, 범위 찾기, 순위 매기기가 모두 쉬워져요. 실무에서는 정렬을 직접 짤 일이 거의 없고 sorted()를 쓰면 되지만, 고전 알고리즘을 직접 짜 보면 같은 일을 하는 여러 방법이 왜 그렇게 다른지 보는 눈이 생겨요.

네 가지 정렬

  • 선택 정렬: 남은 것 중 가장 작은 것을 찾아 맨 앞으로 보내기를 반복해요.
  • 삽입 정렬: 카드를 한 장씩 집어, 이미 정렬된 앞쪽의 제자리에 끼워요.
  • 병합 정렬: 반으로 나눠 각각 정렬한 뒤, 정렬된 두 줄을 앞에서부터 비교하며 합쳐요.
  • 퀵 정렬: 기준값(피벗)을 하나 골라 그보다 작은 것과 큰 것으로 나누고, 양쪽을 다시 정렬해요.

네 가지를 짜서 500개를 정렬할 때 비교를 몇 번 하는지 세어 볼게요. 입력은 무작위, 이미 정렬된 것, 거꾸로 된 것 세 가지예요.

import random

comparisons = 0

def cmp(a, b):                                       # 비교할 때마다 세어요
    global comparisons
    comparisons += 1
    return (a > b) - (a < b)

def selection_sort(items):                           # 가장 작은 것을 찾아 맨 앞으로
    a = list(items)
    for i in range(len(a)):
        smallest = i
        for j in range(i + 1, len(a)):
            if cmp(a[j], a[smallest]) < 0:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]
    return a

def insertion_sort(items):                           # 하나씩 꺼내 앞쪽의 제자리에 끼우기
    a = list(items)
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and cmp(x, a[j]) < 0:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a

def merge_sort(items):                               # 반으로 나눠 각각 정렬하고 합치기
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if cmp(right[j], left[i]) < 0:               # 같으면 왼쪽 것을 먼저 꺼내요
            merged.append(right[j])
            j += 1
        else:
            merged.append(left[i])
            i += 1
    return merged + left[i:] + right[j:]

def quick_sort(items, pick=lambda n: 0):             # 피벗보다 작은 쪽, 큰 쪽으로 나누기
    if len(items) <= 1:
        return list(items)
    p = pick(len(items))
    pivot, rest = items[p], items[:p] + items[p + 1:]
    smaller, same, larger = [], [pivot], []
    for x in rest:
        c = cmp(x, pivot)
        (smaller if c < 0 else larger if c > 0 else same).append(x)
    return quick_sort(smaller, pick) + same + quick_sort(larger, pick)

def random_pivot(n):
    return random.randrange(n)

random.seed(42)
n = 500
inputs = {"무작위": random.sample(range(10 * n), n), "정렬됨": list(range(n)), "거꾸로": list(range(n, 0, -1))}
algorithms = {
    "선택 정렬": selection_sort,
    "삽입 정렬": insertion_sort,
    "병합 정렬": merge_sort,
    "퀵 정렬(첫 값 피벗)": quick_sort,
    "퀵 정렬(무작위 피벗)": lambda a: quick_sort(a, random_pivot),
}
for name, sort in algorithms.items():
    counts = []
    for label, data in inputs.items():
        comparisons = 0
        assert sort(data) == sorted(data)            # 결과가 맞는지도 확인해요
        counts.append(f"{label} {comparisons:,}번")
    print(f"{name}: " + ", ".join(counts))
선택 정렬: 무작위 124,750번, 정렬됨 124,750번, 거꾸로 124,750번
삽입 정렬: 무작위 62,933번, 정렬됨 499번, 거꾸로 124,750번
병합 정렬: 무작위 3,852번, 정렬됨 2,216번, 거꾸로 2,272번
퀵 정렬(첫 값 피벗): 무작위 4,783번, 정렬됨 124,750번, 거꾸로 124,750번
퀵 정렬(무작위 피벗): 무작위 4,418번, 정렬됨 4,816번, 거꾸로 4,629번
  • 선택 정렬은 입력과 상관없이 늘 n(n - 1)/2 = 124,750번이에요. 이미 정렬돼 있어도 "남은 것 중 가장 작은 것"을 찾느라 끝까지 훑어요.
  • 삽입 정렬은 입력에 따라 크게 달라요. 정렬된 입력에서는 499번으로 끝나요. 카드마다 이미 제자리라 한 번씩만 비교하거든요. 거꾸로 된 입력에서는 매번 맨 앞까지 가야 해서 최악이고, 무작위면 그 절반쯤이에요. 그래서 거의 정렬된 데이터에는 삽입 정렬이 아주 빨라요.
  • 병합 정렬은 입력이 어떻든 n log n 근처예요(log₂ 500은 약 9). 반씩 나누니 단계가 log₂ n개이고, 각 단계에서 합치는 비교는 n번을 넘지 않거든요. 대신 합친 결과를 담을 공간이 n만큼 더 들어요.
  • 퀵 정렬은 평균은 빠르지만, 첫 값을 피벗으로 고르면 정렬된 입력에서 최악이 돼요. 피벗이 늘 가장 작은 값이라 0개와 n - 1개로만 나뉘고, 단계가 n개나 쌓이거든요. 실제 데이터는 이미 정렬돼 있거나 거의 정렬된 경우가 흔해서 이건 현실적인 함정이에요. 단계가 쌓이는 만큼 재귀도 깊어져서, 이 코드로 정렬된 1,000개를 정렬하면 파이썬의 재귀 깊이 한계(기본 1,000)에 걸려 RecursionError가 나요. 피벗을 무작위로 고르면 어떤 입력이 와도 평균적으로 n log n이에요.

실제로 쓰는 퀵 정렬은 새 리스트를 만들지 않고 배열 안에서 자리를 바꿔 가며 나눠서, 메모리를 적게 쓰고 캐시에도 유리해요. C++의 std::sort는 보통 퀵 정렬을 바탕으로, 재귀가 너무 깊어지면 다른 방법으로 바꾸고 짧은 구간은 삽입 정렬로 마무리하는 식으로 약점을 메워요.

파이썬의 sorted는 무엇이 다를까

파이썬의 정렬은 Timsort라는 방식이에요(3.11부터는 구간을 합치는 순서를 정하는 규칙을 더 다듬었어요). 데이터에서 이미 정렬된 구간(런)을 찾아내고, 짧은 구간은 삽입 정렬로 늘린 뒤, 구간들을 병합 정렬처럼 합쳐요. 앞에서 만든 cmp로 비교 횟수를 세어 볼게요.

import math
from functools import cmp_to_key

def builtin_comparisons(data):
    global comparisons
    comparisons = 0
    sorted(data, key=cmp_to_key(cmp))
    return comparisons

n = 1_000
nearly = list(range(n))
for i in random.sample(range(n - 1), 10):            # 이웃한 10쌍만 자리를 바꿔요
    nearly[i], nearly[i + 1] = nearly[i + 1], nearly[i]
for label, data in [("무작위", random.sample(range(n), n)), ("이미 정렬됨", list(range(n))),
                    ("거꾸로", list(range(n, 0, -1))), ("거의 정렬됨", nearly)]:
    print(f"{label}: {builtin_comparisons(data):,}번")
print(f"비교로 정렬할 때 최악에 피할 수 없는 횟수 log₂(n!): 약 {math.lgamma(n + 1) / math.log(2):,.0f}번")
무작위: 8,681번
이미 정렬됨: 999번
거꾸로: 999번
거의 정렬됨: 1,759번
비교로 정렬할 때 최악에 피할 수 없는 횟수 log₂(n!): 약 8,529번
  • 이미 정렬된 1,000개는 999번 비교로 끝나요. 처음부터 끝까지 이어진 오름차순 구간 하나를 확인하고 끝이에요. 거꾸로 된 것도 내림차순 구간을 찾아 뒤집기만 해요.
  • 이웃한 10쌍만 흐트러진 데이터는 1,759번이에요. 실제 데이터는 이렇게 일부만 흐트러진 경우가 많아서 이 성질이 큰 힘을 발휘해요.
  • 무작위일 때는 8,681번으로, 이론상 하한인 8,529번에 가까워요. (정확한 횟수는 파이썬 버전에 따라 조금 다를 수 있어요.)

하한은 이렇게 나와요. 1,000개를 늘어놓는 방법은 1,000!가지이고(조합론 강의), 정렬이란 그중 맞는 하나를 골라내는 일이에요. 그런데 비교 한 번의 답은 "예" 아니면 "아니요"라서, 남은 가능성을 많아야 절반으로밖에 못 줄여요. 그러니 최악에는 적어도 log₂(n!)번 비교해야 하고, 이 값은 n log₂ n에서 1.44n쯤을 뺀 크기예요. 그래서 비교로 정렬하는 한 O(n log n)보다 빨라질 수 없어요.

안정 정렬: 같은 값의 순서

정렬 기준이 같은 원소들은 어떤 순서로 나올까요?

students = [("민지", 90), ("준호", 85), ("서연", 90), ("도윤", 85), ("하은", 95)]

def selection_sort_by(items, key):
    a = list(items)
    for i in range(len(a)):
        smallest = min(range(i, len(a)), key=lambda j: key(a[j]))
        a[i], a[smallest] = a[smallest], a[i]
    return a

score = lambda s: s[1]
print("sorted:      ", sorted(students, key=score))
print("선택 정렬:   ", selection_sort_by(students, score))
print("점수 높은 순, 같으면 이름순:", sorted(students, key=lambda s: (-s[1], s[0])))
sorted:       [('준호', 85), ('도윤', 85), ('민지', 90), ('서연', 90), ('하은', 95)]
선택 정렬:    [('준호', 85), ('도윤', 85), ('서연', 90), ('민지', 90), ('하은', 95)]
점수 높은 순, 같으면 이름순: [('하은', 95), ('민지', 90), ('서연', 90), ('도윤', 85), ('준호', 85)]
  • sorted에서는 점수가 같은 준호와 도윤, 민지와 서연이 원래 순서 그대로예요. 이렇게 같은 값끼리 원래 순서를 지키는 정렬을 안정 정렬이라고 해요. 파이썬의 정렬은 안정 정렬이라고 문서에 약속돼 있어요.
  • 선택 정렬은 멀리 떨어진 것끼리 자리를 바꾸다가 민지를 서연 뒤로 보냈어요. 안정 정렬이 아니에요. 삽입 정렬과 병합 정렬은 안정 정렬이고, 퀵 정렬은 보통 안정 정렬이 아니에요.

안정 정렬이면 여러 기준으로 차례로 정렬할 수 있어요. "점수순, 같으면 이름순"을 원하면 이름순으로 먼저 정렬한 뒤 점수순으로 다시 정렬하면 돼요. 더 흔히는 마지막 줄처럼 key에 튜플을 줘서 한 번에 정렬해요. 점수에 마이너스를 붙여 높은 순으로 만들고, 같으면 이름을 비교해요. 자바스크립트의 sort도 2019년 표준부터 안정 정렬이어야 한다고 정해졌어요. 자바는 숫자 배열에는 퀵 정렬을 다듬은 방식을, 객체 배열에는 Timsort를 써요. 같은 숫자끼리는 순서가 바뀌어도 구별할 수 없지만, 객체는 점수가 같아도 서로 다른 사람이라 순서가 의미를 갖거든요.

비교하지 않는 정렬

O(n log n)의 한계는 "비교로 정렬할 때"의 이야기였어요. 값에 대해 더 아는 게 있다면 비교하지 않고도 정렬할 수 있어요.

def counting_sort(scores, top=100):                  # 0점부터 top점까지만 나온다는 걸 알 때
    counts = [0] * (top + 1)
    for s in scores:
        counts[s] += 1                               # 점수마다 몇 명인지 세고
    result = []
    for value, c in enumerate(counts):
        result.extend([value] * c)                   # 작은 점수부터 그 수만큼 늘어놓아요
    return result

random.seed(3)
scores = [random.randint(0, 100) for _ in range(100_000)]
print("sorted()와 결과가 같나요?", counting_sort(scores) == sorted(scores))
sorted()와 결과가 같나요? True

계수 정렬은 비교를 한 번도 하지 않아요. 점수가 0에서 100 사이라는 걸 알고 있으니, 점수마다 몇 명인지 센 뒤 작은 점수부터 늘어놓으면 끝이에요. 값의 범위를 k라 하면 O(n + k)예요. 대신 값이 범위가 작은 정수일 때만 쓸 수 있어요. 범위가 크면 자릿수마다 나눠서 세는 기수 정렬을 쓰기도 해요.

정렬된 데이터에서 찾기

복잡도 강의에서 이진 탐색을 직접 짰어요. 실무에서는 bisect 모듈을 써요.

  • bisect_left(a, x): x를 끼울 수 있는 가장 왼쪽 자리, 즉 x 이상인 첫 값의 위치예요.
  • bisect_right(a, x): x를 끼울 수 있는 가장 오른쪽 자리, 즉 x보다 큰 첫 값의 위치예요.
import bisect

scores = sorted([72, 85, 90, 64, 85, 99, 78, 85, 93, 58])
print("정렬된 점수:", scores)
print("85점은 몇 명?", bisect.bisect_right(scores, 85) - bisect.bisect_left(scores, 85))
lo, hi = bisect.bisect_left(scores, 80), bisect.bisect_right(scores, 90)
print("80점 이상 90점 이하:", scores[lo:hi])
bisect.insort(scores, 88)                            # 정렬을 유지하며 끼워 넣기
print("88점을 끼워 넣으면:", scores)
정렬된 점수: [58, 64, 72, 78, 85, 85, 85, 90, 93, 99]
85점은 몇 명? 3
80점 이상 90점 이하: [85, 85, 85, 90]
88점을 끼워 넣으면: [58, 64, 72, 78, 85, 85, 85, 88, 90, 93, 99]

두 자리의 차이가 그 값의 개수이고, 두 자리 사이를 잘라내면 범위 찾기예요. 해시 테이블이 못 하던 범위 찾기를 O(log n)으로 해요. insort는 정렬을 유지하며 끼워 넣지만, 리스트라서 뒤쪽을 밀어야 하니 끼워 넣기 자체는 O(n)이에요(지난 강의). 자주 끼워 넣으면서 자주 찾아야 한다면 트리 구조가 맞아요.

정렬된 배열이 아니어도 이진 탐색

"어느 지점부터 조건이 참으로 바뀌는가"만 있으면 이진 탐색을 쓸 수 있어요. 대표적인 예가 처음 고장 난 커밋 찾기예요. 어제까지 잘 되던 테스트가 오늘 실패하고, 그 사이 커밋이 1,000개라면요?

commits = [f"c{i:04d}" for i in range(1_000)]        # 오래된 것부터 커밋 1,000개
FIRST_BAD = 737                                      # 실제로는 모르는 값이라고 쳐요
checks = 0

def is_bad(commit):                                  # 그 커밋으로 테스트를 돌려 보는 일
    global checks
    checks += 1
    return int(commit[1:]) >= FIRST_BAD

found = bisect.bisect_left(commits, True, key=is_bad)   # 처음으로 True가 되는 자리
print("처음 고장 난 커밋:", commits[found], "| 테스트를 돌린 횟수:", checks)
처음 고장 난 커밋: c0737 | 테스트를 돌린 횟수: 10

하나씩 확인하면 최악 1,000번이지만, 가운데 커밋에서 테스트해 보고 고장이면 앞쪽 절반, 멀쩡하면 뒤쪽 절반만 남기면 10번이면 끝나요. 조건은 하나, "한 번 고장 나면 그 뒤로는 계속 고장"이어야 해요. bisect의 key 인자(파이썬 3.10부터)로 이런 조건을 바로 쓸 수 있어요. 깃에는 이 일을 해 주는 git bisect가 있어요. 고장 난 커밋과 멀쩡한 커밋을 알려 주면 가운데 커밋을 꺼내 주고, 결과를 알려 줄 때마다 범위를 좁혀 가요. "서버 몇 대면 버틸까", "한 번에 몇 개씩 보내야 제한에 안 걸릴까"처럼 답이 커질수록 조건이 한쪽으로만 바뀌는 문제도 같은 방법으로 풀어요.

경계에서 실수하기 쉬워요

이진 탐색은 아이디어는 쉬운데 정확히 짜기는 어렵기로 유명해요. 흔한 실수 하나를 볼게요.

def buggy_search(ordered, target, limit=100):
    lo, hi, steps = 0, len(ordered) - 1, 0
    while lo < hi:
        steps += 1
        if steps > limit:
            return "100번을 넘게 돌아도 끝나지 않아요"
        mid = (lo + hi) // 2
        if ordered[mid] < target:
            lo = mid                                 # 버그: mid는 이미 확인했으니 mid + 1이어야 해요
        else:
            hi = mid
    return lo

print("10 찾기:", buggy_search([10, 20, 30, 40], 10))
print("40 찾기:", buggy_search([10, 20, 30, 40], 40))
10 찾기: 0
40 찾기: 100번을 넘게 돌아도 끝나지 않아요

10은 잘 찾는데 40에서는 끝나지 않아요. lo와 hi가 이웃해 있으면 mid가 lo와 같아지는데, lo = mid로는 범위가 조금도 줄지 않거든요. 몇몇 값으로만 시험하면 이런 버그를 놓치기 쉬워요. 이진 탐색을 짤 때는 두 가지를 확인해요.

  • 반복할 때마다 범위가 반드시 줄어드나요? mid를 확인했다면 다음 범위에서는 mid를 빼요(mid + 1 또는 mid - 1).
  • 범위의 끝을 포함하나요? hi가 마지막 칸(len - 1)인지 그다음 칸(len)인지 정하고, 끝까지 같은 규칙을 지켜요.

자바 표준 라이브러리의 이진 탐색에도, 아주 큰 배열에서 (lo + hi) / 2가 정수 범위를 넘어 버리는 버그가 9년쯤 숨어 있다가 2006년에야 고쳐졌어요. 파이썬의 정수는 넘치지 않아서 이 문제는 없지만, 그만큼 경계는 까다로워요. 직접 짜기보다 bisect를 쓰는 게 안전해요.

실무에서의 정렬

  • 직접 짜지 말고 sorted()(새 리스트)나 리스트.sort()(제자리)를 써요. key와 reverse로 거의 모든 순서를 만들 수 있어요.
  • 상위 몇 개만 필요하면 전부 정렬하지 않아도 돼요. heapq.nlargest(10, data)는 O(n log 10)으로 상위 10개만 뽑아요. 힙은 다음 강의에서 다뤄요.
  • 찾을 때마다 정렬하지 말아요. 한 번 정렬해 두고 bisect로 찾거나, 같은 값 찾기만 한다면 집합이나 딕셔너리를 써요.
  • 데이터베이스에서는 ORDER BY에 맞는 인덱스가 있으면 따로 정렬하지 않고 순서대로 읽어요. 인덱스의 B-트리가 이미 정렬된 구조이기 때문이에요.

실습

  1. 위의 "거의 정렬된" 데이터(이웃한 10쌍만 바뀜)를 insertion_sort로 정렬하면 몇 번 비교하나요? 왜 그런지 설명해 보세요.
  2. quick_sort의 피벗을 가운데 값(lambda n: n // 2)으로 바꾸고, 정렬된 입력에서 비교 횟수를 세어 보세요. 이 방법도 무너뜨리는 입력이 있을까요?
  3. merge_sort에서 왼쪽의 마지막 값이 오른쪽의 첫 값보다 크지 않으면 비교 없이 그대로 이어 붙이게 고쳐 보세요. 정렬된 입력에서 비교 횟수가 어떻게 되나요?
  4. bisect로 점수를 학점으로 바꾸는 함수를 만들어 보세요. 90점 이상 A, 80점 이상 B, 70점 이상 C, 60점 이상 D, 나머지는 F예요.
  5. 1부터 100만까지의 정수 중 제곱이 처음으로 12,345,678,987을 넘는 수를 이진 탐색으로 찾아보세요.

자주 하는 실수

  • 정렬되지 않은 데이터에서 이진 탐색을 한다. 오류 없이 엉뚱한 답이 나와요.
  • 퀵 정렬의 피벗을 늘 첫 값으로 고른다. 정렬된 입력에서 O(n²)이 되고 재귀도 깊어져요.
  • 이진 탐색의 경계를 대충 짠다. 범위가 줄지 않으면 끝나지 않아요. 가능하면 bisect를 써요.
  • 찾을 때마다 정렬한다. 정렬은 한 번만 하고 결과를 다시 써요.
  • 안정성을 모르고 여러 번 정렬한다. 여러 기준으로 차례로 정렬할 때는 덜 중요한 기준부터 정렬하거나, 튜플 키로 한 번에 정렬해요.
  • 직접 짠 정렬을 실서비스에 쓴다. 표준 정렬이 더 빠르고 검증돼 있어요.

점검 문제

  1. 선택 정렬이 이미 정렬된 입력에서도 느린 이유는?
  2. 삽입 정렬이 거의 정렬된 데이터에 빠른 이유는?
  3. 병합 정렬이 입력과 상관없이 O(n log n)인 이유는?
  4. 첫 값을 피벗으로 쓰는 퀵 정렬이 정렬된 입력에서 O(n²)이 되는 이유와 고치는 법은?
  5. 비교로 정렬하면 O(n log n)보다 빨라질 수 없는 이유는? 계수 정렬은 어떻게 그보다 빠른가요?
  6. 안정 정렬이란 무엇이고, 언제 중요한가요?
  7. 정렬된 리스트에서 어떤 값의 개수를 bisect로 구하는 법은?
  8. 처음 고장 난 커밋을 이진 탐색으로 찾으려면 어떤 조건이 필요한가요?

정답

  1. 남은 것 중 가장 작은 값을 찾으려면, 이미 정렬돼 있어도 남은 것을 끝까지 다 봐야 하기 때문이에요. 입력과 상관없이 늘 n(n - 1)/2번 비교해요.
  2. 원소마다 이미 제자리 근처에 있어서, 앞쪽으로 몇 칸만 비교하면 끼울 자리를 찾기 때문이에요. 완전히 정렬돼 있으면 원소마다 한 번씩, n - 1번이면 끝나요.
  3. 언제나 반씩 나누니 단계가 log₂ n개이고, 각 단계에서 두 줄을 합치는 비교가 n번을 넘지 않기 때문이에요.
  4. 피벗이 늘 가장 작은 값이라 0개와 n - 1개로만 나뉘어서, 단계가 n개로 쌓이고 비교가 n(n - 1)/2번이 되기 때문이에요. 피벗을 무작위로 고르면 평균적으로 O(n log n)이 돼요.
  5. n개를 늘어놓는 방법이 n!가지이고 비교 한 번은 가능성을 많아야 절반으로 줄이니, 최악에는 log₂(n!)번, 즉 n log n 정도의 비교가 필요하기 때문이에요. 계수 정렬은 비교 대신 "값의 범위가 작다"는 정보를 써서 개수만 세니 O(n + k)예요.
  6. 값이 같은 원소끼리 원래 순서를 지키는 정렬이에요. 여러 기준으로 차례로 정렬하거나, 같은 값 안에서 이미 정해진 순서(예를 들어 가입 순)를 유지하고 싶을 때 중요해요.
  7. bisect_right(a, x)에서 bisect_left(a, x)를 빼요. x보다 큰 첫 자리와 x 이상인 첫 자리의 차이가 x의 개수예요.
  8. 한 번 고장 나면 그 뒤 커밋은 모두 고장이라는 조건이요. 그래야 가운데를 확인한 결과만 보고 절반을 확실히 버릴 수 있어요.

다음 강의

지금까지의 구조는 모두 한 줄로 늘어선 데이터였어요. 그런데 폴더 안의 폴더, 회사의 조직도, 친구의 친구처럼 세상의 많은 데이터는 갈라지고 이어져요. 다음 강의에서는 이런 관계를 표현하는 트리와 그래프를 다뤄요. 정렬을 유지하면서 넣고 찾는 이진 탐색 트리, 급한 것부터 꺼내는 힙, 길 찾기의 기본인 너비 우선 탐색과 깊이 우선 탐색을 직접 만들어 봐요.