선형 탐색: 정직한 기준선

"가장 단순한 탐색은 찾을 때까지 전부 들여다보는 거야. 하나도 영리하지 않은데, 그게 정확히 핵심이야. 영리하지 않은 O(n) 훑기가 진짜 정답일 때가 있고, 그걸 굳이 과잉 설계하는 쪽이 실수거든."

숨길 게 없는 알고리즘

선형 탐색은 컬렉션을 원소 하나씩 걸으면서 찾는 값이 나오거나 끝에 닿으면 멈춰. 길이가 n인 시퀀스에서 최악은 O(n)이고, 첫 원소가 바로 그 값이면 최선은 O(1)이야. 별도 인덱스가 없는, 정렬되지 않은 임의의 시퀀스에는 자연스러운 기본값이지. 다만 값의 범위나 저장 구조에 대한 추가 정보가 있다면 해시 인덱스나 직접 주소법 같은 다른 선택지도 열려.

과잉 설계 함정

여기서 진짜로 다루는 건 판단이야. 이진 탐색과 해시맵을 배우고 나면 반사적으로 그쪽으로 손이 가거든. 그런데 생각해 봐. 정렬 안 된 데이터를 이진 탐색하려면 먼저 정렬해야 하고, 그게 O(n log n)이야. 한 번 훑는 O(n)보다 더 비싸지. 정렬 안 된 데이터를 한 번 찾을 거라면 선형 탐색이 완승이야. 화려한 구조는 준비 비용이 여러 번의 탐색에 걸쳐 분할 상환될 때라야 본전을 뽑아. 한 번만 조회할 데이터에 이진 탐색을 꺼내는 건 전형적인 조기 최적화고. n 한 번을 아끼려고 n log n을 치른 셈이니까.

선형 탐색은 별도 인덱스 없이 한 번 훑는 O(n) 기본값이야. 조회를 한 번 하자고 먼저 정렬하는 건 대개 더 비싸지만, 조회가 반복되거나 쓸 만한 추가 구조가 있다면 인덱스를 만드는 비용을 뽑아낼 수 있어.

Python다운 형태들

반복문을 손으로 쓸 일은 드물어. Python이 선형 탐색을 표현력 있는 형태로 여러 개 주거든. x in items는 있는지 묻고, items.index(x)는 어디 있는지 묻고, any(pred(x) for x in items)는 조건에 맞는 게 하나라도 있는지 묻고, next((x for x in items if pred(x)), default)는 첫 번째로 맞는 걸, 없으면 기본값을 줘. 전부 속으로는 O(n) 훑기야. 이게 선형이라는 걸 알아야 반복문 안에 무심코 넣어서 O(n²)를 만드는 사고를 막을 수 있어. 복잡도 트랙에서 본 그 함정 말이야.

피파의 고백

이진 탐색을 갓 배우고 나서, 딱 한 번 하는 조회를 리스트를 먼저 정렬하고 이진 탐색하는 식으로 '최적화'한 적이 있어. 아빠가 비용을 짚어줬지. 한 번 훑는 O(n)을 아끼겠다고 O(n log n)짜리 정렬을 붙인 거였어. 영리한 기분을 내려고 오히려 느리게 만든 거지. 그때 박힌 교훈이 이거야. 도구가 더 정교하다고 해서 더 적절한 건 아니다. 정렬 안 된 시퀀스를 한 번 조회하는 데는 선형 훑기가 대개 가장 단순하고 충분한 답이야.

Code

선형 탐색과 Python다운 표현들·python

# 선형 탐색: 정직한 O(n) 훑기, 뭐에든 작동.
def linear_search(items, target):
    for i, x in enumerate(items):
        if x == target:
            return i           # 찾음 — 조기 종료
    return -1                  # 없음

data = [42, 7, 13, 99, 1]      # 정렬 안 됨
print(linear_search(data, 99))   # 3

# Pythonic 선형 탐색 (전부 밑에선 O(n)):
print(99 in data)                              # True  — 멤버십
print(data.index(13))                          # 2     — 위치
print(any(x > 50 for x in data))               # True  — 매치 있음
print(next((x for x in data if x > 50), None)) # 99    — 첫 매치 또는 기본값

# 함정: 정렬 안 된 데이터의 한 번 탐색엔, 이 O(n) 훑기가
# '먼저 정렬 (O(n log n)) 후 이진 탐색' 을 이겨. n 아끼려 n log n 치르지 마.

Exercise

정렬 안 된 레코드 백만 개짜리 리스트를 받았고 그중 특정 레코드 하나를 딱 한 번 찾아야 해. (a) 선형으로 훑는 방법과 (b) 정렬한 다음 이진 탐색하는 방법의 비용을 비교해 봐. 어느 쪽이 빠르고 왜 그럴까? 이제 상황을 바꿔서, 같은 리스트를 만 번 찾을 거라고 해 보자. 답이 뒤집힐까? 손익분기는 어떻게 따지면 될까?

Hint

한 번 찾는 경우 선형은 O(n)이야. 정렬 후 이진 탐색은 O(n log n) + O(log n)인데 정렬이 지배하니까 선형이 이겨. 만 번 찾는 경우라면 정렬을 한 번 O(n log n)에 해두고 만 번의 O(log n)을 쓰는 쪽이 만 번의 O(n)보다 나아. 이제 전처리가 본전을 뽑는 거지. 손익분기는 탐색에서 아끼는 총량이 정렬에 드는 일회성 비용을 넘어서는 지점이야.

숨길 게 없는 알고리즘

과잉 설계 함정

Python다운 형태들

피파의 고백

Code

External links

Exercise

Progress

댓글 0