목차
백준 단계별로 풀어보기
25.10.18
13단계: 정렬
2751번: 수 정렬하기 2
문제 링크 : https://www.acmicpc.net/problem/2751
문제 풀이
>> 문제를 풀기 위해 알아야 할 개념
- 퀵 정렬(Quick Sort)
: 분할 정복 방법을 통해 정렬하는 알고리즘으로 다음과 같은 과정을 통해 정렬한다.
- 원소 하나를 기준(피벗, pivot)으로 삼는다.
- 피벗보다 작은 것을 앞으로 빼내고 그 뒤에 피벗을 옮겨 피벗보다 작은 것, 큰 것으로 나눈다. --> 이를 'partition step'이라 한다.
- 나누어진 각각에서 다시 피벗을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다.
→ 퀵 정렬의 핵심은 어떻게 pivot을 선정하는가?
: 피벗을 최솟값이나 최댓값으로 계속해서 잡게 되는 최악의 경우 O(n²)의 시간복잡도를 갖게 된다.
>> pivot을 선정하는 여러가지 방식
- 첫번째 값이나 마지막 값을 pivot으로 선정한다. --> 퀵 정렬의 원리와 과정을 이해하기 가장 용이한 방법
- 중간값을 pivot으로 선정한다.
- 무작위 값을 pivot으로 선정한다.
- Median of Three : 첫번째 값, 중간값, 마지막 값을 먼저 정렬하고 그 중 중간값을 pivot으로 선정한다. --> 성능적으로 더욱 향상된 방식이다.
>> Partition Step 방식
- Hoare Partition : 주로 첫번째 값을 pivot으로 선정하고, 양쪽 끝에서 포인터를 시작해 pivot보다 작은 값을 앞으로, pivot보다 큰 값을 뒤로 모은 뒤, 마지막에 pivot을 정확한 자리에 이동시킨다.
- 구현이 좀 복잡하지만 성능이 더 우수하다.
- Lomuto Partition : 마지막 값을 pivot으로 고정하고, 하나의 포인터를 사용해서 pivot보다 작은 값들을 앞으로 모은 뒤, 마지막에 pivot을 정확한 자리에 이동시킨다.
- 비효율적이라 큰 배열이나 중복이 많은 데이터에서 성능이 저하되지만 간단하고 직관적이다.
ex) 첫번째 값을 pivot으로 선정한 방식 (Hoare Partition)
- 코드
private int Partition(int[] arr, int l, int h)
{
int pivot = arr[l]; // pivot 설정
int low = l + 1; // low는 pivot의 바로 다음 위치
int high = h;
while (low <= high)
{
if (arr[low] < pivot) // pivot보다 큰 값이 나올 때까지 이동
{
low++;
continue;
}
if (arr[high] > pivot) // pivot보다 작은 값이 나올 때까지 이동
{
high--;
continue;
}
if (low < high) // low와 high가 멈춘 지점이 서로 역전되지 않았다면
(arr[low], arr[high]) = (arr[high], arr[low]); // swap
}
(arr[l], arr[high]) = (arr[high], arr[l]); // pivot과 high swap
return high; // pivot 위치 반환
}
public void MyQuickSort(int[] arr, int l, int h)
{
if (l < h)
{
int pivot = Partition(arr, l, h);
MyQuickSort(arr, l, pivot - 1);
MyQuickSort(arr, pivot + 1, h);
}
}
※ 이해를 위한 영상
└ 풀이 및 오답노트
: 시간 초과로 자꾸 실패하였다.
>> 첫 오답
- 작성한 코드
<hide/>
class Backjoon
{
static void Main(string[] args)
{
int count = int.Parse(Console.ReadLine());
int[] arr = new int[count];
for (int i = 0; i < count; i++)
{
arr[i] = int.Parse(Console.ReadLine());
}
MyQuickSort(arr, 0, count - 1);
foreach (var t in arr)
{
Console.WriteLine(t);
}
}
private static int Partition(int[] arr, int l, int h)
{
int pivot = arr[l];
int low = l + 1;
int high = h;
while (low <= high)
{
if (arr[low] < pivot)
{
low++;
continue;
}
if (arr[high] > pivot)
{
high--;
continue;
}
if (low < high)
(arr[low], arr[high]) = (arr[high], arr[low]);
}
(arr[l], arr[high]) = (arr[high], arr[l]);
return high;
}
public static void MyQuickSort(int[] arr, int l, int h)
{
if (l < h)
{
int pivot = Partition(arr, l, h);
MyQuickSort(arr, l, pivot - 1);
MyQuickSort(arr, pivot + 1, h);
}
}
}
>> 두 번째 오답
: Console.WriteLine()이 생각보다 시간을 많이 잡아먹기 때문에 StringBuilder를 활용하여 출력하도록 변경
- 작성한 코드
<hide/>
using System.Text;
class Backjoon
{
static void Main(string[] args)
{
StringBuilder sb = new StringBuilder();
int count = int.Parse(Console.ReadLine());
int[] arr = new int[count];
for (int i = 0; i < count; i++)
{
arr[i] = int.Parse(Console.ReadLine());
}
MyQuickSort(arr, 0, count - 1);
foreach (var t in arr)
{
sb.AppendLine($"{t}");
}
Console.Write(sb.ToString().TrimEnd());
}
private static int Partition(int[] arr, int l, int h)
{
int pivot = arr[l];
int low = l + 1;
int high = h;
while (low <= high)
{
if (arr[low] < pivot)
{
low++;
continue;
}
if (arr[high] > pivot)
{
high--;
continue;
}
if (low < high)
(arr[low], arr[high]) = (arr[high], arr[low]);
}
(arr[l], arr[high]) = (arr[high], arr[l]);
return high;
}
public static void MyQuickSort(int[] arr, int l, int h)
{
if (l < h)
{
int pivot = Partition(arr, l, h);
MyQuickSort(arr, l, pivot - 1);
MyQuickSort(arr, pivot + 1, h);
}
}
}
>> 최종 수정
: StringBuilder를 사용해도 시간 초과가 발생했다. 이는 현재 작성한 정렬 알고리즘으로는 이미 정렬된 입력(예: {5, 4, 3, 2, 1}, {1, 2, 3, 4, 5})과 같이 최악의 경우 O(n²)의 시간복잡도를 갖게 될 수도 있기 때문이다.
--> 처음에 pivot을 설정할 때, 랜덤으로 정하여 분할의 편향을 줄인다. 이후, 랜덤으로 정한 pivot을 첫번째 값과 swap하여 기존의 Quick Sort 방식대로 정렬한다.
>> 풀이
: 랜덤으로 pivot을 선정하고 이를 첫번째 값과 swap하여 Hoare 방식으로 Quick Sort
- 랜덤으로 pivot 값을 뽑기 위해 Random을 선언한다. --> Partition 함수에서 사용할 것이기 때문에 Main 밖에 static으로 선언한다.
- StringBuilder를 선언하고, 입력값을 받아 int값으로 변환하여 수의 개수를 담을 변수 count 에 담고, 수를 담을 int형 배열 arr 를 초기화한다.
- for 반복문을 통해 입력 받은 수를 int값으로 변환하여 arr 에 담는다.
- 만든 MyQuickSort 함수를 통해 배열 arr 를 정렬한다.
- foreach 반복문을 통해 배열 arr 에 있는 값을 StringBuilder에 담는다.
- StringBuilder에 있는 값을 출력한다.
정답 코드
using System.Text;
class Backjoon
{
static Random rand = new Random();
static void Main(string[] args)
{
StringBuilder sb = new StringBuilder();
int count = int.Parse(Console.ReadLine());
int[] arr = new int[count];
for (int i = 0; i < count; i++)
{
arr[i] = int.Parse(Console.ReadLine());
}
MyQuickSort(arr, 0, count - 1);
foreach (var t in arr)
sb.AppendLine($"{t}");
Console.Write(sb.ToString().TrimEnd());
}
private static int Partition(int[] arr, int l, int h)
{
int randomPivot = rand.Next(l, h + 1);
(arr[l], arr[randomPivot]) = (arr[randomPivot], arr[l]);
int pivot = arr[l];
int low = l + 1;
int high = h;
while (low <= high)
{
if (arr[low] < pivot)
{
low++;
continue;
}
if (arr[high] > pivot)
{
high--;
continue;
}
if (low < high)
(arr[low], arr[high]) = (arr[high], arr[low]);
}
(arr[l], arr[high]) = (arr[high], arr[l]);
return high;
}
public static void MyQuickSort(int[] arr, int l, int h)
{
if (l < h)
{
int pivot = Partition(arr, l, h);
MyQuickSort(arr, l, pivot - 1);
MyQuickSort(arr, pivot + 1, h);
}
}
}'Development > Baekjoon' 카테고리의 다른 글
| [C#] 1427번: 소트인사이드 (0) | 2025.10.20 |
|---|---|
| [C#] 10989번: 수 정렬하기 3 (0) | 2025.10.19 |
| [C#] 25305번: 커트라인 (0) | 2025.10.17 |
| [C#] 2587번: 대표값2 (0) | 2025.10.16 |
| [C#] 2750번: 수 정렬하기 (0) | 2025.10.15 |
