선형 탐색 (Linear Search)

개념

처음부터 끝까지 순차적으로 탐색하는 가장 단순한 탐색 알고리즘

정렬되지 않은 데이터에서도 사용 가능

---

시간복잡도

케이스	시간복잡도
최선	O(1)
평균	O(n)
최악	O(n)
공간복잡도	O(1)

---

특징

장점

• 구현 간단: 가장 이해하기 쉬운 탐색
• 정렬 불필요: 정렬되지 않은 데이터에도 적용
• 작은 데이터: 소량의 데이터에 효율적
• 첫 번째 발견: 중복 시 첫 요소 반환

단점

• 느린 속도: 대용량 데이터에 비효율적
• 순차 접근: 전체를 확인해야 할 수 있음

---

구현 방법

기본 구현

def linear_search(arr, target):
    """선형 탐색 - 인덱스 반환"""
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1  # 찾지 못함
 
# 테스트
arr = [10, 23, 45, 70, 11, 15]
print(linear_search(arr, 70))  # 3
print(linear_search(arr, 100))  # -1
 
# 시간복잡도: O(n)
# 공간복잡도: O(1)

---

Python식 구현

def linear_search_pythonic(arr, target):
    """Python in 연산자 활용"""
    if target in arr:
        return arr.index(target)
    return -1
 
# 테스트
arr = [10, 23, 45, 70, 11, 15]
print(linear_search_pythonic(arr, 70))  # 3
 
# 내부적으로 선형 탐색 수행

---

모든 위치 찾기

def linear_search_all(arr, target):
    """target이 있는 모든 인덱스 반환"""
    indices = []
 
    for i in range(len(arr)):
        if arr[i] == target:
            indices.append(i)
 
    return indices if indices else -1
 
# 테스트
arr = [1, 2, 3, 2, 4, 2, 5]
print(linear_search_all(arr, 2))  # [1, 3, 5]
print(linear_search_all(arr, 10))  # -1
 
# 시간복잡도: O(n)

---

조건을 만족하는 요소 찾기

def linear_search_condition(arr, condition):
    """조건을 만족하는 첫 요소 반환"""
    for i, element in enumerate(arr):
        if condition(element):
            return i
    return -1
 
# 테스트
arr = [1, 5, 3, 8, 4, 9]
 
# 짝수 찾기
index = linear_search_condition(arr, lambda x: x % 2 == 0)
print(index)  # 4 (첫 번째 짝수 8의 인덱스)
 
# 5보다 큰 수 찾기
index = linear_search_condition(arr, lambda x: x > 5)
print(index)  # 3 (8의 인덱스)
 
# 시간복잡도: O(n)

---

동작 과정

배열: [10, 23, 45, 70, 11, 15]
찾는 값: 70

1단계: arr[0] = 10 ≠ 70
2단계: arr[1] = 23 ≠ 70
3단계: arr[2] = 45 ≠ 70
4단계: arr[3] = 70 = 70  ✓ 발견!

결과: 인덱스 3 반환

---

템플릿

def linear_search_template(arr, target):
    # 배열 순회
    for i in range(len(arr)):
        # 찾으면 즉시 반환
        if arr[i] == target:
            return i
 
    # 찾지 못하면 -1 반환
    return -1

---

핵심 요약

개념	설명
원리	순차적으로 전체 탐색
시간복잡도	O(n)
공간복잡도	O(1)
적용 조건	정렬 불필요
활용	작은 데이터, 비정렬 데이터

---

다른 탐색과 비교

탐색	시간복잡도	정렬 필요	공간복잡도	특징
선형 탐색	O(n)	불필요	O(1)	단순, 느림
이진 탐색	O(log n)	필요	O(1)	빠름
해시 탐색	O(1)	불필요	O(n)	가장 빠름

---

주의사항

1. 조기 종료

# 찾으면 즉시 return
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 즉시 종료
    return -1

2. 빈 배열 처리

def linear_search_safe(arr, target):
    if not arr:  # 빈 배열 체크
        return -1
 
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

3. 대용량 데이터

# 대용량 데이터는 다른 방법 고려
if len(arr) > 1000:
    # 정렬 후 이진 탐색 고려
    arr.sort()
    result = binary_search(arr, target)

---

자주 나오는 문제 유형

1. 문자열에서 문자 찾기

문제: 문자열에서 특정 문자의 위치 찾기

def find_char(s, target):
    """문자열에서 문자 찾기"""
    for i in range(len(s)):
        if s[i] == target:
            return i
    return -1
 
# 테스트
print(find_char("hello", 'l'))  # 2 (첫 번째 'l')
print(find_char("hello", 'z'))  # -1
 
# Python 내장 메서드
print("hello".find('l'))  # 2
print("hello".index('l'))  # 2 (없으면 ValueError)
 
# 시간복잡도: O(n)

핵심: Python find(), index() 내부적으로 선형 탐색

---

2. 최댓값/최솟값 찾기

문제: 배열에서 최댓값의 인덱스 찾기

def find_max_index(arr):
    """최댓값의 인덱스 반환"""
    if not arr:
        return -1
 
    max_idx = 0
    for i in range(1, len(arr)):
        if arr[i] > arr[max_idx]:
            max_idx = i
 
    return max_idx
 
# 테스트
arr = [3, 7, 2, 9, 5]
print(find_max_index(arr))  # 3 (9의 인덱스)
 
# Python 내장 함수
print(arr.index(max(arr)))  # 3
 
# 시간복잡도: O(n)

핵심: 한 번의 순회로 최댓값 위치 찾기

---

3. 두 수의 합 찾기 (Brute Force)

문제: 배열에서 합이 target인 두 수의 인덱스 찾기

def two_sum_linear(arr, target):
    """두 수의 합 (선형 탐색)"""
    n = len(arr)
 
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == target:
                return [i, j]
 
    return -1
 
# 테스트
arr = [2, 7, 11, 15]
print(two_sum_linear(arr, 9))  # [0, 1] (2 + 7 = 9)
 
# 시간복잡도: O(n²)
# 공간복잡도: O(1)
 
# 더 효율적인 방법: 해시맵 O(n)
def two_sum_hash(arr, target):
    seen = {}
    for i, num in enumerate(arr):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return -1

핵심: 중첩 루프로 모든 쌍 확인

---

4. 특정 조건을 만족하는 모든 요소

문제: 조건을 만족하는 모든 요소 찾기

def find_all_condition(arr, condition):
    """조건을 만족하는 모든 요소와 인덱스"""
    result = []
 
    for i, element in enumerate(arr):
        if condition(element):
            result.append((i, element))
 
    return result
 
# 테스트
arr = [1, 5, 3, 8, 4, 9, 2]
 
# 짝수 찾기
evens = find_all_condition(arr, lambda x: x % 2 == 0)
print(evens)  # [(3, 8), (4, 4), (6, 2)]
 
# 5보다 큰 수 찾기
greater = find_all_condition(arr, lambda x: x > 5)
print(greater)  # [(3, 8), (5, 9)]
 
# List comprehension 사용
evens = [(i, x) for i, x in enumerate(arr) if x % 2 == 0]
print(evens)  # [(3, 8), (4, 4), (6, 2)]
 
# 시간복잡도: O(n)

핵심: 필터링 조건을 람다 함수로 전달

---

5. 연속된 부분 배열 찾기

문제: 특정 값들이 연속으로 나타나는 위치 찾기

def find_subarray(arr, subarray):
    """부분 배열의 시작 인덱스 찾기"""
    n = len(arr)
    m = len(subarray)
 
    for i in range(n - m + 1):
        # 부분 배열 비교
        match = True
        for j in range(m):
            if arr[i + j] != subarray[j]:
                match = False
                break
 
        if match:
            return i
 
    return -1
 
# 테스트
arr = [1, 2, 3, 4, 5, 6]
sub = [3, 4, 5]
print(find_subarray(arr, sub))  # 2
 
# 시간복잡도: O(n × m)

핵심: 각 위치에서 부분 배열 매칭 확인

---

6. 중복 제거 후 첫 요소

문제: 중복되지 않은 첫 번째 요소 찾기

def first_unique(arr):
    """중복되지 않은 첫 요소"""
    for i in range(len(arr)):
        is_unique = True
 
        # 나머지와 비교
        for j in range(len(arr)):
            if i != j and arr[i] == arr[j]:
                is_unique = False
                break
 
        if is_unique:
            return arr[i]
 
    return -1
 
# 테스트
print(first_unique([1, 2, 3, 2, 1, 4, 3]))  # 4
 
# 더 효율적인 방법: 해시맵
from collections import Counter
 
def first_unique_hash(arr):
    count = Counter(arr)
    for num in arr:
        if count[num] == 1:
            return num
    return -1
 
print(first_unique_hash([1, 2, 3, 2, 1, 4, 3]))  # 4
 
# 시간복잡도: O(n²) → O(n) with hash

핵심: 해시맵으로 O(n)에 최적화 가능

---

추천 연습 문제

기초

• LeetCode 704 - Binary Search (선형 vs 이진 비교)
• LeetCode 35 - Search Insert Position

중급

• LeetCode 1 - Two Sum
• LeetCode 283 - Move Zeroes

---

선형 탐색 최적화

1. Sentinel Search (보초 탐색)

def sentinel_search(arr, target):
    """마지막에 target 추가하여 조건 하나 제거"""
    n = len(arr)
    last = arr[n - 1]
 
    # 마지막을 target으로 변경
    arr[n - 1] = target
 
    i = 0
    while arr[i] != target:
        i += 1
 
    # 원래 값 복구
    arr[n - 1] = last
 
    # 마지막 이전에 찾았거나, 마지막이 target인 경우
    if i < n - 1 or last == target:
        return i
 
    return -1
 
# 조건문 하나 제거로 미세하게 빨라짐

---

2. Jump Search (점프 탐색)

import math
 
def jump_search(arr, target):
    """√n씩 건너뛰며 탐색"""
    n = len(arr)
    step = int(math.sqrt(n))
 
    # 건너뛰기
    prev = 0
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
 
    # 선형 탐색
    while arr[prev] < target:
        prev += 1
        if prev == min(step, n):
            return -1
 
    if arr[prev] == target:
        return prev
 
    return -1
 
# 테스트 (정렬된 배열)
arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
print(jump_search(arr, 55))  # 10
 
# 시간복잡도: O(√n)
# 정렬된 배열에서 이진 탐색보다는 느리지만 선형보다 빠름

---

언제 사용할까?

사용 가능

• 정렬되지 않은 데이터: 정렬 불필요
• 작은 데이터: n < 100 정도
• 한 번만 탐색: 정렬 비용이 더 큼
• 첫 번째 발견: 중복 시 첫 요소 반환

사용 불가

• 대용량 데이터: 정렬 후 이진 탐색
• 반복 탐색: 해시맵 또는 이진 탐색
• 성능 중요: O(log n) 또는 O(1) 필요

결론: 단순하지만 느림, 작은 데이터나 비정렬 데이터에만 사용!