[알고리즘] 선형 검색

주어진 배열에서 선형 검색으로 값을 찾는 방법을 알아보자.

또, 전화번호부와 같이 배열이 여러개가 있는 경우, 한 배열의 특정 속성값을 찾고 동일한 위치의 다른 배열의 속성값을 출력하는 방법도 알아보며 이를 더 간단하고 확장성있게 구현하는 방법을 배워보자.

선형 검색

선형검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색한다.

즉, 찾고자하는 자료를 찾을 때까지 모든 자료를 확인해야 한다.

효율성 그리고 비효율성

선형 검색 알고리즘은 정확하지만 효율적이지 못한 방법이다.

길이가 n인 리스트에서 자료를 찾을 때, 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우에는 n번만큼 실행되기 때문이다.

반대로 처음 시도했을 때 찾고자 하는 값이 있는 경우도 있을 수 있지만, 평균적으로는 선형 검색이 최악의 상황에서 종료되는 것에 가깝다고 가정할 수 있다.

선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없이 하나씩 찾아야 하는 경우에 유용하다. 이 경우에는 무작위로 탐색하는 것보다 순서대로 탐색하는 것이 더 효율적이기 때문이다.

따라서, 검색 이전에 정렬을 해주는 것이 좋지만 정렬에는 시간이 오래 걸리고 공간을 더 차지한다는 문제가 있다.

만약 여러번 검색을 해야하거나 매우 큰 리스트를 검색해야 할 경우에는 다음과 같은 작업을 통해 시간을 단축할 수 있다.

다음은 주어진 배열에서 특정 값을 찾기 위해 선형 검색을 사용한 코드이다.

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

int main(void)
{
    // numbers 배열 정의 및 값 입력
    int numbers[] = {4, 8, 15, 16, 23, 42};

    // 값 50 검색
    for (int i = 0; i < 6; i++)
    {
        if (numbers[i] == 50)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

• 배열의 크기만큼 for루프를 돌면서 배열의 인덱스를 차례대로 방문하며 찾는 값이 있는지를 검사한다.
  
  

문자열로 이루어진 배열도 비슷한 방식으로 검색할 수 있다.

다음은 전화번호부에서 특정 이름을 찾아 해당하는 전화번호를 출력하는 코드이다.

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

int main(void)
{
    string names[] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
    string numbers[] = {"617–555–0100", "617–555–0101", "617–555–0102", "617–555–0103"};

    for (int i = 0; i < 4; i++)
    {
        if (strcmp(names[i], "EMMA") == 0)
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

• names배열과 numbers배열을 따로 정의하고 names배열에서 검색하여 해당하는 인덱스의 numbers배열 값을 출력한다.

그러나, 이 방식은 names배열과 numbers배열이 서로 같은 인덱스를 가져야 한다는 한계가 있다.

이를 해결하기 위해서는 다음과 같이 새로운 자료형으로 구조체를 정의해 이름과 번호를 묶어주는 것이 좋다.

#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;
}

• person이라는 이름의 구조체를 자료형으로 정의하고 person자료형의 배열을 선언하면 그 안에 포함된 속성값은 .으로 연결해서 접근할 수 있다.
• person a;라는 변수가 있다면, a.name 또는 a.number이 각각 이름과 전화번호를 저장하는 변수가 되는 것이다.

이렇게 더욱 확장성 있는 전화번호부 검색 프로그램을 만들 수 있다.

생각해보기

전화번호부와 같이 구조체를 정의하여 관리 및 검색을 하면 더 편리한 에는 또 무엇이 있을까?

정답

• 주소록 : 이름, 주소
• 도서관 : 책의 제목, 저자, 장르
• 상품관리 : 상품명, 가격, 재고 수량
• 예약 시스템 : 예약자명, 날짜, 서비스 유형