코딩테스트 채점 시스템의 시간 제한, 메모리 제한

보통 다음과 같다.

시간 제한: 1초 메모리 제한: 128MB

파이썬은 C/C++에 비해 동작속도가 느리지만, 파이썬 3.7로 코드를 작성할 때 자신의 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적이다.

시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다.

NLog2N = 20,000,000 when N = 1,000,000

파이썬의 속도가 C/C++에 비해서 느리지만 매우 큰 수의 연산을 기본적으로 지원하기 때문에 코딩이 간편하고, 만약 코딩테스트에서 Pypy3 **지원한다면 코드에 따라서는 속도가 C/C++에 견줄만큼 빠르게 연산을 수행할 수 있다. 삼성전자 공채에서는 코딩 테스트 채점에 **Pypy3을 이용하고, 지원자가 파이썬3으로 코드를 제출하면 Pypy3으로 채점한다고 한다.

시간 제한을 맞추기 위해 신경써야하는 예를 들자면 완전탐색(Brute Forcing)유형 문제이다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다. 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터가 큰 경우에 대해서는 적절하지 않고, 일반적으로 알고리즘 문제를 풀 때 확인(탐색)해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색 알고리즘을 사용하면 적절하다.

이것이 취업을 위한 코딩 테스트다 with 파이썬

                                            저자
                                            나동빈
                                            출판
                                            한빛미디어
                                            발매
                                            2020.08.05.