검색 알고리즘

#이진검색 #선형 검색 #노마드 코더

본 포스팅은 노마드코더 영상을 정리하며 학습하기 위한 목적을 가지고 있습니다.

---

알고리즘이란?

절차/ 스텝이다 - 생활속의 레시피라고 생각하자.

어떤 알고리즘을 선택하는지에 따라 해당 작업을 수행하는 속도 차이가 난다.

어떤 자료구조를 언제 선택하는지 중요한 것 처럼 알고리즘도 같다.

알고리즘 또한 얼마나 많은 절차와 스텝이 필요한 시간복잡도가 있다. - 당연히 적은 절차가 더 훌륭한 알고리즘

 

검색 알고리즘

오늘은 이진검색 알고리즘 vs 선형검색 알고리즘을 알아보자.

모두 검색 알고리즘이며, 다른 종류로는 정렬 알고리즘도 있다.

 

선형 검색 알고리즘

자연스러운 검색으로 1번 부터 차례로 검색해 목표값을 찾는다. 

배열의 순서대로 찾기 때문에 최악의 경우는 맨 마지막 배열 혹은 없는 경우 커지면 커질 수록 시간이 길어진다

선형 검색의 시간복잡도는 다음 그래프와 같다.

배열이 클수록 시간이 많이 소요

이진검색 알고리즘

정렬된 배열에서만 가능하며 특정 자료구조에서만 사용가능하다.

그전에 순서대로 정렬된 배열의 경우 값을 추가하는 시간은 오래걸린다.

대신!!! 정렬하는 시간에 오래 투자하는 만큼 검색하는 순간 보람을 느낄 것이다.

 

이진검색은 반으로 쪼개는 것을 뜻한다

첫 검색을 중간에서 시작하며 중간숫자와 목표숫자의 크기를 비교해 목표숫자가 작으면 왼쪽 크면 오른쪽을 검색하기 시작한다.

Input이 두배가 되도 검색 스탭은 은 두배가 되지 않는다.

예를 들어, 배열의 크기가 10일 경우 3번이면 검색이 끝나지만 20일 경우 6번이 아닌 4번이면 검색이 종료된다.

따라서 거대한 배열을 다룰때 효과적이다. (하지만 배열을 정렬해야 한다..)

그래서 알고리즘이 중요한 것이다.

 

결론

검색하는 시간과 배열을 정렬하는 시간의 상충관계(트레이드오프)를 잘 생각해야한다. 

 

 

출처: 노마드코더 니콜라쓰 쌤 https://www.youtube.com/watch?v=WjIlVlmmNqs&ab_channel=%EB%85%B8%EB%A7%88%EB%93%9C%EC%BD%94%EB%8D%94NomadCoders

노마드코더 강의를 입문해보자. 많은 도움이 된다.

오늘도 감사합니다.