안녕하세요, 블로그 독자 여러분! 오늘은 C# 코딩테스트 강좌의 한 부분으로 줄 세우기 문제를 다루겠습니다. 이 문제는 간단해 보일 수 있지만, 알맞은 알고리즘을 사용하지 않으면 매우 복잡해질 수 있습니다. 또한 실제 취업의 코딩 테스트에서 자주 등장하는 문제 유형 중 하나입니다.
문제 설명
주어진 학생들의 키 정보를 통해 그들을 줄 세우는 문제입니다. 학생들은 키에 따라 오름차순으로 정렬되어야 하며, 같은 키를 가진 학생들은 서로의 순서를 유지해야 합니다. 즉, 정렬 시 안정성을 유지해야 합니다.
문제 정의
주어진 학생들의 키를 배열로 받을 때, 배열을 오름차순으로 정렬해야 합니다.
입력
- 정수 N: 학생의 수 (1 ≤ N ≤ 100,000)
- 정수 배열 heights: 학생들의 키 (1 ≤ heights[i] ≤ 200 cm)
출력
- 정렬된 학생들의 키를 반환해야 합니다.
예제 입력 및 출력
입력: [160, 155, 170, 160, 175]
출력: [155, 160, 160, 170, 175]
문제 해결 전략
문제에 대한 해결 전략을 세우는 것은 중요합니다. 학생들의 키를 정렬해야 하므로, 효율적인 정렬 알고리즘을 적용해야 합니다. 여러 가지 정렬 알고리즘 중에서, 병합 정렬(Merge Sort)이나 퀵 정렬(Quick Sort) 같은 O(N log N) 시간 복잡도를 가진 알고리즘을 쓸 수 있습니다.
1. 병합 정렬 설명
병합 정렬은 분할 정복 알고리즘으로, 배열을 두 개의 하위 배열로 나누고 각각을 정렬한 후, 정렬된 하위 배열을 병합하여 최종적으로 정렬된 배열을 만드는 방식입니다. 이 방식은 안정적이며, 정렬된 배열이 필요할 때 유용합니다.
2. 퀵 정렬 설명
퀵 정렬 역시 분할 정복 알고리즘입니다. 피벗을 기준으로 두 개의 부분 배열로 나누고, 재귀적으로 정렬합니다. 평균 시간 복잡도는 O(N log N)이지만, 최악의 경우 O(N^2)가 될 수 있습니다. 하지만 적절한 피벗 선택을 통해 성능을 개선할 수 있습니다.
C# 코드 구현
이번 섹션에서는 C# 언어로 해당 문제를 해결하는 코드를 작성해보겠습니다. 아래는 병합 정렬을 사용해 학생들의 키를 정렬하는 코드입니다.
using System;
class Sort
{
public static void MergeSort(int[] heights, int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
MergeSort(heights, left, mid);
MergeSort(heights, mid + 1, right);
Merge(heights, left, mid, right);
}
}
public static void Merge(int[] heights, int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
for (int i = 0; i < n1; i++)
leftArray[i] = heights[left + i];
for (int j = 0; j < n2; j++)
rightArray[j] = heights[mid + 1 + j];
int k = left;
int iIndex = 0, jIndex = 0;
while (iIndex < n1 && jIndex < n2)
{
if (leftArray[iIndex] <= rightArray[jIndex])
{
heights[k] = leftArray[iIndex];
iIndex++;
}
else
{
heights[k] = rightArray[jIndex];
jIndex++;
}
k++;
}
while (iIndex < n1)
{
heights[k] = leftArray[iIndex];
iIndex++;
k++;
}
while (jIndex < n2)
{
heights[k] = rightArray[jIndex];
jIndex++;
k++;
}
}
static void Main(string[] args)
{
int[] heights = { 160, 155, 170, 160, 175 };
MergeSort(heights, 0, heights.Length - 1);
Console.WriteLine("정렬된 키: " + string.Join(", ", heights));
}
}
코드 설명
위 코드는 병합 정렬 알고리즘을 이용하여 주어진 배열을 정렬하는 예시입니다. MergeSort 메소드는 재귀적으로 배열을 분할하고, Merge 메소드는 두 하위 배열을 병합하여 정렬합니다.
코드 흐름
- MergeSort 메소드: 배열을 재귀적으로 반으로 나누어 정렬합니다.
- Merge 메소드: 두 개의 정렬된 하위 배열을 하나로 병합하여 정렬된 배열을 만듭니다.
- Main 메소드: 프로그램의 시작점으로, 예시 배열을 정의하고 정렬 후 결과를 출력합니다.
성능 분석
병합 정렬의 시간 복잡도는 O(N log N)이며, 최악의 경우에도 동일한 복잡도를 가집니다. 공간 복잡도는 O(N)입니다. 이 점은 큰 데이터셋을 처리할 때 유리합니다. 정렬이 안정적(stable)하기 때문에, 예를 들어 키가 같은 경우 원래의 순서를 보장할 수 있습니다.
이 문제의 응용
줄 세우기 문제는 여러 분야에 응용될 수 있습니다. 예를 들어, 대기열 관리, 학생 성과 분석 등 다양한 상황에서 유용하게 쓰일 수 있습니다. 이 문제를 해결하면서 다른 데이터 정렬 문제로 확장할 수 있는 가능성을 고려해보면 좋겠습니다.
결론
이번 포스트에서는 C#을 사용하여 줄 세우기 문제를 해결하는 방법을 알아보았습니다. 문제를 정의하고, 이를 해결하기 위한 알고리즘과 코드를 구현하는 과정을 통해 알고리즘 사고를 키워나갈 수 있습니다. 다양한 문제를 통해 알고리즘적 사고를 발전시키는 것이 중요합니다.
다음 시간에는 또 다른 유형의 알고리즘 문제를 다뤄보도록 하겠습니다. 질문이나 피드백은 댓글로 남겨주세요. 고맙습니다!