[CS50] 선형 검색

이번에는 주어진 배열에서 선형 검색으로 값을 찾는 방법을 공부해보려고 합니다. 전화번호부 같이 한개의 배열이 아닌 여러 개의 배열이 있는 경우 한 배열의 특정 속성 값을 찾고 동일한 위치의 다른 배열의 속성 값을 출력하는 방법을 공부해보도록 하겠습니다.

 

선형 검색은 지난 포스팅에서 정리했듯이 처음부터 끝까지 원하는 원소를 찾을 때까지 차례대로 검색하는 것을 말합니다.

선형 검색의 정확성이나 효율성을 따져본다면 처음부터 끝까지 모든 자료를 확인한다는 것에 정확하다고는 할 수 있지만 효율적이지는 않습니다. 만약 100만 개의 원소가 있는 리스트에 원하는 자료가 가장 마지막에 있다거나 리스트 안에 없다면 이처럼 효율성이 매우 떨어지는 작업은 없을 겁니다.

따라서 선형 검색은 자료가 정렬되어있지 않거나 그 어떤 정보도 없어서 하나씩 찾아야 하는 경우에 유용합니다.

#include <stdio.h>

int main(void)
{
    int numbers[] = {4, 6, 15, 16, 23, 42};

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

위 코드처럼 주어진 배열에서 선형 검색을 사용해 원하는 값이 있는지를 검사하면 됩니다.

 

숫자형이 아닌 문자열로 이루어진 배열 역시 이와 비슷하게 코드를 작성할 수 있습니다.

만약 전화번호부에서 특정 이름을 찾아 해당하는 전화번호를 출력하는 프로그램을 작성해보면

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

	// EMMA를 찾기
    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배열과 동일한 index의 numbers값을 출력하는 코드입니다.

단 이 코드의 단점은 names와 numbers가 배열이 서로 같은 인덱스를 가져야 한다는 겁니다. 만약 여기에서 names를 알파벳 순서로 정렬 해버 리거나 numbers의 index가 하나가 추가될 경우 이 코드는 동작하지 않는다는 겁니다.

 

위의 단점을 극복하는 좋은 방법은 이름과 번호를 묶어주는 거겠죠?

#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는 C의 정의된 키워드로 여러 가지 자료형을 담을 수 있습니다. 따라서 문자열 name과 number를 담는 구조체(struct)를 person이라는 이름으로 정의한다는 의미를 갖습니다. 그러면 그 안의 속성 값을 '.'으로 연결해서 접근할 수 있게 됩니다.

자료형인 person의 배열의 이름을 people이라고 한다면 people.name과 people.number로 각각 이름과 전화번호를 저장해 보다 더 확장성 있는 전화번호부 검색 프로그램을 만들 수 있습니다.

 

---

출처

본 내용은 CS50의 2019년 강의를 듣고 작성했습니다. (개념이 어느 정도 정리되면 최신강의도 다시 듣고 수정할 내용 있으면 수정하겠습니다.)

 

강의 자료는 EdX에서 무료로 사용할 수 있고 boostcourse에서 한글 강의로도 들을 수 있습니다.