알고리즘은 왜 배워야하나?
개발자가 어떤 알고리즘을 선택하는지에 따라 해당 작업을 수행하는 스피드가 많이 차이납니다.
그렇기 때문에 어떤 자료구조를 언제 선택하는지 그리고 무슨 알고리즘을 언제 선택해야하는지 알아야합니다.
알맞는 자료구조와 알고리즘을 선택하게 되면 코드의 수행 속도가 확연히 차이나게 됩니다.
알고리즘은 우리가 어떠한 작업을 수행하기 위해 따라야하는 절차/단계들 입니다.
Linear Search(선형검색) 알고리즘
[5, 23, 6, 12, 78, 5, 88, 56, 33, 54]만약 위의 배열에서 5을 찾는다고 했을 때, 순서대로 목표값을 찾는 것을 말합니다.
👍 장점
선형검색은 어느 배열에서든지 사용이 가능합니다.
👎 단점
- 목표값이 배열의 제일 마지막에 있거나 배열에 아예 없는 경우
- 배열이 커지면 커질수록 선형을 검색하는 시간이 길어짐
Binary Search(이진검색) 알고리즘
이진검색 알고리즘은 Linear Search 알고리즘보다 발전된 방법입니다.
긴 배열을 검색할 때 유용하게 쓸 수 있습니다.
대신, 모든 배열에 쓸 수 없고, Sorted Array(정렬된 배열)에서만 사용이 가능합니다.
*Sorted Array란
배열들이 순서대로 정렬된 경우
🚨정렬된 배열에 아이템을 추가하는 것은 정렬되지 않은 경우보다 시간이 오래 걸립니다.
이유인즉, 첫 째, 정렬된 배열에 아이템을 추가하기 위해서는 아이템보다 큰 값을 찾아야합니다.
둘 째, index 0부터 하나씩 비교하면서 아이템보다 큰 값을 찾습니다.
셋 째, 큰 값을 찾고나면 해당 아이템 오른쪽에 있는 모든 요소들을 옮겨줍니다.
넷 째, 그리고 생겨난 빈자리 즉, 큰 값의 왼쪽에 아이템을 추가해줍니다.
이러한 긴 과정 때문에 시간이 오래 걸립니다.
하지만, 정렬된 배열에서 검색하는 것이 정렬되지 않은 경우보다 시간이 적게 걸립니다.
이진검색 수행과정
이진검색은 0 그리고 1을 의미하지 않고, 하나를 반으로 가르는 것을 의미합니다.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]1부터 10까지 들어있는 배열이 있고, 그 중 9을 찾아야하는 상황이라고 가정했을 때,
중간(5)에서 우리 목표 숫자보다 큰지 작은지 확인을 합니다.
9와 5를 비교했을 때 작으니 오른쪽 아이템을 다시 서칭합니다.
그리고 다시 배열의 중간 숫자인 8과 9를 비교해서 작으니까 오른쪽으로 이동합니다.
이제 남은 아이템은 2개 밖에 없기 때문에 목표값인 9를 찾게 됩니다.
선형검색 알고리즘을 이용했다면 9번의 과정이 필요했겠지만
이진검색 알고리즘을 이용해 3번의 과정 만으로 목표값을 찾을 수 있었습니다.
이진검색은 배열이 배로 늘어나더라도 1개의 단계만 추가됩니다.
