알고리즘 | 검색 알고리즘

✔ 학습목표

주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있다.

 

배열

본 글에서부터는 이제껏 배운 내용(메모리의 구조, 자료형, 배열 등)을 바탕으로 검색이나 정렬과 같은 문제풀이 알고리즘을 학습할 것이다. 이에 앞서 배열 속에서 특정 값을 찾는 방법을 이해해야 한다.

 

배열은 한 자료형의 여러 값들이 메모리상에 모여있는 구조다. 컴퓨터는 배열을 볼 때 인덱스 하나하나에 접근하게 된다. 이때 어떤 값이 배열에 들어 있는지 확인하는 데는 정렬 여부에 따라 두 가지 방법이 있다.

 

선형 검색

선형 검색은 순서대로 하나씩 보는 것이다. 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키며 원하는 값이 들어있는지 확인한다. 50이라는 숫자를 찾는 의사 코드로 예를 들어보자.

 

For i from 0 to n-1
	if i'th element is 50
    	Return true
Return false

 

이진 검색

이진 검색은 데이터가 정렬되어 있을 때 배열 중간 인덱스에서부터 시작해 값을 비교하며 원하는 값을 찾는다. 이 과정에서 그보다 작거나 큰 인덱스로 이동을 반복한다. 앞과 같은 상황의 이진 검색 의사 코드를 보자.

 

If no items

    Return false

If middle item is 50

    Return true

Else if 50 < middle item

    Search left half

Else if 50 > middle item

    Search right half

 

이처럼 배열 속에서 특정 값을 찾을 때에는 선형 검색과 이진 검색, 두 가지 방법을 사용할 수 있다.

 

---

 

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 본 강좌 내 실습에서는 CS50 Sandbox를 사용합니다.

 

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