탐색 알고리즘 (1): 순차 탐색 (Linear Search)

1. 순차 탐색이란?

순차 탐색(Linear Search)은 데이터 집합에서 원하는 값을 찾을 때 처음부터 끝까지 차례대로 확인하는 탐색 알고리즘이다. 가장 기본적이고 단순한 형태의 탐색 방법으로, 정렬 여부와 관계없이 사용할 수 있다.

2. 순차 탐색의 동작 원리

순차 탐색은 다음과 같은 과정으로 동작한다:

1. 첫 번째 요소부터 시작하여 목표 값과 비교한다.
2. 목표 값을 찾으면 해당 인덱스를 반환한다.
3. 끝까지 확인했지만 목표 값이 없으면 -1을 반환한다.

2.1 순차 탐색 과정 예제

다음은 배열에서 숫자 6을 찾는 과정이다:

입력 배열: [3, 5, 6, 8, 9]

1. 첫 번째 요소 3과 비교 → 불일치
2. 두 번째 요소 5와 비교 → 불일치
3. 세 번째 요소 6과 비교 → 일치 (탐색 종료)

출력: 인덱스 2

2.2 순차 탐색 예제 코드 (Java)

public class LinearSearch {
    // 순차 탐색 메서드
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // 목표 값의 인덱스 반환
            }
        }
        return -1; // 목표 값을 찾지 못한 경우
    }

    public static void main(String[] args) {
        int[] data = {3, 5, 6, 8, 9};
        int target = 6;
        int result = linearSearch(data, target);

        if (result != -1) {
            System.out.println("찾는 값의 위치: " + result);
        } else {
            System.out.println("값을 찾을 수 없습니다.");
        }
    }
}

3. 순차 탐색의 성능 분석

순차 탐색의 성능은 탐색 대상의 크기(n)에 따라 달라지며, 최선, 평균, 최악의 경우로 구분된다.

3.1 시간 복잡도

• 최선의 경우 (Best Case): O(1) → 첫 번째 요소에서 찾을 때
• 평균의 경우 (Average Case): O(n/2) ≈ O(n)
• 최악의 경우 (Worst Case): O(n) → 마지막 요소에서 찾거나 없는 경우

3.2 공간 복잡도

• 공간 복잡도: O(1) → 추가 메모리 사용 없음 (In-place 알고리즘)

4. 순차 탐색의 장점과 단점

4.1 장점

• 구현이 매우 간단하고 직관적이다.
• 정렬되지 않은 데이터에서도 사용 가능하다.
• 추가 메모리 공간을 사용하지 않는다.

4.2 단점

• 데이터 크기가 커질수록 비효율적이다.
• 평균 시간 복잡도가 O(n)으로 성능이 낮다.

5. 순차 탐색의 활용 및 개선 방법

5.1 활용 사례

• 데이터가 작거나 크기가 고정된 경우
• 정렬되지 않은 데이터에서 빠르게 구현해야 할 때
• 특정 요소의 존재 여부만 확인할 때

5.2 개선 방법

• 보초법(Sentinel Search): 마지막 요소에 목표 값을 추가해 비교 횟수를 줄임
• 이중 탐색(Two-Way Search): 양 끝에서 동시에 탐색하여 성능 개선
• 정렬 후 이진 탐색(Binary Search)로 변경: 데이터가 자주 검색된다면 정렬 후 효율적 탐색 가능

6. 결론

순차 탐색은 가장 단순한 탐색 알고리즘으로 구현이 쉽고 정렬되지 않은 데이터에서 유용하다. 그러나 시간 복잡도가 O(n)으로 데이터가 많을수록 성능이 저하되므로, 대규모 데이터에서는 이진 탐색이나 해시 탐색을 고려하는 것이 좋다.