[CS][CS50] 알고리즘 - 검색 알고리즘 / 알고리즘 표기법 / 선형 검색

boostcource
모두를 위한 컴퓨터 과학 (CS50 2019) : David J. Malan
www.boostcourse.org/cs11
실습환경 : CS50 Sandbox & CS50 IDE

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

 

검색 알고리즘

 

배열을 복습하자면

한 자료형의 여러 값들이 메모리상에 모여있는 구조를 말한다.

 

컴퓨터는 이 값들에 접근할 때 배열의 인덱스(indx)를 이용해 하나 하나 찾아보아야 한다.

 

 

특정 값이 배열 안에 존재하는지를 확인하는 방법(검색 알고리즘)은

배열이 정렬되어 있는지 여부에 따라 선형 검색과 이진 검색을 사용할 수 있다.

 

 

선형 검색

배열이 정렬되어 있지 않은 경우에 사용하기 좋은 검색 알고리즘.

배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문한다.

 

예시로, 위와 같은 6개의 캐비넷 안에 랜덤한 숫자들이 들어가 있고 우리는 여기에서 50을 찾으려고 한다.

 

이 때 선형 검색을 이용한다면?

왼쪽 캐비넷부터 오른쪽 캐비넷까지 하나 하나 열어서 '50 있나~?' 찾아보는 것이다.

선형 검색

 

 

 

이진 검색

배열이 정렬되어 있는 경우에 사용하기 좋은 검색 알고리즘.

배열의 중간 인덱스부터 시작해서 찾고자 하는 값과 비교하며 그 보다 작거나 큰 인덱스로의 방문을 반복한다.

 

아까의 캐비넷은 랜덤으로 숫자가 들어 있었지만 이번에는 오름차순으로 숫자를 다시 배치했다.

이진 검색을 이용해 캐비넷을 열어본다면?

중간 캐비넷부터 열어 50보다 작으면 왼쪽 캐비넷으로, 크다면 오른쪽 캐비넷으로 이동하며 찾아보면 된다.

이진 검색

 

 

비교해보자면

배열이 정렬되어 있는 경우에는 이진 검색이 선형 검색보다 훨씬 효율적이다.

다만 배열이 정렬되어 있지않은 경우에는 이진 검색을 사용할 수 없기에 선형 검색을 해야한다.

 

 

 

---

알고리즘 표기법

이전에 작성한 포스팅
'[JAVASCRIPT][CS] 자바스크립트 배열의 시간 복잡도' 참고

 

각 알고리즘이 실행하는데 걸리는 시간은 그림으로 표현이 가능한데

아래와 같이 직선 또는 굴곡이 있는 선형의 형태를 갖게 된다.

[출처] 모두를 위한 컴퓨터 과학 (CS50 2019) 7-2

 

 

Big O 표기법

위와 같은 그림을 공식으로 표기한 것이 Big O 표기법이다.

Big O 표기법은 알고리즘 실행 시간의 상한을 나타낸 것으로, 쉽게 말하자면 최악의 경우 걸리는 시간이다.

• O(n^2)
• O(n log n)
• O(n) - 선형 검색
• O(log n) - 이진검색
• O(1)

 

Big Ω 표기법

Big O 와는 반대로 알고리즘 실행 시간의 하한을 나타낸 것이다.

운이 좋아서 한 번에 검색하는 경우와 같이 최고의 경우 걸리는 시간이다.

• Ω(n^2)
• Ω(n log n)
• Ω(n) - 배열 안에 존재하는 값의 개수 세기
• Ω(log n)
• Ω(1) - 선형 검색, 이진 검색

 

 

소프트웨어의 성능을 확인하기 위해서는

운 좋게 몇번 만에 성공하는 경우를 측정하기 보다는 한계가 어디까지인지를 알아보곤 한다.

즉, 알고리즘의 성능을 알기 위해서는 Ω(하한) 보다는 O(상한) 를 보는 것이 더 중요하다.

 

 

 

---

선형 검색

원하는 요소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색하는 방법

 

정확하지만 아주 효율적이지는 못하다.

만일 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우를 최악으로 볼 수 있다.

찾고자 하는 자료가 맨 앞에 있는 최선의 경우도 존재하지만 평균적으로 효율성이 떨어진다.

 

때문에 자료가 정렬되어 있지 않거나

그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용하다.

 

예시1. 주어진 배열에서 특정 값 찾기

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

int main(void){
    int numbers[] = {4, 8, 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;
}
// ? Not found

numbers의 첫 값이 4부터 마지막 값인 42까지 전부 순회한 뒤

50을 발견하지 못하고 "Not found"를 출력하는 예시이다.

 

 

예시2. 전화번호부에서 특정 이름의 전화번호 찾기

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

int main(void){
    string names[] = {"DONG", "CHUN", "SDA"};
    string numbers[] = {"10-111-2222", "10-222-3333", "10-333-4444"};
    for(int i=0; i<3; i++){
        if(strcmp(names[i], "CHUN") == 0){
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}
// ? Found 10-222-333

이름이 담긴 names 배열에서 CHUN을 검색해 인덱스를 저장하고(i)

전화번호가 담긴 numbers 배열 중 해당 인덱스를 가진 값을 반환하는 예시이다.

 

 

구조체(struct)

위 예시가 성립하기 위해서는 names와 numbers가 서로 같은 인덱스를 가져야 하는데

이 한계를 해결하기 위해

구조체를 정의해 이름과 전화번호를 함께 묶어주는 아래와 같은 방법도 있다.

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

typedef struct{
    string name;
    string number;
}
person;

int main(void){
    person people[3];

    people[0].name = "DONG";
    people[0].number = "10-111-2222";
    people[1].name = "CHUN";
    people[1].number = "10-222-3333";
    people[2].name = "SDA";
    people[2].number = "10-333-4444";

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

// ? Found 10-222-333

이 구조체는 전화번호부의 예시 외에도

가계부(교통비 40,000, 식비 50,000), 환자 진료 기록(김개발 목디스크, 박선생 성대결절) 등

각 고유한 이름을 갖고, 고정 값이 있는 자료들을 활용하기에 적절하다.

 

 

 

---

복습 퀴즈

Q1. 알고리즘의 성능 및 시간 복잡도를 표현하는 표기법 중 하나로, 최악의 경우일때(상한)를 나타내는 것은?

답: O(n)

 

 

Q2. name과 number 두개의 멤버를 갖는 person이라는 새로운 자료형을 구조체로 정의하고자 한다.

아래 코드의 괄호 안에 들어갈 코드로 알맞은 것은?

(             ) {
	string name;
	string number;
}
person;

답: typedef struct

 

 

Q3. 전화번호부에서 '홍길동'를 찾는 작업을 선형 검색으로 수행하게 될 경우 Big-O는?

답: O(n)

처음부터 끝까지 한 번씩 방문해서 찾기 때문에 n이다.