✏️ 서론
2일 동안 배웠던 정렬 알고리즘을 토대로 교재와 백준에 있는 정렬문제를 풀어보았다.
하나씩 살펴보자.
✏️ 본론
⚡️ [ 문제1 ] 위에서 아래로
먼저, 교재에 있는 문제이다. 난이도가 높은 문제는 아니었다.
문제:크기에 상관없이 나열되어 있는 배열을 큰 수부터 작은 수의 순서로 정렬하시오.
큰 수부터 작은 수의 순서로 정렬하는데 수열을 내림차순으로 정렬하는 문제였지만 오름차순으로 풀었다.
기본적으로 sorted() 내장함수를 사용해서 푸는것이 시간복잡도가 훨씬 효율적이지만, 앞에서 배웠던 삽입 정렬, 선택 정렬, 퀵 정렬, 계수 정렬을 복습해보고 싶어 각각의 방식으로 풀어봤다.
그리고 알고리즘의 동작 시간이 궁금해 time 라이브러리를 호출했다.
작동시간은 컴퓨터 성능마다 차이가 있는 점을 유의하자.
코드의 간결함을 위해 입력은 하단에 적었다.
'''
3
15
27
12
'''# 1. sorted()
import sys
import time
n = int(input())
array = []
for i in range(n):
array.append(int(sys.stdin.readline().rstrip()))
start_time = time.time()
array = sorted(array)
end_time = time.time()
for i in array:
print(i, end=' ')
print()
print(f'동작시간 = {end_time - start_time}')
👉🏽 출력:
27 15 12
동작시간: 1.0013580322265625e-05# 2. 삽입 정렬
import sys
import time
n = int(input())
array = []
for i in range(n):
array.append(int(sys.stdin.readline().rstrip()))
start_time = time.time()
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
end_time = time.time()
print(array)
print(f'동작시간 = {end_time - start_time}')
👉🏽 출력:
27 15 12
동작시간: 1.4781951904296875e-05# 3. 선택 정렬
import sys
import time
n = int(input())
array = []
for i in range(n):
array.append(int(sys.stdin.readline().rstrip()))
start_time = time.time()
for i in range(len(array)):
min_index = i
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
end_time = time.time()
print(array)
print(f'동작시간 = {end_time - start_time}')
👉🏽 출력:
27 15 12
동작시간: 2.5987625122070312e-05# 4. 퀵 정렬
import sys
import time
n = int(input())
array = []
for i in range(n):
array.append(int(sys.stdin.readline().rstrip()))
start_time = time.time()
def quick_sort(array):
if len(array) <= 1:
return array
pivot = array[0]
tail = array[1:]
left = [x for x in tail if x <= pivot]
right = [x for x in tail if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
end_time = time.time()
print(quick_sort(array))
print(f'동작시간 = {end_time - start_time}')
👉🏽 출력:
27 15 12
동작시간: 3.0994415283203125e-06# 5. 계수 정렬
import sys
import time
n = int(input())
array = []
result = []
start_time = time.time()
for i in range(n):
array.append(int(sys.stdin.readline().rstrip()))
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] = count[array[i]] + 1
for i in range(len(count)):
for j in range(count[i]):
print(i, end=' ')
end_time = time.time()
print(f'동작시간 = {end_time - start_time}')
👉🏽 출력:
27 15 12
동작시간: 0.1468818187713623⚡️ [ 문제2 ] 성적이 낮은 순서로 학생 출력하기
마찬가지로 교재에 있는 문제였다.
문제:N명의 학생 정보가 있다. 학생 정보는 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.
동일하게 문제에서 학생 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나 O(N)을 보장하는 계수 정렬을 이용하면 된다.
학생정보는 (이름, 점수) 튜플로 구성되어있는데,
정렬은 점수순으로 나열해야하고, 출력은 이름순으로 나열하는 문제였다.
이럴때는 sorted(lambda) 함수를 사용하면 편하다.
(부록에서 나오는 개념만 알고있다 실제로 문제에 적용하니 정말 편리했다. python 쵝5!! 😎 😎)
score = sorted(array, key=lambda x: x[1])와 같이 람다 함수를 통해 key = lambda x: x[1]를 선언하면 튜플 값 중 x[1]: 점수순으로 정렬을 수행한다.
이때, default 값은 오름차순으로 정의되어있는데,
만약 내림차순으로 하고 싶으면 -x[1]을 사용하자.
자세한 내용은 파이썬 공식문서를 참고하자.
n = int(input())
array = []
for i in range(n):
input_data = input().split()
array.append((input_data[0], int(input_data[1])))
score = sorted(array, key=lambda x: x[1])
for array in score:
print(array[0])
👉🏽 입력
2
안영우 95
안영준 77
👉🏽 출력
안영준 안영우⚡️ [ 문제3 ] 두 배열의 원소교체
문제: N, K, 배열 A와 B의 정보가 주어졌을 때, 최대 K번 바꿔치기 연산을 수행하여 만들수 있는 배열 A의 모든 원소의 최댓값을 출력하는 프로그램을 작성하시오.
리스트 A는 오름차순으로, B는 내림차순으로 정렬하고 두 리스트를 비교해서 B의 큰값을 A로 변경하는 방법을 사용하면 된다.
핵심은 K번 동안만 for문을 돌리고 두 원소를 비교하는 if문을 작성하는것이다.
'''
5 3
1 2 5 4 3
5 5 6 6 5
'''
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a = sorted(a)
b = sorted(b, reverse=True)
for i in range(k):
if a[i] < b[i]:
a[i], b[i] = b[i], a[i]
else:
break
print(f'a = {a}')
print(f'b = {b}')
print(sum(a))
👉🏽 출력
a = [6, 6, 5, 4, 5]
b = [1, 2, 3, 5, 5]
26⚡️ 백준 알고리즘 문제들
이 외에도 백준 알고리즘 단계별 풀이 - 정렬파트 9 문제 중 8 문제를 풀었다.
나머지 한 문제는 머리가 식으면 풀려고 한다.
특히, 백준 8번과 9번은 2번 문제와 비슷한데
lambda 함수 문제를 더 풀어보고 싶으면 꼭 풀어보길 권장한다!!
그리고 입력의 범위가 최대 100,000 ~ 200,000까지 일 때,
문자열을 받는 입력이 있다면 input() 대신 적극sys.stdin.readline().rstrip().split()을 사용하자.
시간이 반으로 줄어든다.!
제일 상단은 sys.stdin.readline().rstrip().split()으로, 제일 하단은 input()으로 동일 코드 중 입력코드만 변경했다.
✏️ 결론
비록 교재에서 배울 알고리즘이 많이 남았지만, 천천히 알고리즘을 배우면서 문제를 풀 때 어떻게 문제에 접근해야하지? 같이 고민할 수 있다는게 너무 좋다.
내일은 이진탐색에 대해 배워보자..!
