4: 알고리즘-3(선형 검색:Linear Search)

선형검색

찾고자 하는 자료를 검색하는 데 사용되는 다양한 알고리즘 중 하나

선형검색은 원하는 값이 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색하는 방법

 

---

효율성과 비효율성

• 선형 검색 알고리즘은 정확하지만 효율적이지 못한 방법
• 리스트의 길이가 n일 때, 최악의 경우 리스트의 모든 값을 확인해야 해서 n번만큼 실행됨
• 최악의 상황(worst case)은 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우
• 최선의 상황은 처음 시도했을 때 찾고자 하는 값이 있는 경우
• 선형검색은 자료가 정렬되어 있지 않거나 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용함
• 정렬은 시간이 오래 걸리고 공간을 더 차지하지만 이 과정을 진행하면 여러 번 리스트를 검색해야 하거나 매우 큰 리스트를 검색해야 할 경우 시간을 단축할 수 있음

---

주어진 numbers 배열에서 50이라는 특정 값을 찾기 위해서 선형 검색을 사용하는 코드를 작성

 

#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");
      }
    }
    printf("Not found\n");
}

 

배열의 크기만큼 for 루프를 돌면서 배열의 인덱스를 차례대로 방문해 찾는 값(50)이 있는 지를 검사함

결과는 numbers 배열 안에 50이 없기 때문에 "Not found"가 출력됨!

---

전화번호부에서 이름을 찾는 것이라 가정하고 숫자가 아니라 이름을 찾아보는 코드를 작성

 

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

    for (int i = 0; i <4; i++)
    {
        if (names[i] == "EMMA")  //오류
        {
            printf("Found\n");
        }    
    }
    printf("Not found\n");
}

 

출력이 안되고 오류가 되는 이유: ==는 문자열에 사용할 수 없음

→ 문자열은 자체가 배열로 여러 개의 문자로 구성되어 있기 때문에 char, bool, float, int와는 다름. 두 문자열을 비교하고 싶다면 문자열 속에 문자를 하나씩 비교해야 함

→ 파이썬이나 자바 같은 다른 언어에서는 한 줄로 비교가 가능하지만 C는 모든 것이 로우 레벨로 진행되기 때문에 문자열을 비교하기 위해 등호를 사용할 수 없음

---

<string.h> 라이브러리에 포함되어 있는 문자열을 비교하는 함수 strcmp()을 사용하면 문자열을 비교할 수 있음. strcmp 함수는 두 문자열이 같다면 0을 반환함.

 

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

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

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

 

결과

- strcmp함수로 올바르게 코드를 작성했지만 Found와 Not found가 출력됨

- 코드 안에서 Not found는 계속 출력되기 때문에 함수가 종료됐다는 의미인 return을 작성해주기!

- return은 함수 내의 변수나 어떤 값을 돌려주는 역할을 하기 때문에 성공했다는 의미인 0을 반환시켜 줘야 함(0이 반환되게 되면, 즉 True가 되기 때문에 출력이 돼서 끝남)

- return 옆 숫자 자체에는 큰 의미가 없는 관습(0은 성공, 1은 실패를 의미)

---

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

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

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

 

결과

---

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

 

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

int main(void)
{
    string names[4] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
    string numbers[4] = {"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("%s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

 

names 배열과 numbers 배열을 따로 정의하고 names 배열에서  해당하는 인덱스의 numbers 배열의 값을 출력함!

numbers 배열을 string으로 선언한 이유: 숫자처럼 보이지만 다른 요소들이 많다면 정수형(int)으로 나타내는 것은 좋지 않음(예를 들면 전화번호 010-1234-5678에 – 괄호도 있기 때문에 이것은 문자가 아닌 숫자로!)

 

결과

결괏값은 올바르게 나오지만 이 경우에 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";

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

 

• typedef는 새로운 타입을 정의한다는 의미이고, struct(구조체)는 C에 미리 정의된 키워드임. 그릇처럼 여러 가지 자료형을  담을 수 있음(struct는 여러 자료형을 위한 그릇) 
• 이 구조체에 이름과 전화번호를 저장하고 이름을 person으로 정의함!(컴파일러에게 int, float, char, bool, string 뿐만 아니라 person이라는 자료형이 있다고 알려줄 수 있음)
• 이렇게 하면 모든 정보를 한 번에 묶어서 표현할 수 있음! person 자료형의 값이 4개 있고, 각각의 person 안에는 이름과 번호가 들어있음
• person이라는 이름의 구조체를 자료형으로 정의하고 person 자료형의 배열을 선언하면 그 안에 포함된 속성 값은 "."으로 연결해서 접근할 수 있음(만약 person a;라는 변수가 있다면 a.name 또는 a.number가 각각 이름과 전화번호를 저장하는 변수가 될 수 있음) 
• 이전과 출력 값은 같지만 더 잘 설계된 코드가 완성됨!(캡슐화가 됨)

https://www.boostcourse.org/cs112/joinLectures/41307

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

https://everysmallstep.tistory.com/24

4: 알고리즘-1(검색 알고리즘)