이분 탐색(Binary Search)
데이터가 담긴 리스트를 탐색하는 방법은 크게 순차 탐색(Linear Search)과 이분 탐색(Binary Search)이 존재한다. 예를 들어 { 8, 3, 1, 5, 4, 7, 9, 2, 6, 10}, 10개의 데이터가 담긴 리스트가 있다고 하자. 이 리스트에서 9의 위치를 찾기 위해서는 어떻게 해야 할까? 위 리스트처럼 정렬되지 않은 리스트에서 데이터를 탐색하기 위해서는 어쩔 수 없이 처음부터 끝까지 순차적으로 탐색을 진행하여 9의 위치를 찾는 방법밖에 없을 것이다. 그렇다면 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}처럼 정렬된 리스트가 있다고 생각해 보자. 이 리스트에서도 9의 위치를 찾기 위해서는 어떻게 해야 할까? 단순하게는 앞서 언급한 방법처럼 처음부터 순차적으로 9의 인덱스..
2021. 7. 2.
선택 정렬(Selection Sort)
정렬 알고리즘은 알고리즘에서 가장 먼저 배우는 알고리즘이다. 정렬 알고리즘에는 선택 정렬, 삽입 정렬, 버블 정렬, 합병 정렬, 퀵 정렬, 힙 정렬 등 다양한 정렬 알고리즘이 존재한다. 선택, 삽입, 버블 정렬은 구현이 상대적으로 쉽지만 성능이 좋지 않은 반면, 합병, 퀵, 힙 정렬은 구현이 상대적으로 복잡하지만 성능이 훨씬 좋기 때문에 후자의 정렬들을 사용하는 것을 나는 선호하는 편이다. 하지만 성능의 차이를 알기 위해선 모든 정렬 알고리즘의 원리를 알아야한다. 이번에는 선택 정렬(Seletcion Sort)을 다뤄보겠다. 선택 정렬은 주어진 리스트를 돌면서 가장 작은(큰) 원소를 찾아 정렬된 원소를 제외한 제일 앞의 원소와 교환해주면 되기 때문에 가장 이해하기가 쉽고 단순한 정렬 방법이다. 선택 정렬..
2021. 7. 1.
