안녕하세요! 이번 글에서는 C++을 이용한 코딩테스트 문제 중 하나인 “K번째 수 구하기”에 대해 다뤄보겠습니다. 쿠폰 픽업과 같이 실생활에서도 한 번쯤은 고민해본 K번째 수 구하기 문제는 알고리즘 문제풀이에서 자주 접할 수 있는 문제 중 하나입니다. 이번 포스트에서는 문제 정의부터 풀이 과정, C++ 코드 구현까지 상세히 설명하겠습니다.
문제 정의
주어진 정수 배열이 있고, 이 배열에서 K번째로 작은 수를 찾는 문제입니다. 여기서 K는 1부터 시작하는 정수로, 첫 번째로 작은 수, 두 번째로 작은 수, …의 의미를 갖습니다.
예를 들어, 다음과 같은 입력을 고려해 봅시다:
배열: [3, 1, 2, 4, 5] K: 3
주어진 배열에서 3번째로 작은 수는 3입니다. 따라서 이 경우의 정답은 3이 됩니다.
입력 형식
- 첫 번째 줄: 배열의 길이 N (1 <= N <= 100,000)
- 두 번째 줄: 정수 배열 A (1 <= A[i] <= 10^9)
- 세 번째 줄: 정수 K (1 <= K <= N)
출력 형식
K번째로 작은 수를 출력합니다.
문제 풀이 계획
이 문제를 해결하기 위해 사용할 수 있는 몇 가지 알고리즘을 생각해 볼 수 있습니다.
- 정렬: 배열을 정렬한 후 K번째 인덱스를 반환합니다.
- 최소힙 사용: 힙을 사용해서 K번째로 작은 수를 찾아낼 수 있습니다.
- 퀵 선택 알고리즘: 평균 O(N) 시간복잡도로 K번째 수를 찾을 수 있는 알고리즘입니다.
여기서는 가장 직관적이고 이해하기 쉬운 방법인 배열 정렬을 사용한 풀이를 구현해 보겠습니다.
구현하기
먼저 C++의 vector를 사용하여 배열을 입력받고, sort() 함수를 이용해 정렬하겠습니다. 그 후, K번째 수를 출력하는 방식으로 프로그램을 구성하겠습니다.
코드 구현
#include#include #include // sort()의 사용을 위해 include using namespace std; int main() { int N, K; // 배열의 크기 N 입력 cout << "배열의 길이 N을 입력하세요: "; cin >> N; vector A(N); // 배열 A 입력 cout << "정수 배열 A를 입력하세요 (띄어쓰기로 구분): "; for(int i = 0; i < N; i++) { cin >> A[i]; } // K 값 입력 cout << "K 값을 입력하세요: "; cin >> K; // 배열 정렬 sort(A.begin(), A.end()); // K번째 수 출력 (인덱스는 K-1) cout << K << "번째 수는: " << A[K - 1] << endl; return 0; }
코드 설명
이 코드는 다음과 같은 흐름으로 동작합니다:
- 사용자로부터 배열의 길이 N을 입력받습니다.
- N 길이의 정수 형 벡터 A를 생성합니다.
- 사용자로부터 배열 A의 원소를 입력받습니다.
- K 값을 입력받습니다.
- 배열 A를 오름차순으로 정렬합니다.
- K번째 수를 출력합니다. C++에서는 인덱스가 0부터 시작하므로 K-1을 사용해야 합니다.
코드 분석
문제의 입력은 최대 100,000개로, 최악의 경우 O(N log N)의 시간복잡도를 가진 정렬을 수행하게 됩니다. 정렬 후에는 K번째 수를 O(1) 시간에 찾을 수 있으므로, 전체 시간복잡도는 O(N log N)입니다. 이는 주어진 시간 제한 내에 충분히 해결할 수 있는 복잡도입니다.
테스트 케이스
위 코드를 검증하기 위해 몇 가지 테스트 케이스를 고려해 보겠습니다:
테스트 케이스 1
입력: 5 3 1 2 4 5 3 출력: 3번째 수는: 3
테스트 케이스 2
입력: 10 10 9 8 7 6 5 4 3 2 1 5 출력: 5번째 수는: 5
테스트 케이스 3
입력: 5 1 10000 500 999 1000 2 출력: 2번째 수는: 500
결과 및 최적화
기본적인 풀이를 구현해 보았습니다. 정렬을 사용한 방법은 직관적이며 구현이 용이하지만, 배열의 크기가 매우 클 경우 다른 방법이 필요할 수 있습니다. 예를 들어, 퀵 선택 알고리즘을 사용하는 방법이 있습니다. 퀵 선택 알고리즘은 평균적으로 O(N)의 성능을 가지며, 메모리가 제한된 경우 유용하게 사용될 수 있습니다.
퀵 선택 알고리즘 개요
퀵 선택 알고리즘은 분할 정복 알고리즘의 일종으로, 랜덤 피벗을 선택하여 배열을 두 부분으로 나누고 K번째 수가 어떤 부분에 있는지를 판별하여 해당 부분만 계속 찾는 방법입니다. 매우 큰 배열에서도 빠르게 K번째 수를 찾을 수 있습니다.
퀵 선택 구현 예시
#include <iostream> #include <vector> #include <cstdlib> // rand() 함수를 위해 using namespace std; // 배열에서 K번째 수를 찾는 퀵 선택 알고리즘 int quickSelect(vector& A, int left, int right, int K) { if (left == right) return A[left]; int pivotIndex = left + rand() % (right - left); int pivotValue = A[pivotIndex]; // 피벗을 배열의 맨 끝으로 이동 swap(A[pivotIndex], A[right]); int storeIndex = left; for (int i = left; i < right; i++) { if (A[i] < pivotValue) { swap(A[storeIndex], A[i]); storeIndex++; } } // 피벗을 자신의 위치로 이동 swap(A[storeIndex], A[right]); if (K == storeIndex) return A[K]; else if (K < storeIndex) return quickSelect(A, left, storeIndex - 1, K); else return quickSelect(A, storeIndex + 1, right, K); } int main() { int N, K; cout << "배열의 길이 N을 입력하세요: "; cin >> N; vector A(N); cout << "정수 배열 A를 입력하세요 (띄어쓰기로 구분): "; for(int i = 0; i < N; i++) { cin >> A[i]; } cout << "K 값을 입력하세요: "; cin >> K; int result = quickSelect(A, 0, N - 1, K - 1); cout << K << "번째 수는: " << result << endl; return 0; }
마무리
오늘은 C++을 이용하여 K번째 수를 찾는 문제를 해결하는 방법에 대해 알아보았습니다. 기본적인 방법으로는 배열을 정렬하여 K번째 수를 찾는 방법을 구현하였고, 더 효율적인 방법으로 퀵 선택 알고리즘에 대해서도 간략히 설명드렸습니다. 이러한 문제들은 코딩 테스트에서 자주 출제되므로 반복적으로 학습해 두는 것이 좋습니다. 이 문제를 통해 알고리즘의 기초적인 이해와 C++ 프로그래밍 능력을 키우는 데 도움이 되길 바랍니다.
독서 감사합니다! 추가적인 질문이 있으시면 댓글로 남겨주세요.