최근 몇 년 간 프로그래밍 및 알고리즘 문제 해결 능력은 IT 업계뿐만 아니라 다양한 분야에서 매우 중요한 평가 기준이 되었습니다. 본 강좌에서는 ‘카드 정렬하기’라는 문제를 통해 기본적인 조작과정, 알고리즘 설계 및 최적화를 배워보도록 하겠습니다. 이 문제는 실무 및 코딩 테스트에서 중요한 정렬 알고리즘의 이해도를 높이는 데 도움이 됩니다.
문제 설명
옛날 카드 게임에서는 카드의 숫자를 정렬하는 것이 필수적입니다. 여러분은 N장의 카드가 있고, 각 카드마다 정수가 적혀 있습니다. 여러분은 이 카드를 오름차순으로 정렬해야 합니다. 하지만, 이 과정에서 몇 가지 규칙이 있습니다:
- 카드는 정수로 이루어져 있으며, 정렬된 순서로 나열해야 합니다.
- 카드의 개수 N (1 ≤ N ≤ 10^6) 입니다.
- 카드에 적힌 숫자는 -10^9 ≤ 숫자 ≤ 10^9 범위 내의 정수입니다.
입력 형식
첫 줄에 카드의 개수 N이 주어지고, 다음 N개의 줄에는 각 카드의 숫자가 주어집니다.
출력 형식
카드를 오름차순으로 정렬한 후, 각 카드의 숫자를 한 줄에 하나씩 출력합니다.
예제
입력: 5 3 1 4 1 5 출력: 1 1 3 4 5
문제 해결 전략
이 문제는 정렬 문제로, 여러 가지 정렬 알고리즘을 사용할 수 있습니다. 그러나 주어진 범위를 고려할 때, 기본적인 정렬 알고리즘인 퀵 정렬이나 병합 정렬을 활용하는 것이 좋습니다. 이 강좌에서는 C++의 STL에 포함된 std::sort 함수를 사용하여 효율적으로 문제를 해결하는 방법을 보여드리겠습니다.
STL 표준 라이브러리의 sort() 함수
C++의 표준 템플릿 라이브러리(STL)에는 sort() 함수가 포함되어 있습니다. 이 함수는 인자로 주어진 컨테이너의 요소들을 정렬해줍니다. std::sort는 평균적으로 O(N log N) 시간복잡도를 가지며, 매우 효율적입니다.
코드 구현
#include <iostream>
#include <vector>
#include <algorithm> // sort()를 사용하기 위해 포함합니다.
int main() {
int N;
std::cin >> N; // 카드의 개수 입력받기
std::vector<int> cards(N); // 카드 숫자를 저장할 벡터 생성
// 카드 숫자 입력받기
for (int i = 0; i < N; i++) {
std::cin >> cards[i];
}
// 카드 숫자 정렬
std::sort(cards.begin(), cards.end());
// 정렬된 카드 숫자 출력
for (int i = 0; i < N; i++) {
std::cout << cards[i] << std::endl;
}
return 0;
}
코드 분석
위 코드는 다음과 같은 과정으로 구성되어 있습니다:
- 라이브러리 포함:
#include <iostream>,#include <vector>,#include <algorithm>를 포함하여 입력과 출력 및 정렬을 위한 기본 라이브러리를 추가합니다. - 입력: 사용자로부터 카드의 개수 N을 입력받고, 이후 N개의 카드 숫자를 벡터에 저장합니다.
- 정렬:
std::sort()함수를 사용하여 벡터에 저장된 카드 숫자를 오름차순으로 정렬합니다. 이때,begin()과end()메소드를 사용하여 시작과 끝 위치를 설정합니다. - 출력: 정렬된 카드 숫자를 출력합니다.
시간 복잡도 분석
위에서 언급한 std::sort() 함수는 평균적으로 O(N log N) 복잡도로 작동합니다. 이는 대량의 데이터를 처리하는 데 매우 효율적입니다. 입력 크기 N이 최대 10^6일 때, 정렬을 수행하는데 충분한 시간 내에 실행가능합니다.
결론
이번 강좌를 통해 카드 정렬 문제를 해결하는 과정을 배웠습니다. 문제를 해결하기 위해 STL의 sort() 함수를 활용하여 간단하면서도 효율적인 코드를 작성할 수 있었습니다. 이러한 정렬 알고리즘은 많은 프로그래밍 문제와 실제 상황에서도 자주 사용되므로, 잘 익히고 활용하는 것이 중요합니다.
다음 시간에는 추가적인 알고리즘 문제를 통해 여러분의 코딩 테스트 능력을 한층 더 발전시켜보도록 하겠습니다.
감사합니다!