탐색 - 2. 선형 탐색(Linear Search)

📌 2. 선형 탐색(Linear Search)

---

2.1 선형 탐색(Linear Search)의 개념 및 동작 방식

선형 탐색(Linear Search)은 가장 기본적인 탐색 알고리즘으로, 배열이나 리스트의 요소를 처음부터 끝까지 차례대로 비교하며 원하는 값을 찾는 방식입니다.

🔹 동작 원리

1. 배열의 첫 번째 요소부터 순차적으로 탐색을 시작합니다.
2. 찾고자 하는 값과 현재 요소를 비교합니다.
3. 값이 일치하면 해당 인덱스를 반환하고 탐색을 종료합니다.
4. 끝까지 탐색했지만 값이 없으면 실패로 처리합니다.

🔹 예제

다음은 정수 배열에서 특정 값을 찾는 과정을 예로 듭니다.

배열:

[ 5, 8, 12, 20, 25, 30 ]

찾고자 하는 값: 20

• 첫 번째 요소(5) 비교 → 불일치
• 두 번째 요소(8) 비교 → 불일치
• 세 번째 요소(12) 비교 → 불일치
• 네 번째 요소(20) 비교 → 일치! (탐색 성공, 인덱스 3 반환)

---

2.2 최선/최악/평균 시간 복잡도 분석 (O(n))

🔹 시간 복잡도

경우	설명	시간 복잡도
최선 (Best Case)	찾고자 하는 값이 첫 번째 요소에 위치한 경우	O(1)
최악 (Worst Case)	찾고자 하는 값이 배열의 마지막 요소이거나 존재하지 않는 경우	O(n)
평균 (Average Case)	배열 내 임의의 위치에 있는 값을 찾는 경우	O(n/2) ≈ O(n)

💡 결론: 선형 탐색은 데이터 크기가 커질수록 탐색 시간이 길어지는 비효율적인 방법입니다.
따라서, 데이터가 많을 경우 이진 탐색(Binary Search) 또는 해싱(Hashing) 같은 효율적인 탐색 방법을 고려해야 합니다.

---

2.3 선형 탐색의 한계점

🔹 단점

1. 비효율적
   • 최악의 경우 배열의 모든 요소를 검사해야 하므로 데이터 크기가 클수록 실행 시간이 증가합니다.
2. 정렬 여부와 무관하지만 개선되지 않음
   • 정렬된 배열이어도 탐색 속도가 향상되지 않습니다. (이진 탐색과 대비되는 점)
3. 매번 처음부터 검색해야 함
   • 해싱(Hashing)처럼 즉각적인 검색(O(1))이 불가능하고, 항상 처음부터 차례대로 검사해야 함.

🔹 언제 사용해야 할까?

✔ 데이터의 크기가 작을 때 (ex: 100개 이하)
✔ 데이터가 정렬되지 않았고, 별도의 추가 메모리 사용이 불가능할 때
✔ 간단한 구현이 필요한 경우

---

🔍 실습: 배열에서 특정 값을 찾는 선형 탐색 구현

1️⃣ C 언어로 선형 탐색 구현 (for 루프 사용)

#include <stdio.h>

// 선형 탐색 함수
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // 값이 발견된 경우 인덱스 반환
        }
    }
    return -1; // 값이 없는 경우 -1 반환
}

int main() {
    int numbers[] = {10, 20, 30, 40, 50, 60, 70};
    int size = sizeof(numbers) / sizeof(numbers[0]); // 배열 크기 계산
    int target = 40; // 찾을 값

    int result = linearSearch(numbers, size, target);

    if (result != -1) {
        printf("값 %d은(는) 인덱스 %d에 있습니다.\n", target, result);
    } else {
        printf("값 %d을(를) 찾을 수 없습니다.\n", target);
    }

    return 0;
}

📌 실행 결과

값 40은(는) 인덱스 3에 있습니다.

---

🔍 실습: 배열 크기 증가 시 실행 속도 비교 (clock() 사용)

데이터 크기가 증가할수록 선형 탐색이 얼마나 느려지는지 확인하는 코드입니다.

2️⃣ 실행 속도 비교 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 선형 탐색 함수
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // 값이 발견된 경우 인덱스 반환
        }
    }
    return -1; // 값이 없는 경우 -1 반환
}

int main() {
    int size = 100000; // 큰 배열 크기 설정
    int *numbers = (int *)malloc(size * sizeof(int)); // 동적 배열 할당

    // 배열 초기화 (1부터 size까지)
    for (int i = 0; i < size; i++) {
        numbers[i] = i + 1;
    }

    int target = size; // 마지막 값 찾기 (최악의 경우)

    // 시간 측정 시작
    clock_t start = clock();
    int result = linearSearch(numbers, size, target);
    clock_t end = clock();

    double time_spent = (double)(end - start) / CLOCKS_PER_SEC;

    if (result != -1) {
        printf("값 %d은(는) 인덱스 %d에 있습니다.\n", target, result);
    } else {
        printf("값 %d을(를) 찾을 수 없습니다.\n", target);
    }

    printf("실행 시간: %.6f 초\n", time_spent);

    free(numbers); // 동적 메모리 해제
    return 0;
}

📌 실행 결과 (예시)

값 100000은(는) 인덱스 99999에 있습니다.
실행 시간: 0.005678 초

💡 데이터 크기가 100,000개일 때도 실행 속도가 빠르지만, 1,000,000개 이상으로 커지면 실행 시간이 급격히 증가할 수 있습니다.
이럴 때 이진 탐색(Binary Search) 또는 해싱(Hashing) 같은 효율적인 방법을 사용하면 성능을 크게 향상시킬 수 있습니다.

---

📌 마무리 및 정리

• 선형 탐색(Linear Search)은 데이터를 처음부터 끝까지 순차적으로 검색하는 기법이다.
• 최선 O(1), 최악 O(n), 평균 O(n)의 시간 복잡도를 가진다.
• 데이터 크기가 커질수록 속도가 느려지는 단점이 있다.
• 작은 데이터셋에서는 간단한 구현으로 유용하지만, 큰 데이터셋에서는 이진 탐색(Binary Search)이나 해싱(Hashing)을 고려해야 한다.
• clock()을 이용한 실행 시간 비교 실습을 통해 탐색 속도 변화를 확인할 수 있다.