문제 설명
이번에 공부한 문제는 N개의 수를 오름차순으로 정렬하는 프로그램을 작성하는 것이었습니다. 문제를 해결하기 위해 기본적인 정렬 알고리즘 중 하나인 버블 정렬을 사용해보았습니다.
문제 조건
- 수의 개수 N은 1 이상 1,000 이하입니다.
- 각 수는 절댓값이 1,000보다 작거나 같은 정수입니다.
- 수는 중복되지 않습니다.
입출력 예
| 입력 | 출력 |
|---|---|
| 5 | 1 |
| 5 | 2 |
| 2 | 3 |
| 3 | 4 |
| 4 | 5 |
| 1 |
문제 해결 방법
버블 정렬
이번 문제를 해결하기 위해 선택한 알고리즘은 버블 정렬입니다. 버블 정렬은 인접한 두 원소를 비교하고, 순서가 잘못된 경우 서로 교환하는 방식으로 동작합니다. 이 과정을 리스트가 정렬될 때까지 반복합니다.
시간 복잡도
버블 정렬의 최악, 최선, 평균 시간 복잡도는 모두 (O(n^2))입니다. 이는 중첩된 두 개의 루프가 리스트의 길이에 비례하여 실행되기 때문입니다.
공간 복잡도
버블 정렬은 주어진 리스트 내부에서 원소를 교환하므로 추가적인 공간이 거의 필요하지 않습니다. 따라서 공간 복잡도는 (O(1))입니다.
코드 구현
다음은 버블 정렬을 사용하여 문제를 해결하는 Python 코드입니다.
def bubble_sort(numbers):
n = len(numbers)
for i in range(n):
for j in range(0, n-i-1):
if numbers[j] > numbers[j+1]:
# Swap the elements
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
def sort_numbers():
import sys
input = sys.stdin.read
data = input().split()
N = int(data[0])
numbers = list(map(int, data[1:N+1]))
# 버블 정렬을 사용하여 정렬
bubble_sort(numbers)
# 결과 출력
for number in numbers:
print(number)
if __name__ == "__main__":
sort_numbers()코드 설명
bubble_sort함수는 리스트를 받아 버블 정렬 알고리즘을 사용하여 정렬합니다.- 리스트의 길이를
n으로 설정하고,i를 0부터n-1까지 반복합니다. - 내부 루프에서
j를 0부터n-i-2까지 반복하면서 인접한 두 원소를 비교하고, 순서가 잘못된 경우 교환합니다.
- 리스트의 길이를
sort_numbers함수는 입력을 받아 숫자들을 리스트로 변환한 후,bubble_sort함수를 호출하여 정렬합니다.- 정렬된 숫자들을 차례대로 출력합니다.
예시 테스트
- 입력:
5 5 2 3 4 1 - 출력:
1 2 3 4 5
이 코드는 주어진 모든 조건을 만족하며, 각 입력에 대해 올바르게 동작합니다.
결론
이번 문제를 통해 버블 정렬 알고리즘을 복습할 수 있었습니다. 버블 정렬은 간단한 정렬 알고리즘이지만, 리스트를 직접 정렬하는 과정을 이해하는 데 유용합니다. 버블 정렬의 시간 복잡도는 (O(n^2))로, 데이터가 많을 경우 비효율적일 수 있지만, 알고리즘의 기본 개념을 이해하는 데는 적합합니다. 또한, 공간 복잡도가 (O(1))로 추가적인 메모리 사용이 거의 없다는 점에서 장점이 있습니다. 주어진 문제를 해결하면서 정렬 알고리즘의 기본 개념을 다시 한 번 정리할 수 있었습니다. 앞으로 더 복잡한 정렬 알고리즘도 공부해볼 예정입니다.
