문제 설명
“수 정렬하기 2” 문제는 입력된 수열을 정렬하여 출력하는 문제입니다. 이 문제는 일반적인 정렬 알고리즘을 이해하고 구현하는 것을 목표로 합니다.
주어진 수 N개의 수가 있을 때, 이 수열을 오름차순으로 정렬하여 출력해야 합니다. 수는 -1000보다 크거나 같고, 1000보다 작거나 같은 정수입니다.
입력 형식
첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 수가 주어집니다.
출력 형식
정렬된 수를 한 줄에 하나씩 출력합니다.
예제 입력
5
5
4
3
2
1
예제 출력
1
2
3
4
5
문제 풀이 과정
1. 문제 이해하기
이 문제는 가장 기본적인 수 정렬 문제로, 다양한 정렬 알고리즘을 활용할 수 있습니다.
기본적으로 C++에서는 표준 라이브러리의 정렬 함수를 사용할 수 있어 효율적인 해결책이 될 수 있습니다.
하지만, 수동으로 정렬 알고리즘을 구현하는 것도 좋은 연습이므로, 선택 정렬과 삽입 정렬의 두 가지 방법을 소개하겠습니다.
2. 기본적인 수집과 저장
입력 데이터를 받아오기 위해 배열이나 벡터를 사용할 수 있습니다. C++에서는 벡터(vector)를 사용하는 것이 일반적입니다.
다음은 벡터를 사용하여 데이터를 저장하는 방법입니다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N; // 수의 개수 입력
vector<int> numbers(N);
for (int i = 0; i < N; i++) {
cin >> numbers[i]; // 수 입력
}
return 0;
}
3. 정렬 알고리즘
입력된 수를 저장한 벡터를 정렬하기 위한 두 가지 방법, 즉 선택 정렬과 삽입 정렬을 구현해보겠습니다.
3-1. 선택 정렬
선택 정렬은 주어진 배열에서 가장 작은(또는 큰) 원소를 선택하여 앞쪽으로 보냅니다. 이를 반복하여 정렬을 완성합니다.
선택 정렬의 시간 복잡도는 O(N^2)입니다.
void selectionSort(vector<int> &arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]); // 원소 교환
}
}
3-2. 삽입 정렬
삽입 정렬은 배열의 각 원소를 적절한 위치에 삽입하여 정렬을 수행합니다.
삽입 정렬의 시간 복잡도는 O(N^2)으로, 데이터가 거의 정렬되어 있을 때 효율적입니다.
void insertionSort(vector<int> &arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 원소 이동
j--;
}
arr[j + 1] = key; // 삽입
}
}
4. 최종 코드
위의 정렬 알고리즘 중 하나를 선택하여 최종 코드를 완성하겠습니다. 아래는 벡터와 표준 라이브러리의 sort 함수를 사용하는 방법입니다.
#include <iostream>
#include <vector>
#include <algorithm> // sort() 함수 포함
using namespace std;
int main() {
int N;
cin >> N; // 수의 개수 입력
vector<int> numbers(N);
for (int i = 0; i < N; i++) {
cin >> numbers[i]; // 수 입력
}
sort(numbers.begin(), numbers.end()); // 정렬 수행
for (int i = 0; i < N; i++) {
cout << numbers[i] << endl; // 정렬된 수 출력
}
return 0;
}
5. 시간 복잡도
위와 같이 표준 라이브러리의 sort 함수를 사용하면, 평균적으로 O(N log N) 시간 복잡도로 정렬이 가능해집니다.
이는 선택 정렬과 삽입 정렬보다 훨씬 더 효율적입니다.
6. 결론
“수 정렬하기 2” 문제를 통해 정렬 알고리즘의 기본 개념과 C++의 벡터 사용 방법에 대해 연습할 수 있었습니다.
다양한 정렬 알고리즘을 이해하고 구현하는 것은 프로그래밍 실력을 높이는 데 매우 유용한 과정입니다.
실무에서도 자주 사용되는 정렬 알고리즘에 대한 이해도를 높이고, 보다 복잡한 알고리즘을 해결하기 위한 초석이 될 것입니다.