선형 검색(Linear Search) 완벽 분석: C 언어 예제와 성능 최적화 방법

1. 선형 검색(Linear Search)란? 

선형 검색(순차 검색)은 가장 기본적인 검색 알고리즘으로, 배열의 처음부터 끝까지 차례대로 확인하면서 원하는 값을 찾는 방법이다.

 

📌 동작 방식:

1. 배열의 첫 번째 원소부터 시작해서 원하는 값과 비교한다.
2. 일치하는 값을 찾으면 검색을 종료하고 해당 위치를 반환한다.
3. 배열의 끝까지 비교했음에도 찾지 못하면 검색 실패를 알린다.

❗장점:

1. 배열이 정렬되어 있지 않아도 사용할 수 있다.
2. 구현이 간단하고 직관적이다.

❗ 단점:

1. 비효율적이다. 최악의 경우 배열의 모든 요소를 확인해야 하므로 시간 복잡도가 O(n)이다.
2. 데이터 크기가 클수록 검색 속도가 느려진다.

 

2. 정수 배열에서의 선형 검색 예제

다음 코드는 numbers 배열에서 특정 숫자를 찾는 선형 검색을 수행한다.

#include <stdio.h>

int main(void)
{
    int numbers[] = {4, 8, 15, 16, 23, 42};  // 검색할 정수 배열

    for (int i = 0; i < 6; i++)  // 배열의 모든 요소를 순회
    {
        if (numbers[i] == 50)  // 현재 요소가 찾는 값(50)과 같은지 확인
        {
            printf("Found\n");
            return 0;  // 찾으면 프로그램 종료
        }
    }
    printf("Not found\n");  // 배열을 끝까지 검색했는데 못 찾으면 "Not found" 출력
    return 1;  // 검색 실패를 나타내는 반환 값
}

 

📌 코드 설명

• numbers[] 배열에서 50이 있는지 확인한다.
• 배열을 처음부터 끝까지 차례대로 탐색하면서 50과 같은 값이 있는지 확인한다.
• 발견하면 즉시 출력 후 프로그램 종료 (return 0;)
• 배열 끝까지 찾지 못하면 "Not found"를 출력하고 1을 반환한다.

❗ 만약 배열 크기가 100만 개라면?

• 최악의 경우 100만 번 비교해야 한다 → 비효율적
• 데이터가 많아질수록 속도가 느려지므로 더 빠른 검색 방법이 필요하다 → 이진 검색(Binary Search)나 해시 테이블 사용 고려

 

3. 문자열에서 선형 검색을 사용할 때 주의할 점

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    string names[4] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};

    for (int i = 0; i < 4; i++)
    {
        if (names[i] == "EMMA") // ❌ 잘못된 코드
        {
            printf("Found\n");
        }
    }
    printf("Not found\n");
}

 

*위의 코드는 제대로 작동하지 않는다.

이 코드에서 if (names[i] == "EMMA")는 문자열을 비교하려는 코드인데, C에서는 문자열을 단순히 == 연산자로 비교할 수 없다. 그 이유는 다음과 같다:

1. "EMMA"는 문자열 리터럴이다. 즉, 문자열 리터럴 "EMMA"는 메모리상에서 'E', 'M', 'M', 'A', '\0' 이렇게 5개의 문자가 저장된 메모리 공간의 시작 주소를 가리키는 포인터이다.
2. names[i]는 배열의 i번째 요소로, "EMMA"라는 문자열을 가리키는 포인터이다. 즉, names[0]은 "EMMA"라는 문자열을 가리키고, 그 문자열이 저장된 메모리 주소를 가리키는 포인터이다.

따라서, == 연산자는 두 포인터가 가리키는 주소가 같은지 비교할 뿐, 이름이 같은지를 비교하지 않는다. 문자열의 내용을 비교하려면 strcmp()와 같은 함수가 필요하다. 이 함수는 두 문자열을 하나씩 비교하여 동일하면 0을 반환하고, 다르면 다른 값을 반환한다.

 

 

 

✅ 올바른 문자열 비교 코드

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string names[] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};  // 이름 목록

    for (int i = 0; i < 4; i++)  // 배열 전체 탐색
    {
        if (strcmp(names[i], "EMMA") == 0)  // ✅ 올바른 문자열 비교
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");  // 찾지 못하면 "Not found" 출력
    return 1;
}

 

📌 strcmp() 함수의 동작 원리

• strcmp(str1, str2)는 두 문자열을 비교하고, 만약 두 문자열이 동일하면 0을 반환한다.
• "EMMA"와 names[i]가 같다면 strcmp(names[i], "EMMA") == 0이 되어 "Found"를 출력하고 프로그램을 종료한다.
• 단, strcmp() 함수를 사용하려면 string.h를 위에서 불러와야 한다. 그 이유는 strcmp() 함수가 string.h 라이브러리에 정의되어 있기 때문이다. 만약 이 헤더 파일을 포함하지 않으면, 컴파일 시 strcmp() 함수가 무엇인지 알 수 없어 에러가 발생할 것이다.

 

4. 선형 검색의 한계: 구조체를 활용한 데이터 관리

문제점:

• 만약 "EMMA"를 찾았을 때, 그 사람의 전화번호도 함께 검색하려면 어떻게 해야 할까?
• 가장 간단한 방법은 이름 배열과 전화번호 배열을 따로 두는 것이다.

string names[] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
string numbers[] = {"617-555-0100", "617-555-0101", "617-555-0102", "617-555-0103"};

하지만 이 방법은 데이터의 일관성을 유지하기 어렵다.
예를 들어, 만약 names[] 배열의 순서가 바뀌면 numbers[] 배열의 정보도 바뀌어야 한다.
이런 문제를 해결하려면 구조체(struct)를 사용하면 된다:)

 

 

여기서 잠깐!

그런데 전화번호는 왜 문자열이어야 할까?

전화번호에는 하이픈(-), 괄호(()), 심지어 해외번호에서 사용하는 플러스(+) 기호가 포함될 수 있다.
이러한 기호들은 숫자가 아니라 문자로 취급되므로, 전화번호는 문자열로 처리해야 한다. 만약 전화번호를 정수형(int, long)으로 처리한다면, 기호들(하이픈, 플러스 등)을 저장할 수 없기 때문이다.

 

또한, 전화번호는 숫자처럼 보이지만, 그 속에 문자 요소들이 포함되어 있기 때문에 숫자형 변수에 넣는 것이 적합하지 않다. 예를 들어, 전화번호의 맨 앞에 0이 올 수 있는데, 정수형 변수에서는 선행 0이 생략되므로, 이를 문자 배열로 다루는 것이 더 자연스럽다. 따라서, 전화번호를 문자열 배열로 저장하는 것이 적합하다.

    

 

5. 구조체를 활용한 검색 (전화번호부 예제)

✅ struct를 사용하여 name과 number를 하나의 데이터 단위로 저장

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// 구조체 정의
typedef struct
{
    string name;   // 이름
    string number; // 전화번호
} person;

int main(void)
{
    // 구조체 배열을 사용하여 데이터를 저장
    person people[4];

    people[0].name = "EMMA";
    people[0].number = "617–555–0100";
    people[1].name = "RODRIGO";
    people[1].number = "617–555–0101";
    people[2].name = "BRIAN";
    people[2].number = "617–555–0102";
    people[3].name = "DAVID";
    people[3].number = "617–555–0103";

    // EMMA 검색
    for (int i = 0; i < 4; i++)
    {
        if (strcmp(people[i].name, "EMMA") == 0)
        {
            printf("Found %s\n", people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

 

📌 코드 설명

• 여기서 typedef struct는 struct 타입을 정의하고, person이라는 새로운 이름을 그 구조체 타입에 붙여준 거다.
• struct는 구조체를 정의하는 키워드다. 즉, 여러 개의 변수(필드)를 하나의 단위로 묶을 때 사용된다.
• (다시말해서-)typedef는 새로운 이름을 정의하는 것이다. 즉, 기존에 존재하는 타입에 대해 다른 이름을 붙이는 데 사용된다. 따라서, 위의 예시처럼 struct라는 타입을 person라는 이름으로 바꿀 수 있다. 이렇게 하면, 이후에 person를 struct 대신 사용할 수 있게 되는것! ㅎㅎ
• (again ㅋㅋㅋ 다시말해서-) person이라는 새로운 자료형을 정의하여, name과 number를 묶어 하나의 단위로 관리한다.
• people이라는 배열에 여러 사람의 정보를 저장한 후, 선형 검색을 사용하여 "EMMA"를 찾고 해당 전화번호를 출력한다.
• 만약 "EMMA"가 발견되면 그 사람의 전화번호가 출력되고, 그렇지 않으면 "Not found"가 출력된다.

✅ 장점

• 구조체를 사용하면 이름과 번호를 함께 묶어 관리할 수 있어 데이터의 일관성을 유지할 수 있다. 🥰
• 데이터가 많아지면 구조체에 새로운 필드를 추가하여 더 많은 정보를 저장할 수 있다.

 

🧐 왜 typedef를 사용하나?

1. 가독성 향상:
   긴 자료형을 간단하게 줄여서 사용할 수 있다. 예를 들어, struct person을 계속 쓰는 것보다 Person이라고 짧게 사용할 수 있으니까(: 사실 typedef는 타입 정의(Type Definition)의 약자로, C 언어에서 새로운 자료형을 정의할 때 사용되는 키워드다. 앞서 설명했듯, 기존의 데이터 타입에 대해 더 간단하고 직관적인 이름을 부여할 수 있다. typedef를 사용하면 복잡한 타입을 다룰 때 코드의 가독성을 높일 수 있고, 관리하기 더 쉽게 만들 수 있다는 장점이 있다는 것. 💕
2. 코드 관리 용이:
   만약 구조체나 다른 타입을 바꿔야 할 때, typedef를 사용하면 타입 정의만 수정하면 되니까, 코드 전반에 걸쳐 수정할 필요 없이 편리하게 관리할 수 있다.

 

🧐 typedef의 다양한 용도?

• 구조체, 배열, 포인터, 함수 포인터 등 여러 타입을 재정의 가능.
• 예를 들어, 포인터를 typedef로 간단히 정의할 수도 있다.

 

6. 선형 검색의 시간 복잡도

데이터 크기(n) 최선의 경우 (O(1)) 최악의 경우 (O(n))

10개	1번 비교	10번 비교
1,000개	1번 비교	1,000번 비교
1,000,000개	1번 비교	1,000,000번 비교

• 최선의 경우(O(1)): 찾는 값이 배열의 첫 번째 요소에 있는 경우
• 최악의 경우(O(n)): 찾는 값이 배열의 마지막 요소이거나 없는 경우

➡ 데이터가 많아질수록 선형 검색은 비효율적!
➡ 이진 검색(Binary Search) 또는 해시 테이블(Hash Table) 같은 효율적인 검색 방법을 고려해야 한다.

• 이진 검색은 데이터가 정렬되어 있을 때 O(log n)의 시간 복잡도로 검색할 수 있어 선형 검색보다 훨씬 효율적이다.
• 해시 테이블은 키를 기반으로 값을 빠르게 찾을 수 있어 O(1) 시간에 검색할 수 있다.

---

+ 정리

 

✅ 선형 검색은 단순하고 구현이 쉬운 알고리즘이다.
✅ 하지만 데이터가 많아질수록 검색 속도가 느려진다.
✅ 문자열 검색 시 strcmp()를 사용해야 한다.
✅ 구조체를 사용하면 데이터 일관성을 유지할 수 있다.
✅ 더 빠른 검색이 필요하면 이진 검색(Binary Search) 또는 해시 테이블(Hash Table)을 고려해야 한다.