알고리즘 스터디 3주차
백준의 단계별 풀어보기에서 정렬해보기 를 풀어보았습니다.
2750 수 정렬하기
def problem_2750(input_num):
input_list = []
for i in range(int(input_num)):
input_list.append(int(input()))
input_list.sort()
for i in range(int(input_num)):
print(input_list[i])
my_num = input()
problem_2750(my_num)
간단한 정렬문제인데, 파이썬에서는 더 간단하게 sort 함수를 제공하고 있습니다.
문제는 이 sort 함수의 성능인데,
파이썬의 sort 함수는 timsort 라는 알고리즘으로 구성되었다고 합니다.
timsort는 worst 인 경우 시간복잡도가 O(n log(n)) 으로 상당히 빠른 알고리즘입니다.
timsort에 관한 자세한 설명은 링크 를 참고하시기 바랍니다.
sort 의 성능만 고려하면 되는 간단한 문제인 줄 알았는데, 112ms 로 채점시간이 꽤 걸렸습니다.
sort 이외에 시간이 걸릴만한 부분은 입출력시 사용한 for loop 였습니다.
파이썬의 입력 방법은 input() 도 있지만 sys.stdin.read() 등의 함수도 있습니다.
두 방법이 완전히 동일한 기능을 하는것은 아니지만, 문제에서는 input() 을 sys.stdin.read()로 대체해도 큰 문제가 없었습니다.
그에 비해 성능차이는 약 50ms 정도로 꽤 많은 차이를 보였습니다.
참고로 두 방법의 차이는 여기에 잘 나와있으니 읽어보시면 좋을 것 같습니다.
그리고 마지막에 print 를 하는 부분에서 for 문 대신에 * 를 사용해 주었습니다.
짧은 리스트를 print 하는 것이기 때문에 성능면에서 큰 차이는 없으나, 긴 리스트를 print 하는 경우에는 * 를 사용하는 것이 더 나은 성능을 보였습니다.
그렇게 해서 최종적으로 수정한 코드는 아래와 같습니다. 72ms 로 50ms 의 시간을 줄일 수 있었습니다.
import sys
def problem_2750(input_num):
input_list = []
for i in range(int(input_num)):
input_list.append(int(sys.stdin.readline()))
input_list.sort()
print(*input_list, sep='\n')
my_num = input()
problem_2750(my_num)
2108 통계학
from collections import Counter
import sys
def problem_2108(input_num):
input_num = int(input_num)
input_list = []
for i in range(input_num):
input_list.append(int(sys.stdin.readline()))
sorted_list = sorted(input_list)
avg = round(sum(sorted_list)/input_num)
med = sorted_list[input_num//2]
rang = sorted_list[-1] - sorted_list[0]
cnt = Counter(sorted_list)
d = dict([(value, []) for value in cnt.values()])
for key, value in cnt.items():
d[value].append(key)
if len(d[max(d.keys())]) > 1:
most = sorted(d[max(d.keys())])[1]
else:
most = d[max(d.keys())][0]
print(avg,med,most,rang, sep='\n')
my_num = input()
problem_2108(my_num)
평균, 중앙값, 최빈값, 범위를 구하는 문제입니다.sort 함수를 이용하면 해결이 가능한 문제입니다.
파이썬에서 내장함수로 소팅을 하는 방법은 두 가지가 있는데, 둘의 알고리즘은 동일하나 사용법이 조금 다릅니다.
my_list = [b,a,c,e,d] my_list.sort() my_list >> [a,b,c,d,e] #list.sort() 는 list 의 원소 자체를 소팅한 결과로 변경하는데, sorted(my_list) my_list >> [b,a,c,e,d] sorted_list = sorted(my_list) sorted_list >> [a,b,c,d,e] #sorted(list) 는 소팅한 결과를 반영하려면 다른 변수를 사용해야 합니다.