- 어떤 자료구조를 언제 선택하는지 중요한 것처럼 무슨 알고리즘을 언제 선택하는지 배워야 함
- 완벽한 자료구조 및 알고리즘 조합을 찾아내면 코드의 스피드 자체가 달라질 것!
1. Algorithm
- List of Steps : 어떠한 작업을 위해 따라야 하는 절차/스텝들
- Time Complexity(시간 복잡도)가 존재 : 얼마나 많은 절차/스텝이 필요한가에 대한 것
2. Linear Search(선형검색 알고리즘)
- 검색을 하기 위한 '자연스러운' 방법
- 처음부터 끝까지, 순서대로, 차근차근
- 어느 배열에서도 사용 가능
- 배열 제일 마지막에 찾는 요소가 있거나, 배열에 아예 없는 경우 가장 최악의 방법
- 배열이 커지면 커질수록 선형검색을 하는 시간이 길어짐
3. Binary Search(이진검색 알고리즘)
- Linear Search보다 발전된 방법이지만 모든 배열에 사용할 수는 없음
- Sorted Array(정렬된 배열)에서만 사용 가능
Sorted Array?
- 배열이 순서대로 정렬된 경우를 의미
- ex) 1부터 10까지 작은 수에서 큰 수 순서대로 정렬
- 정렬된 배열에 item을 추가하는 것은 정렬이 안된 경우보다 시간이 더 걸림
정렬된 배열에서 검색을 하는 것은 매우매우 빠름!
-
Binary : '반으로 쪼개는 것'을 의미
-
선형검색과 달리 이진검색에서는 index 0부터(처음부터) 검색하지 않음
-
이진검색은 정렬된 배열의 정중앙에서 시작
-
정 가운데에 있는 숫자가 목표 숫자보다 큰지, 작은지를 확인
- 만약 목표보다 숫자가 크다면 item의 왼쪽으로 감
- 목표보다 숫자가 작다면 item의 오른쪽으로 감
-
찾고자 하는 값이 배열의 중간 값보다 큰지, 작은지를 확인하며 계속 쪼개면서 검색
-
input이 2배가 되더라도 필요한 step은 2배가 되지 않고 +1이 될 뿐!
- 이진검색은 매 스텝마다 절반의 item을 없애기 때문!- 큰 사이즈의 데이터 처리 시 매우 효율적
4. 정리
- Binary Search(이진 검색)
- 거대한 배열을 다룰 때 효율적
- 하지만 배열 정렬이 우선
- 검색을 많이 해야하는 상황이면 정렬을 우선하고 검색하는 이진검색이 효율적
- 유의사항 : 배열 정렬을 하면 item 추가 시 시간 소요
출처 : 검색 알고리즘 기초개념 설명 by 노마드코더
https://www.youtube.com/watch?v=WjIlVlmmNqs
