C++ 코딩테스트 강좌, 수 정렬하기 1

안녕하세요! 이번 강좌에서는 C++을 이용한 코딩 테스트 문제 중 “수 정렬하기 1″에 대해 다루어 보겠습니다. 이 문제는 정렬 알고리즘의 기초를 다지기에 좋은 문제이며, 다양한 알고리즘을 적용하여 효율성을 비교할 수 있습니다. 문제를 해결하는 과정을 단계별로 살펴보겠습니다.

문제 설명

문제는 다음과 같습니다:

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하여 출력하시오.
(정수 N은 1 이상 1,000,000 이하이다.)

입력 예시:

5
5
3
2
4
1

출력 예시:

1
2
3
4
5

문제 분석

이 문제는 정렬 알고리즘의 기본이 되는 문제로, 주어진 수를 정렬하여 출력하면 됩니다. 정렬은 일반적으로 O(N log N)의 시간 복잡도를 가지는 효율적인 알고리즘을 사용하는 것이 이상적입니다. 가장 많이 사용되는 정렬 알고리즘으로는 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 등이 있습니다. 이 문제에서는 C++의 STL(Standard Template Library)을 활용한 `std::sort` 함수의 사용이 가능하므로 손쉽게 문제를 해결할 수 있습니다.

풀이 과정

1. 입력 처리

우선, 입력을 어떻게 처리할 것인지 결정해야 합니다. C++에서는 cin을 사용하여 표준 입력으로부터 수를 읽어들일 수 있습니다. 주어진 수의 개수를 먼저 입력받고, 그 다음으로 수들을 받아서 벡터에 저장하겠습니다.

2. 정렬 알고리즘 선택

정렬 알고리즘으로는 위에서 언급한 대로 여러 가지가 있으나, C++ STL의 std::sort 함수를 사용하는 것이 가장 간편합니다. 이 함수는 내부적으로 퀵 정렬 알고리즘을 사용하여 평균적으로 O(N log N)의 성능을 제공합니다.

3. 정렬 후 출력

정렬된 결과를 출력하기 위해서는 다시 반복문을 사용해야 합니다. 각 수를 출력할 때 마다 줄 바꿈을 해야 하므로 cout을 활용하면 됩니다.

4. 코드 구현

위의 내용을 바탕으로 전체 코드를 작성해 보겠습니다.

#include 
#include 
#include  // std::sort를 사용하기 위해 포함 필요

using namespace std;

int main() {
    int N;
    cin >> N; // 수의 개수 입력받기

    vector 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;
}

코드 설명

코드를 하나씩 살펴보겠습니다:

  • #include <iostream>: 입출력을 위한 라이브러리입니다.
  • #include <vector>: 동적 배열을 사용하기 위한 라이브러리입니다.
  • #include <algorithm>: STL 알고리즘 함수들을 사용하기 위한 라이브러리입니다.
  • using namespace std;: std 네임스페이스를 사용하기 위해 추가합니다.
  • int N;: 수의 개수를 저장할 변수를 선언합니다.
  • vector numbers(N);: N개의 정수를 저장할 벡터를 선언합니다.
  • cin: 사용자로부터 입력을 받습니다. 수의 개수 N 만큼의 정수를 입력 받습니다.
  • sort(numbers.begin(), numbers.end());: 벡터 내의 수를 오름차순으로 정렬합니다.
  • cout: 정렬된 결과를 출력합니다.

테스트 케이스

이제 코드를 작성했으니 다양한 테스트 케이스에 대해 실행해 보겠습니다. 아래는 몇 가지 예시입니다.

예시 1

입력:

5
5
3
2
4
1

출력:

1
2
3
4
5

예시 2

입력:

10
9
8
7
6
5
4
3
2
1
0

출력:

0
1
2
3
4
5
6
7
8
9

예시 3

입력:

3
1
1
1

출력:

1
1
1

성능 분석

이제 알고리즘의 성능을 분석해보겠습니다. std::sort는 평균적으로 O(N log N)의 성능을 가집니다. 따라서 문제의 조건인 1 이상 1,000,000 이하의 정수를 입력받는 상황에서도 충분히 빠르게 동작할 것입니다. 이 외에도 다양한 정렬 알고리즘을 사용해볼 수 있지만, 문제의 요구사항을 만족시키기에는 std::sort가 가장 적합하다고 할 수 있습니다.

마무리

이번 강좌에서는 C++을 활용한 “수 정렬하기 1” 문제를 다뤄보았습니다. 정렬의 기초와 동시에 STL을 활용하는 방법을 익힐 수 있었습니다. 다음 강좌에서는 더 복잡한 데이터 구조와 알고리즘을 다루어 보도록 하겠습니다. 감사합니다!

작성자: 코딩보이