파이썬 코딩테스트 강좌, 수 정렬하기 2

1. 문제 설명

주어진 수를 오름차순으로 정렬해야 합니다. 이 문제는 파이썬을 사용하여 정렬 알고리즘을 이해하고 적용하는 데 중점을 두고 있습니다. 입력은 N개의 수로 이루어진 리스트이며, 출력은 정렬된 리스트가 되어야 합니다.

2. 문제 조건

  • 입력: 첫째 줄에 수의 개수 N이 주어집니다. (1 ≤ N ≤ 1,000,000)
  • 둘째 줄에는 N개의 정수 A가 주어집니다. (A는 -1,000,000,000 이상 1,000,000,000 이하의 정수입니다.)
  • 출력: 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력합니다.

3. 입력 예시

5
3
1
2
5
4

4. 출력 예시

1
2
3
4
5

5. 문제 접근 방법

이 문제의 해결 방안으로는 다양한 정렬 알고리즘이 존재하지만, 파이썬에서는 기본적으로 제공하는 sorted() 함수를 이용하는 것이 가장 효율적이며 간단한 방법입니다. 하지만 학습 목적으로 다른 정렬 알고리즘도 살펴보겠습니다.

5.1. 버블 정렬(Bubble Sort)

버블 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 큰 값을 뒤쪽으로 보내는 방식입니다. 복잡도는 평균 O(N^2)입니다. 직관적이지만 성능면에서 비효율적입니다.

5.2. 선택 정렬(Selection Sort)

선택 정렬은 리스트에서 가장 작은 값을 선택하여 정렬 위치에 놓고 나머지 리스트에서 반복하는 방식입니다. 이 알고리즘의 평균 복잡도도 O(N^2)입니다.

5.3. 삽입 정렬(Insertion Sort)

삽입 정렬은 정렬된 리스트를 하나씩 확장하는 방식입니다. 평균 O(N^2) 복잡도를 가지며, 정렬된 데이터에 대해서는 매우 효율적입니다.

5.4. 파이썬의 정렬 함수

파이썬의 sorted() 함수는 Timsort라는 알고리즘을 사용하고 있으며, 평균 O(N log N)의 성능을 제공합니다. 이는 최적화된 정렬로, 실제로 많은 데이터에서 뛰어난 성능을 보입니다.

6. 코드 구현

아래의 코드는 주어진 입력을 받아 정렬하는 방법을 보여줍니다. 

import sys

input = sys.stdin.read
data = input().splitlines()

N = int(data[0])  # 첫 줄에서 수의 개수 N을 읽어온다.
numbers = []

for i in range(1, N + 1):  # 두 번째 줄부터 수를 읽어온다.
    numbers.append(int(data[i]))

numbers.sort()  # 기본 sort 함수를 사용하여 정렬

for number in numbers:  # 정렬된 수를 출력
    print(number)

7. 고급 정렬 알고리즘: 병합 정렬(Merge Sort)

병합 정렬은 분할 정복 알고리즘의 일종으로, 리스트를 재귀적으로 나누고 정렬된 하위 리스트를 병합하여 전체를 정렬하는 방식입니다. 평균 복잡도는 O(N log N)으로, 매우 효율적입니다.

7.1. 병합 정렬 구현

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 사용 예시
if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = list(map(int, input().split()))
    
    sorted_data = merge_sort(data)
    for number in sorted_data:
        print(number)

8. 결론

이번 문제를 통해 파이썬의 기본 정렬 기능뿐만 아니라 다양한 정렬 알고리즘을 배울 수 있었습니다. 각 알고리즘의 특성과 복잡도, 사용 방법을 이해하는 것이 중요합니다. 이 지식은 향후 알고리즘 문제를 해결하는 데 도움이 될 것입니다. 다양한 문제를 풀어보며 실력을 키우는 것이 중요합니다.

© 2023 알고리즘 교육 기관