[CS50] 알고리즘 - 선형 검색(Linear Search)

선형 검색(Linear Search)

• 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색한다.
• 찾고자 하는 자료를 찾을 때까지 모든 자료를 확인해야 한다.
• 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용하다.
  (이 경우에는 무작위 탐색보단 순서대로 탐색하는 것이 효율적이다.)

 

효율성/비효율성

• 정확하지만 아주 효율적이지 못한 방법이다.
• 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우에 효율성이 매우 떨어짐을 느낀다. (최악의 상황)
  (반대로 최선의 상황은 처음 시도했을 때 찾고자 하는 값이 있는 경우이다.)
• 평균적으로 선형 검색이 최악의 상황에서 종료되는 것에 가깝다고 가정할 수 있다. 

 

검색 이전에 정렬을 해줘야 한다.
정렬은 시간이 오래 걸리고 공간을 더 차지하지만 이 추가과정을 진행한다면 추후에 여러번 리스트를 검색해야 하거나 매우 큰 리스트를 검색해야 할 경우에 시간을 단축할 수 있다.

 

 

 

[코드1]

// phonebook.c
#include <cs50.h>
#include <stdio.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<6; i++)
    {
        if (strcmp(names[i], "EMMA") == 0) // C언어에서는 names[i] == "EMMA" 사용 못한다. 자료형이 다르기 때문에
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1; // 성공적이지 않았다면 1 반환 (관습)
}

$ make phonebook
$ ./phonebook
617–555–0100

=> names 배열과 numbers 배열이 서로 같은 인덱스를 가져야 한다는 한계가 있다.

=> names의 값들을 알파벳 순서대로 정렬을 한다면 numbers의 값들 또한 다시 정렬을 해야한다.

=> 새로운 자료형으로 구조체를 정의해서 이름과 번호를 묶어 주는 방법으로 [코드1]의 한계를 극복할 수 있다.

 

 

[코드2]

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

// struct는 구조체를 의미한다. C에서 미리 정의된 키워드로 여러가지 자료형을 담을 수 있다.
typedef struct // typedef : 새로운 타입을 정의한다.
{
    string name; // 사람 이름
    string number; // 전화번호 
}
person; // 이 구조체를 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;
}

=> 이름순으로 정렬해도 이름과 번호의 관계는 그대로 유지된다.

=> [코드1]보다 더욱 확장성 있는 전화번호부 검색 프로그램을 만들 수 있다.

=> 웹, 모바일, 게임 프로그램 등을 작업하게 된다면 [코드2]처럼 캡슐화를 하여 많은 관련 정보를 한 번에 관리할 일이 많을 것이다. 

 

think about

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

회원 정보, 시험 성적, 건강검진 기록, 책 정보 등

 

David J. Malan의 강의

모두를 위한 컴퓨터 과학 (CS50 2019)