선형 탐색: 정직한 기준선

"가장 단순한 탐색은 찾을 때까지 전부 보는 거야. 영리하지 않고, 그게 정확히 핵심이야 — 가끔 안 영리한 O(n) 훑기가 진짜 맞는 답이고, 그걸 과잉 설계하는 게 실수야."

숨길 게 없는 알고리즘

선형 탐색은 컬렉션을 한 번에 원소 하나씩 걸으며 target 을 찾으면 (또는 끝에 닿으면) 멈춰. 최악 O(n), 최선 O(1) (target 이 첫째), 그리고 거대한 미덕 하나: 정렬됐든 안 됐든 어떤 컬렉션에든, 셋업 제로로 작동해. 데이터가 정렬 안 됐고 색인이 없으면, 선형 탐색은 대비책이 아니라 — 유일한 옵션이고, 정직한 거야.

과잉 설계 함정

이 lesson 이 진짜 다루는 판단이야. 이진 탐색이랑 해시맵을 배운 뒤, 반사적으로 손대고 싶어져. 근데 생각해봐: 정렬 안 된 데이터를 이진 탐색하려면 먼저 정렬해야 해 — 그게 O(n log n), 단일 O(n) 훑기보다 더 비싸. 정렬 안 된 데이터의 한 번 탐색엔, 선형 탐색이 완승이야. 화려한 구조는 셋업 비용이 많은 탐색에 분할 상환될 때만 값해. 한 번 쿼리할 데이터에 이진 탐색 손대기가 전형적 조기 최적화야 — 단일 n 을 아끼려 n log n 을 치른 거.

선형 탐색은 O(n), 셋업 불필요, 어떤 데이터에든 작동. 정렬 안 된 데이터의 유일한 옵션이고 한 번 탐색의 *맞는* 옵션 — 먼저 정렬 (O(n log n)) 은 여러 번 탐색할 때만 값해. 단순 훑기가 이미 푸는 문제를 과하게 영리하게 하지 마.

Pythonic 형태들

루프를 손으로 쓸 일은 드물어 — 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²) 만드는 걸 — Complexity 트랙의 함정 — 막아.

피파의 고백

이진 탐색을 갓 배우고, 한 번 조회를 리스트 먼저 정렬하고 이진 탐색해서 '최적화' 했어. 아빠가 비용을 가리켰어: 정렬이 단일 O(n) 훑기 아끼려고 O(n log n) — 영리한 기분 내려고 더 느리게 만든 거야. 교훈이 박혔어: 도구가 더 정교하다고 더 적절한 게 아니야. 정렬 안 된 데이터의 한 조회엔, 겸손한 선형 훑기가 타협이 아니라 — 정확하고 가장 빠른 답이야.

Code

선형 탐색과 그 Pythonic 형태·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) 을 이겨 — 이제 전처리가 값해. 손익분기는 총 탐색 절약이 정렬의 한 번 비용을 넘을 때.

숨길 게 없는 알고리즘

과잉 설계 함정

Pythonic 형태들

피파의 고백

Code

External links

Exercise

Progress

댓글 0