알고리즘 / 선형 검색

학습 강의

www.boostcourse.org/cs112/lecture/119019

www.boostcourse.org/cs112/lecture/119021

 

 

메모리와 자료구조, 그리고 배열

 

컴퓨터 안에는 메모리(RAM)가 있다. 메모리를 바이트 단위의 격자 배열로 취급하면, 문제를 풀어내기 위해 왼쪽에서 오른쪽, 위에서 아래로 나아가는 자료 구조를 이용할 수 있다. 

 

배열은 한 자료형의 여러 값들이 메모리 상에 모여 있는 구조로, 실생활에서 살펴보면 사물함 락커에 비유할 수 있다. 컴퓨터는 배열의 값들에 접근할 때 배열의 인덱스 하나하나를 접근하는데, 마치 사물함 락커를 하나 하나 열어보는 것과 비슷하다. 

 

어떤 값이 배열 어느 곳에 있는 지 찾아보기 위해서, 배열 정렬의 여부에 따라 선형 검색과 이진 검색의 방법을 사용할 수 있다. 이번 포스팅에서는 선형 검색에 대해 다뤄볼 예정이다.

 

 

선형 검색의 의미

 

배열의 인덱스를 처음부터 끝까지 차례대로 하나씩 방문하여 그 값이 속하는 지 검사한다. 예를 들어 사물함이 1~10번까지 있다면 1번, 2번, ... , 10번 까지 하나하나 열어서 원하는 값이 안에 들어있는 지 보는 것이다. 

 

정리하자면, 선형검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색한다.

 

숫자 50을 찾는 의사 코드는 아래와 같다. 

For i from 0 to n-1

	If i'th element is 50
    
    	Return true

Return false
        

 

 

선형 검색의 효율성

 

선형 탐색 알고리즘은 정확하지만 효율적인 방법은 아니다. 만약에 리스트의 길이가 n이라고 하자. 운이 좋다면 첫 번째 시도에서 원하는 값을 찾을 수도 있겠지만, 값이 맨 마지막에 있거나 리스트의 없는 경우에는 리스트의 모든 원소를 확인하기 위해 n번만큼 실행되기 떄문이다. 

 

따라서 선형 탐색은 자료가 정렬되어 있지 않거나, 사전 정보가 하나도 주어지지 않을 경우 하나씩 찾아야 하는 경우에 유용하다.

 

 

데이터가 미리 정렬 되어 있다면, 선형 검색보다 더 효율적인 다른 알고리즘을 사용해서 원하는 자료를 찾는 데 걸리는 시간을 단축 시킬 수 있다. 데이터 정렬의 중요성이 부각되는 측면이다.

 

 

선형 검색의 Big O와 Big Ω

• Big O : O(n)
• Big Ω : Ω(1)