오늘의 알고리즘(4월 15일)

1. 백준, 수 정렬하기, 2750번 

 

www.acmicpc.net/problem/2750

2750번: 수 정렬하기

---

2. 생각해보자. 

• 첫번째 입력 N은 입력될 숫자의 개수다.
• 첫번째 입력 N을 이용하여 N번의 for문을 통해 숫자를 입력 받는다. 
• N개의 숫자는 리스트에 저장한 후 정렬 함수(sort)를 이용하여 정렬한다. 

n = int(input())
numbers = []

for _ in range(n):
    numbers.append(int(input()))

numbers.sort()

for data in numbers:
    print(data)

 

 

- 맞긴 했는데 코드가 별로 안이쁜거 같다. 충분히 효율적일까? 

---

3. 해설 및 코드분석

• 이번 문제의 초점은 다양한 정렬 알고리즘을 구현하는 것이다. 
• 정렬 알고리즘에 따라 어떻게 구현될 수 있는지 확인해보자.

 

a) 선택정렬 알고리즘

• 선택정렬 알고리즘은 입력을 받을 때마다, 가장 작거나 큰 원소를 찾아 맨 앞쪽으로 정렬하는 방식이다.

n = int(input())
array = list()

for _ in range(n):
    array.append(int(input()))

for i in range(n):
    min_index = i #가장 작은 원소의 인덱스
    for j in range(i + 1, n):
        if array[min_index] > array[j]:
            min_index = j

    array[i], array[min_index] = array[min_index], array[i] #스와프

for i in array:
    print(i)

 

b) 파이썬의 기본 정렬 라이브러리를 이용한 풀이

• 내가 작성한 코드와 동일하다. 
• 선택 정렬의 정렬과정 부분(이중 for문이 사용된 부분)이 sort() 함수로 대체된 것이다.