1. 선형 탐색 (Linear Search) — O(n)

핵심 인사이트 (3줄 요약)

1. 본질: 배열을 처음부터 끝까지 순차적으로 비교하는 가장 단순한 탐색 알고리즘으로, 정렬 여부에 상관없이 동작한다.
2. 가치: 구현이 극히 단순하고 전처리가 필요 없어 소규모 데이터나 정렬 비용이 높은 상황에서 오히려 최선의 선택이 된다.
3. 판단 포인트: 데이터가 정렬·인덱싱되어 있으면 이진/해시 탐색으로 전환하되, 단건·소규모·비정렬·연결 리스트에서는 선형 탐색이 합리적이다.

Ⅰ. 개요 및 필요성

선형 탐색 (Linear Search)은 배열의 첫 번째 원소부터 마지막 원소까지 목표값과 하나씩 순서대로 비교하는 알고리즘이다. 별도의 사전 조건(정렬 등)이 없어 어떤 데이터에도 바로 적용할 수 있다.

선형 탐색이 적합한 상황:

• 데이터가 정렬되어 있지 않고 정렬 비용이 탐색 이득보다 클 때
• 배열 크기가 작아 탐색 비용 차이가 미미할 때 (n < 100 수준)
• 연결 리스트처럼 임의 접근 (Random Access)이 불가능한 자료구조
• 스트리밍 데이터에서 조건을 만족하는 첫 원소를 실시간으로 추출할 때

📢 섹션 요약 비유: 선형 탐색은 도서관에서 책을 찾을 때 처음 책장부터 한 권씩 훑어보는 것과 같다. 책이 몇 권뿐이라면 정리하는 시간조차 아까우니 이 방법이 오히려 빠르다.

Ⅱ. 아키텍처 및 핵심 원리

기본 동작 흐름

배열: [7, 2, 15, 4, 9, 11, 3]     목표: 9

단계 1:  i=0 → arr[0]=7  → 7 ≠ 9 → 계속
단계 2:  i=1 → arr[1]=2  → 2 ≠ 9 → 계속
단계 3:  i=2 → arr[2]=15 → 15 ≠ 9 → 계속
단계 4:  i=3 → arr[3]=4  → 4 ≠ 9 → 계속
단계 5:  i=4 → arr[4]=9  → 9 = 9 → 반환(4) ✓

ASCII 다이어그램 — 선형 탐색 포인터 이동

┌─────────────────────────────────────────────────────────────┐
│  배열:    [ 7 ] [ 2 ] [15 ] [ 4 ] [ 9 ] [11 ] [ 3 ]        │
│  인덱스:    0     1     2     3     4     5     6            │
│                                                             │
│  탐색 진행 →→→→→→→→→→→→→→→→→→→→→→→                         │
│   i=0: 7≠9  i=1: 2≠9  i=2: 15≠9  i=3: 4≠9                 │
│                                                             │
│                               i=4: 9=9  ← Found!           │
│                               ↓                            │
│                            반환: 4                          │
└─────────────────────────────────────────────────────────────┘

Sentinel(감시자) 최적화

일반 선형 탐색은 매 반복마다 두 가지 조건을 검사한다:

1. 인덱스가 배열 범위를 벗어났는가?
2. 현재 원소가 목표값과 같은가?

Sentinel 기법은 배열 끝에 목표값을 추가하여 범위 검사를 제거한다.

일반:     while (i < n) AND (arr[i] != target)
Sentinel: arr[n] = target;   while (arr[i] != target)   // 범위 검사 제거

탐색 비교 횟수는 동일하지만 분기(Branch) 횟수가 절반으로 줄어 CPU 파이프라인 친화적이다.

📢 섹션 요약 비유: Sentinel은 미로 출구에 "도착!" 표지판을 세워두는 것과 같다. 표지판이 없으면 매 걸음마다 "여기가 출구인가? 벽에 부딪혔나?"를 두 번 물어야 하지만, 표지판이 있으면 한 번만 물으면 된다.

Ⅲ. 비교 및 연결

탐색 알고리즘 3종 비교

선형 탐색의 실질적 강점

• 문자열 매칭: Naive 패턴 매칭 알고리즘 = 텍스트 상의 선형 탐색 확장
• 스트리밍 처리: 실시간 데이터 스트림에서 조건 원소 추출 (정렬 불가)
• 연결 리스트: 임의 접근 불가이므로 이진 탐색 자체가 불가능

📢 섹션 요약 비유: 선형 탐색과 이진 탐색의 관계는 작은 동네 골목길과 고속도로의 차이다. 골목이 짧다면 굳이 고속도로 진입로를 찾을 필요가 없다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오

시나리오 1: 소규모 캐시 히트 확인 (n=16)

• LRU (Least Recently Used) 캐시에서 캐시 히트 확인
• n=16 수준이면 선형 탐색이 캐시 라인 전체를 L1 캐시에 적재 → 이진 탐색보다 빠를 수 있음

시나리오 2: DB 풀 테이블 스캔 (Full Table Scan)

• SQL WHERE 절에 인덱스 없는 컬럼 조건 → 내부적으로 선형 탐색
• 대용량 테이블에서 성능 병목 → 인덱스 설계로 이진/해시 탐색 전환이 필수

시나리오 3: 단일 탐색 후 대용량 정렬

• 리스트가 한 번만 탐색된다면: 정렬 O(n log n) + 이진 탐색 O(log n) > 선형 탐색 O(n)
• 여러 번 탐색: 정렬 비용을 분할 상각 → 이진 탐색이 유리

기술사 판단 기준

📢 섹션 요약 비유: 기술사 시험에서 선형 탐색은 "작은 문제에 복잡한 도구를 꺼낼 필요 없다"는 원칙의 증거다. 데이터가 10개인데 이진 탐색 인덱스를 구축하는 것은 가위로 종이 한 장 자르려고 레이저 커터를 설치하는 격이다.

Ⅴ. 기대효과 및 결론

선형 탐색 (Linear Search)은 O(n)이라는 한계에도 불구하고 정렬 불필요, 구현 단순, 임의 접근 불요라는 세 가지 장점으로 실무에서 지속적으로 활용된다.

Sentinel 최적화로 분기 횟수를 절반으로 줄일 수 있고, 하드웨어 수준에서 소규모 배열(n < 32)은 이진 탐색보다 캐시 친화적이어서 실질 성능이 더 빠른 경우도 있다.

핵심 결론: 데이터가 작고 정렬이 없을 때, 선형 탐색은 최선의 선택이다. 선택 기준은 이론적 복잡도가 아니라 실제 상황(데이터 크기, 탐색 빈도, 정렬 비용)이다.

📢 섹션 요약 비유: 선형 탐색은 스위스 아미 나이프 같은 존재다. 전문 도구보다 성능은 낮지만, 항상 손에 들고 다닐 수 있어서 작은 작업에는 가장 먼저 꺼내는 도구다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[이진 탐색 (Binary Search)]
    │
    ▼
[해시 탐색 (Hash Search)]
    │
    ▼
[Sentinel 최적화]
    │
    ▼
[풀 테이블 스캔 (Full Table Scan)]

이 흐름도는 선행 개념이 현재 개념으로 응축되고, 다시 확장 개념으로 이어지는 순서를 보여준다.

👶 어린이를 위한 3줄 비유 설명

1. 🔍 숨바꼭질에서 친구를 찾을 때 방마다 하나씩 문을 열어보는 것처럼, 선형 탐색은 배열을 처음부터 순서대로 확인한다.
2. 📦 택배가 100개 쌓인 창고에서 이름표 없이 박스를 하나씩 열어보는 것과 같아서, 박스가 많을수록 오래 걸린다.
3. ✅ 하지만 박스가 딱 5개라면? 정리하는 시간조차 아까우니 그냥 하나씩 열어보는 게 가장 빠른 방법이다.