Algorithm/C. Sortings & Search (14) 썸네일형 리스트형 32. Quick Sort 병합 정렬은 $\Theta(n\text{ lg }n)$의 시간복잡도를 갖지만 메모리 사용량이 너무 많다는 문제가 있다. 이러한 문제가 발생하지 않으면서 병합 정렬과 같은 평균 시간복잡도를 갖는 정렬 방법으로 퀵 정렬(Quick Sort)이 있다. 퀵 정렬은 한 원소의 위치를 고정하고 앞뒤 원소들을 같은 방법으로 정렬하는 분할 정복 기법의 일종이며, 평균적인 상황에서 최고의 성능을 보이지만 최악의 시간복잡도는 $\text{O}(n^2)$라는 문제점이 존재하며, 동일한 값이 여러 개 존재하는 경우 정렬 과정에서 상대적인 순서가 바뀔 수 있다. 퀵 정렬의 과정을 요약하면 다음과 같다. 1. 피벗을 고른다. 2. 피벗보다 뒤에 나와야 하는 첫 번째 원소 $a_i$를 찾는다. 3. 피벗보다 앞에 나와야 하는 마지.. 31. Merge Sort 이번에는 $\Theta(n^2)$보다 빠른 시간복잡도를 갖는 정렬 방법을 알아보자. 그중 가장 간단하다고 할 수 있는 병합 정렬(합병 정렬, Merge Sort)은 데이터를 여러 구간으로 분할한 후 각각의 구간을 정렬한 후 합치는 방법으로 데이터를 정렬한다. 분할 정복을 이용한 정렬 방법으로 볼 수도 있다. (사실 시간복잡도가 $\Theta(n\text{ lg }n)$인 정렬 알고리즘들 대부분이 분할 정복을 기반으로 하지만 병합 정렬에서 그 특징이 가장 두드러진다고 할 수 있다.) 다음은 병합 정렬 과정을 시뮬레이션한 것이다. 그림으로 도식화하면 다음과 같다. 시뮬레이션에서도 알 수 있듯이 원소 $n$개의 정렬과 병합을 $\Theta(n)$ 시간에 수행할 수 있기 때문에 시간복잡도가 $\Theta(n\t.. 30. Insertion Sort 삽입 정렬(Insertion Sort)은 각각의 원소를 이전에 정렬한 앞쪽 원소들과 비교해서 맞는 위치에 추가하는 과정을 반복한다. 원소를 앞쪽에 추가하면 이전에 정렬된 원소 중 이번 원소가 추가될 자리 뒤쪽에 있는 원소들의 위치가 하나씩 뒤로 밀리게 되므로 단순히 각각의 원소를 바로 앞 원소부터 차례로 비교하면서 비교 관계가 바뀌었다면 서로 바꾸는 식으로 구현하면 된다. 다음은 이전 글에 예시로 나온 정렬을 C++에서 삽입 정렬로 구현한 코드이다. for(k = 0; k++ 1 && a[i - 1] > a[i]; i--)swap(a[i - 1], a[i]); } 이 코드는 굉장히 간단하고, 시간복잡도가 $O(n^2)$이라서 앞의 두 코드보다 약간 더 빠른 경우가.. 29. Selection Sort 선택 정렬(Selection Sort)은 버블 정렬과는 다르게 비교 관계가 바뀐 쌍을 발견해도 바로 바꾸지 않고 마지막 값까지 확인한 다음 최솟값을 찾아서 제자리에 넣는 과정을 반복한다. 맨 처음에는 $1\text{~}n$번째 원소 중 가장 앞에 오는 것을 찾아서 첫 번째 원소와 바꾸고, 다음에는 $2\text{~}n$번째 원소 중 가장 앞에 오는 것을 찾아서 두 번째 원소와 바꾸고, 같은 방법으로 $(n-1)\text{~}n$번째 원소까지 확인하게 되면 정렬이 완료된다. 다음은 이전 글에 예시로 나온 정렬을 C++에서 선택 정렬로 구현한 코드이다. for(k = 1; k < n; k++) { for(i = m = k; i 28. Bubble Sort 버블 정렬(거품 정렬, Bubble Sort)은 가장 간단한 정렬 방법의 하나로 인접한 두 원소를 비교하는 과정을 반복한다. 처음에는 $1$번째와 $2$번째 원소를 비교하고, $2$번째와 $3$번째 원소를 비교하고, 이런 식으로 계속해서 비교하며 $(n-1)$번째와 $n$번째 원소를 비교한다. 만약 비교한 두 원소의 순서가 바뀌어 있다면 두 원소를 바꾼다. 이렇게 차례대로 한 번 비교를 실행하면 $n$번째 원소를 제자리에 넣을 수 있다. 이제 정렬해야 하는 원소는 $(n-1)$개이고, 다시 앞에서부터 비교를 실행하는데 이번에는 $(n-2)$번째와 $(n-1)$번째 원소를 비교하는 것까지 하면 된다. 이런 식으로 차례대로 한 번 비교를 실행할 때마다 원소 하나의 위치가 추가로 맞게 되고 이 과정을 $(n-.. 27. Sorting & Search Intro 카테고리 B에서 기본적인 문제 해결 방법들을 차례로 소개했는데, 여기서 빠진 두 가지가 있다. 정렬(Sorting)과 탐색(Search)이다. 정렬은 데이터를 특정한 기준에 따라 순서대로 나열하는 것이고, 탐색은 데이터의 집합에서 특정 기준을 만족하는 데이터를 찾는 것이다. 정렬과 탐색은 다양한 알고리즘의 기본이 되는데, 예를 들어 그리디 문제에서 특정 기준에 따라 '가장 ~한 것'부터 처리하기 위해서는 데이터들을 그 기준에 따라 정렬해야 한다. 대부분의 프로그래밍 언어에서는 내장 정렬 함수와 일부 탐색 함수를 제공하기 때문에 그것들의 사용법을 익혀서 쓰는 것이 쉽고 정확하지만, 상황에 따라 적절한 방법을 선택하기 위해서는 다양한 정렬과 탐색 방법을 이해할 필요가 있다. 카테고리 C에서는 $8$가지의 주.. 이전 1 2 다음
