배열의 요소가 많지 않다면 순차 탐색이 어느 정도 충분한 탐색 방식일 수 있습니다. 그렇지만 요소가 적지 않은 배열이라면 정렬되지 않은 상태에서 탐색을 하는 것은 비효율적입니다. 따라서 정렬을 먼저 한 다음 탐색을 하는 것이 효율적입니다. 그 중 이진 탐색을 먼저 살펴보겠습니다. 이진 탐색이란? 이진 탐색은 배열의 중앙에 있는 값을 선택해 찾고자 하는 값과 비교를 통해 탐색 범위를 반으로 줄이는 탐색 기법입니다. 데이터의 양이 많을 때 사용하면 탐색 횟수를 획기적으로 줄일 수 있습니다. 이진 탐색 구현 이진 탐색의 핵심은 반으로 나누기입니다. 과정은 아래와 같습니다. 리스트의 가운데 있는 요소를 선택 선택한 요소가 찾으려고 하는 값보다 크면 왼쪽 리스트 탐색 작으면 오른쪽 리스트 탐색 찾으면 요소의 인덱..

탐색이란? 자료구조에서 탐색이란 여러 개의 데이터 중 원하는 데이터를 찾는 작업을 말합니다. 탐색은 크게 두 가지로 나눌 수 있습니다. 정렬되지 않은 상태에서 탐색 정렬된 상태에서 탐색 이번 포스팅에서는 정렬되지 않은 상태에서의 탐색을 살펴보겠습니다. 순차 탐색 정렬되지 않은 상태에서 탐색을 하려면 어떻게 해야 할까요? 리스트의 첫 번째 요소부터 하나씩 순차적으로 요소를 방문해서 비교를 하면 됩니다. int seq_search(int key, int low, int high) { for(int i = low; i

기수 정렬이란? 처음 이 정렬을 들으면 기수라는 단어가 생소할 겁니다. 사전에서 찾아보면 다음과 같습니다. 십진수에서는 0부터 9까지의 숫자를 각 자릿수에 넣을 수 있습니다. 우리는 이 리스트를 오름차순으로 정렬하고 싶습니다. 그렇다면 각 요소마다 가장 낮은 자릿수에서부터 한 자리씩 정렬하면 어떨까요? 사실 이 한 줄이 바로 기수 정렬의 아이디어입니다. 이 때 가장 낮은 자릿수를 LSD(Least Significant Digit)라 하고, 가장 높은 자릿수를 MSD(Most Significant Digit)라 합니다. 기수 정렬은 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬하는 방식입니다. 왜 그런지 구현 과정을 보면서 확인해봅시다. 기수 정렬 구현 기수 정렬의 핵심은 각 자릿수끼..

힙 정렬이란? 힙 정렬은 힙 트리를 이용해 정렬을 하는 것을 말합니다. 사실 최대 힙과 최소 힙은 각각 루트에 최댓값과 최솟값이 이미 있습니다. 루트를 계속 꺼내면 힙의 정의에 의해 그 다음 큰 값(혹은 작은 값)이 계속 루트에 상주하게 됩니다. 따라서 트리에 노드가 없을 때까지 힙 트리의 삭제 함수를 계속 호출만 하면 됩니다. 힙 정렬에는 최대 힙과 최소 힙 중 어느 것을 사용할까요? 눈치 채셨겠지만, 상관없습니다. 내림차순으로 정렬하려면 최대 힙을 사용하면 되고, 오름차순으로 정렬하려면 최소 힙을 사용하면 됩니다. 예시로 최대 힙을 사용한 힙 정렬을 들어보겠습니다. 힙 트리에 관한 자세한 정보는 아래의 힙 (Heap) 포스팅을 참고하시기 바랍니다. [자료구조] 힙 (Heap) 힙 (Heap) 힙은 여..

퀵 정렬이란? 퀵 정렬은 합병 정렬과 동일하게 분할 정복 알고리즘을 사용합니다. 차이점이 존재한다면, 퀵 정렬은 리스트를 비균등하게 분할합니다. 작동 방식 작동 방식에 앞서, 퀵 정렬에는 피벗(pivot)이라는 요소가 존재합니다. 피벗이란, 뜻 그대로 중심점이라는 뜻입니다. 퀵 정렬은 중심축을 기준으로 왼쪽 리스트와 오른쪽 리스트로 나뉩니다. 따라서 피벗이라는 요소가 존재하고 반드시 알고 있어야 합니다. 피벗을 설정할 때는 리스트의 첫 번째 요소로 하던 가운데 요소로 하던 상관 없습니다. 여기에서는 첫 번째 요소로 하겠다는 가정으로 진행하겠습니다. 리스트 안에 있는 한 요소를 피벗으로 선택하고, 피벗을 기준으로 작은 요소들은 왼쪽으로 옮기고 큰 요소들은 오른쪽으로 옮깁니다. 다 했다면 피벗을 제외한 왼쪽..

합병 정렬이란? 합병 정렬은 리스트를 분할하고 결합하는 과정 속에서 정렬을 수행하고자 하는 방법입니다. 분할-정복에 따른 수행 방식입니다. 앞서 정렬을 할 때는 기존의 리스트를 그대로 이용해서 수행했습니다. 숫자가 적을 때는 시간이 오래 걸리지 않지만, 커지면 시간 복잡도에 따라 수행 시간이 어마하게 늘어남을 알 수 있습니다. 합병 정렬은 기존의 리스트를 쪼개서 더 작은 리스트를 만듭니다(분할). 쪼갤 수 있을 때까지 쪼갭니다(정복) 문제를 충분히 작게 만들었다면, 정렬을 합니다. 이 때 정렬은 숫자 단 두개만을 비교합니다. 정렬을 했다면, 다시 원래 리스트의 크기로 돌아갈 있도록 합쳐줍니다(결합). 합쳐주는 과정에서도 순서대로 숫자가 들어가야 합니다. 따라서 분리되어 있는 리스트의 맨 앞에서 하나씩 꺼..

셸 정렬이란? 이전에 포스팅 했던 삽입 정렬은 시간 복잡도가 $O(n^2)$로 정렬 알고리즘 중에서는 느린 축에 속하는 정렬 방식이었습니다. 하지만 삽입 정렬은 어느 정도 배열이 정렬이 된 상태라면 시간 복잡도를 줄일 수 있습니다. 이에 착안해 도널드 셸(Donald L.Shell)이라는 창시자가 본인의 이름을 따 셸 정렬이라고 부르게 됩니다. 쉘 정렬은 정렬해야 할 리스트를 일정한 간격에 따라 나눕니다. 그렇게 여러 개로 나누어진 부분 리스트를 만들어 각 부분 리스트를 삽입 정렬을 이용해 정렬하는 방식입니다. 셸 정렬 구현 셸 정렬의 핵심은 간격입니다. 셸 정렬이 구현되어 있는 함수에서는 처음 간격이 (배열 혹은 리스트 크기 / 2)로 시작했다가 1이 될 때까지 정렬을 반복합니다. 간격이 줄어들면서 점..