탐색 알고리즘 - 1. 선형 탐색 / 2. 이진 탐색 알고리즘

이글은 코드잇의 알고리즘 강의와 오픈소스들을 참고하여 정리한 글입니다^^

알고리즘 공부 방법

하나의 문제를 해결하는 방법에는 여러가지가 있다. 그 방법들을 찾아서 가장 좋은 방법을 찾는 것이 알고리즘 공부 방법이다.

예를 들어, 책장에서 원하는 책을 찾는 방법 2가지 방법을 확인해보자.

1. 왼쪽부터 하나씩 확인하다가 찾기
   

2. 책이 알파벳순으로 정렬되어 있다는 것을 활용하여,
   (1) 전체 중 중간을 선택한 뒤, 원하는 책이 앞인지 / 뒤인지 확인하기
   

   (2) 남은 책들 중에 중간지점을 선택한 뒤, 확인하기
   
   (3) 이렇게 반씩 줄이는 것을 반복하다보면 원하는 책을 찾을 수 있다.
   

탐색문제

위에서 살펴보면 문제는 탐색문제이다.
탐색이란? 저장된 정보들 중에 원하는 값을 찾는 것이다. ex> 파이썬 숫자 리스트 중 특정값 찾기

탐색문제 해결방법 2가지

1. 선형 탐색 알고리즘(Linear search algorithm) : 순서대로 하나하나씩 찾기
2. 이진 탐색 알고리즘(Binary search algorithm) : 반씩 제외시키면서 찾기

1. 선형 탐색 알고리즘 : 순서대로 하나하나씩 찾기

   • 왼쪽부터 하나하나씩 원하는 값을 찾아본다.
     

   • 원하는 값 발견시, 더이상 안보고 끝낸다.
     

2. 이진 탐색 알고리즘 : 반씩 제외하면서 찾기

   • 중간지점(중간값)을 먼저 선택한 뒤, 왼쪽 or 오른쪽만 남긴다.
     

   • 남은값들 중에 중간값을 선택(여기서는 그냥 왼쪽것을 선택)하고, 왼쪽or오른쪽 남기기
     

   • 반복해서 찾아가기
     
     

2가지 탐색문제 해결방법 중 어느 것이 더 효율적일까??

탐색 알고리즘 2개 비교

16개의 원소를 가지고 있는 리스트가 있다고 가정하고, 얼마나 걸리는지 한번 생각해보자.

선형탐색의 경우, 언제 가장 빨리 마치고/ 언제 가장 늦게 마칠 까?

• 정답이 리스트 첫 원소인 경우 -> 1번걸림
  

• 정답이 마지막 원소이거나 없는 경우 -> 16번걸림
  

이진탐색의 경우, 가장 빨리 되는 경우는

• 정답이 가운데( 0 + 15 // 2) 있는 경우 -> 1번
  
• 정답이 없는 경우 = ex> 0을 찾는 경우 -> 4번
  
  
  
  

이진 탐색의 경우 최악의 경우시 4번만 봐도 되지만, 선형 탐색은 16번 다 봐야한다.

최악의 경우를 일반화 해보면, n개의 원소 리스트는

• 선형탐색 -> n번
• 이진탐색 -> 2^m = n의 m번 걸린다.
• 리스트의 길이가 길어지더라도, 이진 탐색은 걸리는 시간이 아주 천천히 늘어난다.

언제 선형탐색을 쓸까???

이진 탐색의 전제조건은 정렬된 리스트-이진탐색이다.
만약, 리스트가 정렬되지 않은 상태라면 정렬x리스트-선형탐색을 쓸 수 밖에 없다.