병합정렬로도 풀리지않는 문제 어떻게 풀까?
먼저 왜 풀리지 않는지를 알아야한다.
모든 문제의 해결은 그 문제가 무엇인지 정확히 판단하는것부터 시작이다.
시간 복잡도가 O(n LOgN)인 병합정렬로도 풀리지않는 문제 그 이유는 다음과 같다.
1. 파이썬을 사용했기 때문에
파이썬은 인터프리터 언어이다. 인터프리터 언어는 코드를 한줄 한줄 읽어들이면서 실한 한다. 그렇기 때문에 컴파일 언어와 비교했을때 상대적으로 느리다.
인터프리터 언어에는 Js, ruby, sql 등이 있다.
## 2.입출력 단계에서의 지연 input()과 print()는 사용하기 편한 입출력식 이지만 표준입출력식은 아니다. 그렇기 때문에 sys import를 통한 입출력보다는 속도가 저하된다.
파이썬대신 pypy3를 이용하여 해결
pypy란 파이썬의 언어 구현 중 하나로, 기존 인터프리터 방식의 단점을 보완하고자 armin rigo라는 사람이 Just-In-Time컴파일을 구현한 것이다. 즉 쉽게말하면 컴파일 파이썬 이라고도 할 수 있다.
백준이나 타 알고리즘 문제해결 사이트에서는 pypy3를 지원하고 있으므로(삼성sw테스트에도 사용가능) 그저 언어만 바꾸면 된다.
컴파일 언어의 구동 과정:
소스코드(님이 쓴 코드)를 기계어로 컴파일 - 실행파일을 만든다 - 실행한다.
쉽게말해서 코드를 통으로 기계어로 만들어서 실행하는것이다.
**jit컴파일(just - in - time) 이란 몰까?
jit컴파일이란 프로그램을 실행하는 시점에서 필요한 부분들을 컴파일 하는 방식이다.
이 방식을 사용하면 같은 함수가 여러번 불릴때 매번 기계어 코드를 생성하는것을 방지할 수 있다.
입출력 단계에서 속도 개선 시키기
input() 대신 sys.stdin.leadline()을 작성하면 입력단계에서 속도를 개선시킬수 있다.
import sys
a,b = map(int, sys.stdin.readline().split()) # 예제언뜻 보기에 input과 sys.stdin.leadline은 둘다 builtin function으로 동일해 보이지만 완벽하게 같지는 않다.
sys.stdin.leadline은 개행문자를 그대로 입력받는다.
하지만 input은 개행문자를 지워주는 역할까지 동시에 수행한다. 이것이 leadline이 input보다 나은 속도를 보여주는 원인이 될 수 있다.
- sys.stdin.leadline().strip()을 통해 개행문자를 지워줄 수 있지만 이 경우 그냥 input()을 사용하는게 더 나은 속도를 보인다고 한다.
또한 입력의 끝이 어떤식으로 표시되냐 하는것이다. 입력이 더 이상 없으면 input은 EOFE 오류를 발생시킨다. 반면 sys.stdin.readline은 EOF에서 빈 문자열을 반환하며, 이 문자열을 확인해야 한다.
자 그럼 저번시간에 못끝낸 2751을 해치워보자
n = int(input())
s= []
for _ in range(n):
s.append(int(input()))
s.sort()
for i in s:
print(i)파이썬 대신 pypy3로 제출 간드앗!!!
두근두근!!!!!
해치웠다!!
여기서 잠깐..
저번 포스팅에서 신나게 병합정렬 설명해놓고 정작 빌트인 sort써서 풀어버리기~?
ㅋㅋㅋㅋ 이건 너무한거 아니냐고~ 라고 할까봐 준비했다.
파이썬에 기본 내장되있는 sort함수 자체가 병합정렬의 일종인 팀정렬이다.
그럼 오늘은 여기까지...
