알고리즘 기초 (선형탐색)

Harvard CS50 x Edwith 강의를 학습하며 정리한 내용입니다.

 

 

 

 

선형 탐색

 

 

선형탐색

• 찾고자 하는 자료가 발견될때까지 처음부터 끝까지 차례대로 탐색하는 방법

선형탐색의 효율성과 비효율성

선형탐색은 처음부터 끝까지 차례대로 탐색함으로써 정확도는 높지만 효율적이지 못한 방법입니다. 만약 찾고자 하는 자료의 길이가 n이라고 가정한다면 최악의 경우 n번만큼 확인을 해야합니다. 이보다 더 최악은 자료의 길이 안에 찾는 자료가 없는 경우이며 이 길이가 작은 단위가 아닌 100만, 1000만의 경우 속도나 효율성 측면에서 좋지 못한 선택이 되기도 합니다. 무조건 나쁘고 효율적이지 못할 것 같지만 자료가 정렬되어 있지 않거나 어떠한 기준이나 정보 없이 하나씩 찾아야 하는 경우엔 선형탐색을 사용하는 것이 효율적이고 유용합니다. 이러한 설명을 통해 알 수 있는점은 정렬의 필요성입니다. 정렬은 오래걸리고 공간을 차지하기도 하지만 이러한 과정을 거쳐 여러번 검색을 하거나 아주 긴 길이의 리스트를 검색해야 할 경우 시간을 단축시킬 수 있는 장점을 가지고 있습니다.

 

 

Ex) 

자신의 핸드폰 전화번호부에 저장된 '홍길동' 을 찾는 동안 이름을 하나씩 확인하는 것을 의미합니다. 하지만 검색이 없다는 가정하에 우린 보통 순서대로 하나씩 확인하지 않고 가나다순 혹은 알파벳순으로 정렬된 것을 확인하여 'ㅎ'로  바로 가서  '홍길동'을 찾을 수 있습니다. 이러한 정렬 과정을 통해 탐색을 더 효과적으로 만들어주는 알고리즘도 있지만 정렬이 되어 있지 않은 경우는 어쩔 수 없이 선형탐색을 사용해야 합니다.