서론
안녕하세요. 이번 강좌에서는 코딩테스트 준비에 유용한 정렬 알고리즘 중 하나인 ‘삽입 정렬(Insertion Sort)’에 대해 깊이 있게 다루어 보겠습니다. 정렬 알고리즘은 데이터 구조와 알고리즘 문제해결의 기초가 되는 중요한 주제입니다. 특히, 이론적 배경과 코드 구현, 그리고 문제 풀이의 구체적인 사례를 제시하여 독자 여러분의 이해를 돕고자 합니다.
삽입 정렬이란?
삽입 정렬은 데이터가 정렬된 상태에서 새 데이터를 삽입하는 방식으로 작동하는 정렬 알고리즘입니다. 주어진 데이터에서 하나씩 원소를 선택하여, 이미 정렬된 부분과 비교하면서 적절한 위치에 삽입합니다. 이 알고리즘은 매우 직관적이며, 구현하기도 쉽습니다.
삽입 정렬의 작동 원리
삽입 정렬은 다음과 같은 방식으로 작동합니다:
- 정렬되지 않은 리스트에서 첫 번째 원소를 선택합니다. 이 원소는 이미 정렬된 상태로 간주합니다.
- 다음 원소를 선택하여 정렬된 원소들과 비교합니다.
- 현재 선택한 원소가 정렬된 원소보다 작다면, 정렬된 리스트의 적절한 위치에 삽입합니다.
- 이 과정을 리스트의 끝까지 반복합니다.
삽입 정렬의 시간 복잡도
삽입 정렬의 시간 복잡도는 최악의 경우 O(n²)입니다. 그러나 데이터가 거의 정렬된 상태라면 평균적으로 O(n)의 성능을 보여줍니다. 이는 삽입 정렬이 다른 알고리즘들과 비교했을 때 장점이 될 수 있습니다. 특별한 경우에는 O(n)으로 동작하기 때문에 실제 문제에서는 종종 사용됩니다.
삽입 정렬의 C# 구현
이제 실제로 C#을 사용하여 삽입 정렬 알고리즘을 구현해 보겠습니다:
using System;
class Program
{
static void InsertionSort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int key = arr[i];
int j = i - 1;
// 현재 key보다 큰 원소를 한 칸씩 뒤로 이동
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // key를 적절한 위치에 삽입
}
}
static void Main()
{
int[] array = { 12, 11, 13, 5, 6 };
InsertionSort(array);
Console.WriteLine("정렬된 배열: ");
foreach (int num in array)
{
Console.Write(num + " ");
}
}
}
문제 풀이: 주어진 배열 정렬하기
다음은 실제 코딩테스트에서 주어질 수 있는 문제의 예시입니다:
문제: 정수 배열이 주어졌을 때, 삽입 정렬을 사용하여 배열을 오름차순으로 정렬하시오.
입력 예: [64, 34, 25, 12, 22, 11, 90]
출력 예: [11, 12, 22, 25, 34, 64, 90]
위 문제를 해결하기 위해서는 앞서 설명한 삽입 정렬 알고리즘을 구현하면 됩니다. 주어진 배열을 삽입 정렬로 정렬해보겠습니다.
using System;
class InsertionSortExample
{
static void InsertSort(int[] array)
{
for (int i = 1; i < array.Length; i++)
{
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key)
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}
static void Main()
{
int[] nums = { 64, 34, 25, 12, 22, 11, 90 };
InsertSort(nums);
Console.WriteLine("정렬된 배열: ");
foreach (var num in nums)
{
Console.Write(num + " ");
}
}
}
결론
이번 강좌에서는 삽입 정렬 알고리즘에 대해 깊이 이해하고, C#으로 구현하는 방법과 실제 문제를 해결하는 과정을 살펴보았습니다. 비교적 쉬운 이해와 구현 덕분에 삽입 정렬은 많은 코딩테스트 문제의 출제 원본으로 많이 사용됩니다. 이제 여러분도 삽입 정렬을 마스터했으니, 다양한 문제를 풀어보며 더욱 실력을 쌓아보세요!