[CS50] 검색 알고리즘

지금까지는 메모리의 구조, 자료형 같은 기본적인 개념을 공부했지만 이번 포스팅부턴 지금껏 배운 내용을 활용해서 검색, 정렬 등과 같은 문제를 풀어내는 알고리즘에 대해 공부하고 정리해보도록 하겠습니다.

 

검색 알고리즘은 선형 검색, 이진 검색, 해시 검색 이렇게 3가지가 있는데 이중 선형 검색과 이진 검색에 대해 공부해보도록 하겠습니다.

 

선형검색

만약 10 23 6 1 2 50 이렇게 정렬이 되지 않은 6개의 숫자가 보이지 않게 있을 때 50을 찾아내는 방법엔 어떤 것이 있을까요?

□□□□□□ 이렇게 박스 안에 들어있다고 가정한다면 당연히 정렬도 되어있지 않은 수니까 맨 처음 □부터 끝까지 하나하나 열어서 살펴보는 방법밖엔 없습니다. 만약 여기서 50이 가장 뒤에 있다면 모든 박스를 다 열어봐야 할 겁니다.

이처럼 선형 검색은 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사합니다.

이것을 의사 코드로 나타내 본다면

for i from 0 to n-1

	if i`th element is 50 //i 번째의 값이 50일때
    return true
    
return false

이렇게 나올 겁니다.

 

이진검색

그렇다면 1 2 6 10 23 50 83 93 99 이렇게 정렬이 되어있다면 어떨까요??

마찬가지로 □□□□□□□□□ 이렇게 9개의 박스가 있을 때 여기서 50을 찾는 가장 빠른 방법은 가운데 박스를 먼저 열어보고 그 숫자가 50보다 낮으면 뒤의 박스를 높으면 앞의 박스를 열어 점점 범위를 좁혀나가는 방법이 있습니다.

이처럼 이진 검색은 만약 배열이 정렬되어있다면 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장되어있는) 인덱스 또는 큰(큰 값이 저장되어있는) 인덱스로 이동을 반복하여 검사합니다.

이것을 의사 코드로 나타내 본다면

if no items
	return false
    
if middle item is 50
	return true

else if 50 < middle item
	serch left half

else if 50 > middle item
	serch right half

로 나타낼 수 있습니다.

 

---

출처

본 내용은 CS50의 2019년 강의를 듣고 작성했습니다. (개념이 어느 정도 정리되면 최신강의도 다시 듣고 수정할 내용 있으면 수정하겠습니다.)

 

강의 자료는 EdX에서 무료로 사용할 수 있고 boostcourse에서 한글 강의로도 들을 수 있습니다.