코딩 테스트에서 자주 출제되는 문제 유형인 ‘K번째 수 구하기’에 대한 자세한 설명과 문제 해결 방법을 소개합니다.
문제 설명
주어진 배열 arr와 정수 K가 있을 때, K번째로 작은 수를 찾아 반환하는 문제입니다. 배열은 0부터 시작하는 인덱스를 가지며, 같은 수가 여러 개 있을 경우, 여러 개의 K번째 수 중 하나를 반환할 수 있습니다.
예를 들어, 배열이 [7, 10, 4, 3, 20, 15]이고 K=3일 경우, 3번째로 작은 수는 7입니다.
입력 형식
입력으로는 다음과 같은 형식이 주어집니다:
- 첫 번째 줄: 배열의 크기
N(1 <= N <= 10^6) - 두 번째 줄:
N개의 정수 (배열의 원소는 -10^9 이상 10^9 이하) - 세 번째 줄: 정수
K(1 <= K <= N)
입력 예시
6
7 10 4 3 20 15
3
출력 형식
배열 내에서 K번째로 작은 수를 출력합니다.
출력 예시
7
문제 풀이 과정
1단계: 문제 이해
우리는 그러면 주어진 배열에서 K번째로 작은 수를 찾아야 합니다. 배열이 정렬되어 있지 않기 때문에, 정렬된 상태에서 K번째 원소의 값을 찾아야 합니다.
2단계: 알고리즘 선택
가장 직관적인 방법은 배열을 정렬한 후 K번째 원소를 반환하는 것입니다. 그러나 이 방법은 O(N log N) 시간 복잡도를 가집니다. 이를 최적화하기 위해 다양한 방법이 존재합니다:
- Quickselect 알고리즘 (평균 O(N) 시간 복잡도)
- Heap 자료구조를 이용한 방법
이번 강좌에서는 Quickselect 방법을 사용하겠습니다.
3단계: Quickselect 설명
Quickselect는 Quick Sort 알고리즘과 유사하며, 피벗(pivot)을 선택하여 왼쪽 부분과 오른쪽 부분으로 나뉘게 됩니다. 이때 K의 위치에 따라 결과를 도출합니다.
Quickselect의 과정
- 중간 피벗값을 선택합니다.
- 피벗보다 작거나 같은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동시킵니다.
- K가 피벗 인덱스와 동등하면 피벗을 반환합니다.
- K가 피벗보다 작으면 왼쪽 부분에 대해 Quickselect를 재귀적으로 호출합니다.
- K가 피벗보다 크면 오른쪽 부분에 대해 Quickselect를 재귀적으로 호출합니다.
C# 코드 구현
using System;
using System.Linq;
class KthSmallest
{
public static int QuickSelect(int[] arr, int left, int right, int k)
{
if (left == right) // 배열에 원소가 하나만 있을 경우
return arr[left];
Random random = new Random();
int pivotIndex = left + random.Next(right - left);
int pivot = arr[pivotIndex];
// 피벗을 최우측으로 이동
Swap(arr, pivotIndex, right);
int storeIndex = left;
for (int i = left; i < right; i++)
{
if (arr[i] < pivot)
{
Swap(arr, storeIndex, i);
storeIndex++;
}
}
Swap(arr, storeIndex, right); // 피벗을 제자리에 놓음
if (k == storeIndex) return arr[k];
else if (k < storeIndex) return QuickSelect(arr, left, storeIndex - 1, k);
else return QuickSelect(arr, storeIndex + 1, right, k);
}
private static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void Main()
{
int N = int.Parse(Console.ReadLine());
int[] arr = Console.ReadLine().Split().Select(int.Parse).ToArray();
int K = int.Parse(Console.ReadLine()) - 1; // K를 0-based index로 변환
int result = QuickSelect(arr, 0, N - 1, K);
Console.WriteLine(result);
}
}
코드 설명
위의 C# 코드는 Quickselect 알고리즘을 사용하여 K번째 수를 찾습니다:
QuickSelect메소드: 배열에서 K번째 작은 수를 찾아 반환합니다.Swap메소드: 두 원소의 위치를 바꿉니다.Main: 입력을 받고 실행합니다.
이 알고리즘은 평균적으로 O(N) 시간 복잡도를 가지며, 이는 매우 효율적입니다.
마무리
이번 강좌에서는 C#을 사용하여 ‘K번째 수 구하기’ 문제를 해결하는 방법을 배웠습니다. Quickselect 알고리즘을 통해 효율적으로 문제를 해결하는 방법을 실습함으로써, 코딩 테스트에서 유용한 기법을 익힐 수 있었습니다. 추가적으로 다양한 알고리즘과 문제를 경험하여 더욱 능력을 키우길 바랍니다.