알고리즘 | 선형 검색

✔ 학습목표

주어진 배열 또는 구조체에서 선형 검색(linear research)을 할 수 있다.

 

1) 선형 검색

자료를 검색하는 데는 다양한 알고리즘이 사용될 수 있다. 우리는 그 예시로 선형 검색과 이진 검색을 배웠다. 선형 검색은 원하는 원소가 발견될 때까지 순서대로 보는 방법이다. 본 글에서는 주어진 배열에서 선형 검색으로 값을 찾는 방법을 배운다.

 

효율성

선형 검색은 정확하지만 효율적이지 못한 방법이다(알고리즘 표기법에서 배운 대로 시간의 상한선이 O(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;
}

 

main함수 내에서 int 형으로 배열을 정의하고, 그 크기만큼 for 루프를 돌면서 인덱스마다의 값을 비교하는 프로그램이다. 만약 인덱스 중 50이라는 숫자가 있으면 printf로 결과를 출력한다. 이때 return값도 사용하는데, 값을 찾으면 0을 아니면 1을 반환한다. 

 

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

 

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

 

 

배열 name과 number을 문자열로 선언한 후 for 루프 내에서 각 인덱스마다 값을 비교하는 프로그램이다. 이 경우 코드 자체에는 문제가 없지만 배열 내 값이 한 쌍임에도 불구하고 서로 다른 인덱스를 가진다는 한계가 있다.   

 

* C에서는 문자열을 '=='로 비교할 수 없기 때문에 strcmp(string compare) 함수를 사용했다. 이는 string.h라이브러리를 추가해야 사용이 가능하다. syntax는 다음과 같다.

 

#include <string.h>

int strcmp(const char *s1, const char *s2);

 

 

2) 구조체

여러 데이터를 관리해야 할 때 좋은 방법 중 하나가 구조체(struct)를 사용하는 것이다. 구조체의 syntax는 다음과 같다.

 

struct structureName 
{
    dataType member1;
    dataType member2;
    ...
};

 

간단한 사용 예시를 보자.

 

struct Person
{
    char name[50];
    int citNo;
    float salary;
};

int main()
{
    struct Person person1, person2, p[20];
    return 0;
}

 

위와 같은 내용을 다른 방식으로도 표현 가능하다.

 

struct Person
{
    char name[50];
    int citNo;
    float salary;
} person1, person2, p[20];

 

위의 두 예제 모두에서 struct Person 형의 변수 person1과 person, p[20]이 만들어진다.

 

구조체에 대해 배웠으니 앞선 선형 검색의 문자열 예제를 이어가보자.

 

#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이라는 이름의 구조체를 자료형으로 정의했다. main함수 내에서 person 자료형의 배열을 선언하면 그 안에 포함된 속성 값은 '.'로 연결해서 접근할 수 있다. person a라는 변수가 있으면 a.name은 이름, a.number은 전화번호를 각각 저장하는 변수가 되는 것이다. 이처럼 구조체를 사용하면 더욱 확장성 있는 프로그램을 만들 수 있다.

 

* typedef는 C에서 자료형에 새로운 이름, 쉽게 말해 별칭을 붙일 때 사용하는 키워드다.

 

 

 

- 구조체의 syntax 및 예제

C struct (Structures)

---

 

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 본 강좌 내 실습에서는 CS50 Sandbox를 사용합니다.

 

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