코딩테스트에서 수 정렬하기는 매우 기본적이면서도 중요한 문제입니다. 이 글에서는 C++를 사용하여 수를 정렬하는 방법에 대해 심도 깊은 설명과 함께 알고리즘 문제를 해결하는 과정을 안내하겠습니다.
문제 설명
문제는 주어진 수들을 정렬하여 출력하는 것입니다. 구체적인 입력과 출력의 조건은 다음과 같습니다.
- 첫째 줄에는 정렬할 원소의 개수 N이 주어집니다. (1 ≤ N ≤ 1,000,000)
- 둘째 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어집니다. (−1,000,000,000 ≤ A[i] ≤ 1,000,000,000)
출력은 오름차순으로 정렬된 N개의 정수를 한 줄에 하나씩 출력해야 합니다.
입력 예시
5
5
4
3
2
1
출력 예시
1
2
3
4
5
문제 풀이 과정
문제를 해결하기 위해 여러 가지 방법이 있지만, 여기서는 C++의 STL(Standard Template Library)을 활용한 sorting 알고리즘을 이용할 것입니다. STL의 sort() 함수는 빠르고 효율적인 정렬 알고리즘으로, 일반적으로 O(N log N)의 시간 복잡도를 가집니다.
1. 필요한 헤더 파일 포함하기
STL의 sort 함수와 벡터를 사용하기 위해 필요한 헤더 파일을 포함합니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
2. 메인 함수 작성하기
입력을 처리하고, 정렬 후 결과를 출력하는 메인 함수를 작성하겠습니다.
int main() {
int N;
cin >> N; // 원소의 개수 입력 받기
vector<int> A(N); // 크기가 N인 벡터 A 선언
// N개의 정수 입력 받기
for(int i = 0; i < N; i++) {
cin >> A[i];
}
// 벡터 A 정렬
sort(A.begin(), A.end());
// 정렬된 결과 출력
for(const int &num : A) {
cout << num << endl;
}
return 0;
}
3. 코드 설명
위 코드는 다음과 같은 단계로 작동합니다:
- 정수 N을 입력 받아 정렬할 숫자의 개수를 결정합니다.
- 크기가 N인 벡터 A를 생성하여, N개의 정수를 입력 받습니다.
- STL의
sort()함수를 사용하여 벡터 A를 정렬합니다. - 정렬된 벡터의 내용을 출력합니다.
시간 복잡도 분석
본 문제를 해결하기 위한 알고리즘의 시간 복잡도는 O(N log N)입니다. 이는 입력받는 원소의 개수 N에 비례하여 증가하지만, 가장 일반적인 정렬 알고리즘인 quicksort를 기반으로 하기 때문에 실질적으로 매우 빠른 성능을 발휘합니다.
공간 복잡도 분석
공간 복잡도는 O(N)입니다. 벡터 A는 입력된 모든 수를 저장하기 위해 N개의 공간을 할당받기 때문입니다. STL을 사용하여 공간 관리가 효율적이며, 배열 대신 벡터를 사용함으로써 메모리 관리가 용이합니다.
결론
이번 포스팅에서는 C++를 활용하여 기본적인 수 정렬 문제를 경험해 보았습니다. 코딩테스트에서 자주 출제되는 문제 중 하나인 수 정렬하기 문제를 통해, STL을 활용한 정렬 알고리즘의 사용법을 익히고, 시간 복잡도와 공간 복잡도를 분석하는 방법을 배웠습니다. 이러한 기본적인 문제들에 대한 이해는 향후 더 복잡한 문제를 해결하는 데 큰 도움이 될 것입니다.
추가 연습 문제
더 많은 연습을 위해 다음과 같은 변형 문제를 시도해 보세요:
- 입력으로 주어진 수들 중 중복된 수를 제거하고 정렬하여 출력하는 프로그램을 작성하시오.
- 정렬된 수들을 내림차순으로 출력하시오.
- 각 수의 빈도 수를 함께 출력하는 프로그램을 작성하시오. (같은 수가 몇 번 등장하는지를 세어야 함)
이와 같은 추가 연습을 통해 더욱 깊이 있는 경험을 쌓을 수 있습니다.