문제 설명
이번에 공부한 문제는 N개의 수를 오름차순으로 정렬하는 프로그램을 작성하는 것입니다. 문제를 해결하기 위해 효율적인 정렬 알고리즘 중 하나인 병합 정렬(Merge Sort)을 사용해보았습니다.
문제 조건
- 수의 개수 N은 1 이상 1,000,000 이하입니다.
- 각 수는 절댓값이 1,000,000보다 작거나 같은 정수입니다.
- 수는 중복되지 않습니다.
입출력 예
| 입력 | 출력 |
|---|---|
| 5 | 1 |
| 5 | 2 |
| 4 | 3 |
| 3 | 4 |
| 2 | 5 |
| 1 |
문제 해결 방법
병합 정렬
이번 문제를 해결하기 위해 선택한 알고리즘은 병합 정렬입니다. 병합 정렬은 리스트를 반으로 나누어 각각 정렬한 후, 두 정렬된 리스트를 합치는 방식으로 동작합니다. 이 알고리즘의 시간 복잡도는 (O(n \log n))으로 매우 효율적입니다.
시간 복잡도
병합 정렬의 최악, 최선, 평균 시간 복잡도는 모두 (O(n \log n))입니다. 이는 리스트를 반으로 나누고 다시 합치는 과정이 로그 시간에 이루어지기 때문입니다.
공간 복잡도
병합 정렬은 추가적인 리스트를 사용하여 정렬하기 때문에 공간 복잡도는 (O(n))입니다.
코드 구현
다음은 병합 정렬을 사용하여 문제를 해결하는 Python 코드입니다.
def merge_sort(numbers):
if len(numbers) <= 1:
return numbers
mid = len(numbers) // 2
left_half = merge_sort(numbers[:mid])
right_half = merge_sort(numbers[mid:])
return merge(left_half, right_half)
def merge(left, right):
sorted_list = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_list.append(left[i])
i += 1
else:
sorted_list.append(right[j])
j += 1
# 남은 요소 추가
sorted_list.extend(left[i:])
sorted_list.extend(right[j:])
return sorted_list
def sort_numbers():
import sys
input = sys.stdin.read
data = input().split()
N = int(data[0])
numbers = list(map(int, data[1:N+1]))
# 병합 정렬을 사용하여 정렬
sorted_numbers = merge_sort(numbers)
# 결과 출력
for number in sorted_numbers:
print(number)
if __name__ == "__main__":
sort_numbers()코드 설명
merge_sort함수는 리스트를 반으로 나누어 각각 재귀적으로 정렬한 후,merge함수를 사용하여 두 정렬된 리스트를 합칩니다.merge함수는 두 개의 정렬된 리스트를 받아 하나의 정렬된 리스트로 합칩니다. 두 리스트를 하나씩 비교하며 더 작은 값을 결과 리스트에 추가합니다.sort_numbers함수는 입력을 받아 숫자들을 리스트로 변환한 후,merge_sort함수를 호출하여 정렬합니다.- 정렬된 숫자들을 차례대로 출력합니다.
예시 테스트
- 입력:
5 5 4 3 2 1 - 출력:
1 2 3 4 5
이 코드는 주어진 모든 조건을 만족하며, 각 입력에 대해 올바르게 동작합니다.
결론
이번 문제를 통해 병합 정렬 알고리즘을 복습할 수 있었습니다. 병합 정렬은 시간 복잡도가 (O(n \log n))으로 매우 효율적이어서 대량의 데이터를 정렬하는 데 적합합니다. 주어진 문제를 해결하면서 정렬 알고리즘의 기본 개념을 다시 한 번 정리할 수 있었습니다. 앞으로도 다양한 정렬 알고리즘을 공부하여 알고리즘에 대한 이해를 더욱 깊게 할 예정입니다.
1인개발자가 되겠다