선형 검색

CS50 2019 강의를 듣고 내용을 정리한 시리즈 글입니다.

---

학습목표

주어진 배열 또는 구조체에서 선형 검색을 할 수 있습니다.

핵심 단어

• 선형 검색
• 구조체

강의 내용

1. 선형 검색의 효율성

선형 검색 알고리즘은 정확하지만 효율적이지 못한 방법이다.
리스트의 길이가 n이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행된다.

100만 개의 원소가 있는 리스트라고 가정해본다면 효율성이 매우 떨어짐을 알 수 있다.

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

그리고 이것은 검색 이전에 왜 정렬을 해야 하는지 알 수있는 이유가 된다.

물론 정렬은 시간이 오래 걸리고 공간을 더 차지하지만 여러 번 리스트를 검색해야 하거나 매우 큰 리스트를 검색해야 할 경우 시간을 단축할 수 있게 된다.

주어진 배열에서 특정 값을 찾기 위해서 선형 검색을 사용한다면, 아래와 같은 코드를 작성할 수 있다.

def linear_search(value, array):
    for i in array:
        if i == value:
            return True
    return False

2. 구조체

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

예를들어 전화번호부에서 이름을 찾아 전화번호를 출력하는 프로그램은 names 배열과 numbers 배열을 따로 정의하고 names 배열에서 검색해 해당하는 인덱스의 numbers 배열 값을 출력하는 형태로 만들 수 있다.

하지만 이 경우에는 names 배열과 numbers 배열이 서로 같은 인덱스를 가져야 한다는 문제가 있다.

더 좋은 방법은 새로운 자료형으로 구조체를 정의해서 이름과 번호를 묶어주는 것이다.

Python에서 사용하려면 dataclass를 사용하면 된다. (Python 3.7 이상)

from dataclasses import dataclass

@dataclass
class PhoneBook:
    name:str = None
    number:str = None

phone_book = PhoneBook()

phone_book.name   = "kim"
phone_book.number = "010-..."

위처럼 구조체를 사용한다면 더욱 확장성 있는 프로그램을 만들 수 있다.

생각해보기

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

학교나 회사 등의 인사관리 데이터