모두를 위한 컴퓨터 과학(CS50) - 검색 알고리즘

사진이 겁나 크네요..

 

위와 같은 서랍이 있다고 치자.

우리는 서랍이 모두 열려 있다고 가정할 때

해당 서랍에 어떤 내용물이 들어있는지 한눈에 파악할 수 있다.

 

하지만 이것은 인간의 얘기..!

 

컴퓨터는 인간과 달리 전체를 파악하는 능력이 없다.

 

그렇다면 컴퓨터는 저 서랍에 어떻게 접근하는 것일까?

 

 

선형 검색(Linear Search)

떠올릴 수 있는 가장 쉬운 방법이 선형 검색일 것이다.

쉽게 말해 서랍의 맨 윗칸부터, 즉 첫 번째 인덱스부터

마지막 칸(마지막 인덱스)까지 열어보는 것이다.

 

이를 깔끔하게 정리해서 표현하자면

배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 검색하는 것을 말한다.

 

파이썬으로 선형 검색의 간단한 예제를 만들어 보자

 

 

우선 a라는 이름의 리스트를 만들었다.

즉, 위에서 말한 서랍을 만들고 각 서랍에 1, 2, 3, 4, 5, 6, 7 값을 넣어줬다.

 

이제 숫자 7을 선형 검색으로 찾아보자

첫 번째 인덱스인 0부터 마지막 인덱스인 6까지 순서대로 탐색하도록

for문을 이용해 반복을 돌렸다.

 

인덱스 접근 순서를 확인하기 위해 인덱스에 따른,

쉽게 말해 서랍에 들어 있는 숫자 값을 출력하기로 했다.

 

그리고 마지막으로 숫자 7을 찾으면 찾은 7의 인덱스 값을 출력하기로 했다.

 

결과는 다음과 같다.

 

해당 예제는 서랍에 담긴 값을 순서대로 출력하는 것을 보여준다.

 

그렇다면 이 방법이 가장 효율적인 방법일까?

정답은 '그럴 수도 있고 아닐 수도 있고'이다.

 

우선 해당 서랍을 보면 임의의 값이 아니라

숫자가 정렬되어 들어가 있는 것 같이 보인다.

 

그렇다면 이 수가 위의 리스트처럼 정렬되어 있는 모습이 아니라면 어떨까?

예를 들어 1 다음에 30이오고 30 다음에 7이 들어 있는 리스트라면 어떨까?

 

그렇다 정렬이 되어 있지 않다고 가정한다면

하나씩 순차대로 탐색하는 것이 가장 효율적인 방법이다.

어떤 서랍에 7이 들어 있는지 알 수 있는 방법이 없다면

하나씩 열어보는 것이 가장 효율적인 방법이다.

 

 

 

 

이진 검색

그렇다면 이번엔 서랍이 정렬되어 있다고 생각해보자.

그렇다면 선형 검색을 하는 것이 효율적일까?

 

유명한 미니 게임 중에 1부터 50까지의 숫자 중

생각한 숫자를 맞추는 게임이 있다.

 

문제를 낸 사람은 문제를 맞히는 사람이 말하는 숫자가

본인의 숫자보다 작을 경우 down을

본인의 숫자보다 클 경우 up을

맞을 경우 정답을 말하는 3가지 경우가 존재한다.

 

다른 조건이 주어지지 않을 때

문제를 맞추는맞히는 사람이 가장 빨리 정답을 맞추는 방법은

절반의 숫자를 부르는 방법이다.

 

예를 들어 첫 번째 질문은 25로 한다.

출제자가 up을 외친 경우

범위는 26부터 50으로 한정된다.

 

그렇다면 다음 질문은 38로 한다.

출제자가 down을 외친 경우

범위는 26부터 38이 된다.

 

이렇게 정확히 반씩 범위를 좁혀 나가는 것이

가장 유리한 방식이고

이 방식이 이진 검색이다.

 

하지만 이 방식은 예시와 같이 숫자가 정렬되어 있는 경우에만

의의를 갖는다는 것에 주의해야 한다.

 

 

---

출처 : 네이버 edwith, 부스트코스 [모두를 위한 컴퓨터 과학]