코딩 테스트를 위한 파이썬 배경 지식

본 포스팅은 백준 Online Judge의 자주 틀리는 요인을 바탕으로 작성한 글입니다. 하지만 백준에만 종속되지 않은 내용이 대부분이니 코딩 테스트를 위해 파이썬을 선택했다면 도움이 될 것입니다.

파이썬은 문법이 직관적이지만, 다른 언어들에 비해 성능은 좋은 편이 아니다. 따라서 극도로 효율적이어야 하는 프로그램을 만들어야 하거나, 시간 제한이 아주 엄격한 코딩 테스트에는 적합하지 않다. 만약 코딩 테스트를 위해 파이썬을 선택했다면 아마 풍부한 자료와 쉬운 난이도 때문일 것이다.

필자가 파이썬을 선택한 이유는 다음과 같다.

• 파이썬에 익숙하고, 코딩 테스트 관련 자료가 많다.
• 파이썬은 쉽고 직관적이다. 부수적인 코드 없이 코딩 테스트에서 요구하는 풀이만 코드로 작성할 수 있어서 명확하다.
• JavaScript를 가장 많이 사용하지만 JavaScript는 내장 자료 구조가 부실하여 코딩 테스트에 적합하지 않다.

어떤 이유로 파이썬을 선택했건, 코딩 테스트를 위해서 필수로 알아야 하거나, 알아두면 좋을 만한 배경 지식들이 있다. 본 포스팅에서는 파이썬으로 코딩 테스트를 보거나 연습할 때 도움이 될 만한 다양한 배경 지식들을 다룬다.

파이썬은 느리다

앞서 말한 것처럼 파이썬은 느린 언어다. 따라서 제대로 된 풀이더라도 시간 제한을 지키지 못할 수 있다. 이런 경우, 코딩 테스트 환경에서 Pypy 런타임을 제공한다면 Pypy로 런타임 환경을 바꾸어 제출해보고 그래도 안 된다면 다른 언어를 사용하자.

다음은 Pypy로 제출하는 경우 알아두어야 할 내용이다.

• Pypy는 파이썬과 정해진 재귀 깊이 제한이 없다. Pypy 1.4.1 release 문서에 따르면, 순수하게 내장 Stackoverflow 감지 메커니즘에 의존한다고 한다. 하지만 Differences between PyPy and CPython 문서에 따르면 근사적으로 스택 영역 크기를 설정하여 재귀 깊이를 조정할 수 있다고 한다. 정확한 정보를 찾을 수는 없었지만, Pypy 공식 문서에서 sys.setrecursionlimit 관련 이슈가 몇 번 정도 있었던 것으로 보아 재귀 깊이를 설정할 수는 있는 것 같다.

하지만 Pypy는 재귀에 극도로 약하다. 재귀 깊이가 10만 단위 이상으로 너무 깊어지면 Stackoverflow가 발생하고, 그 제한은 파이썬보다 낮다. 또한 sys.setrecursionlimit에서 설정해 놓은 재귀 깊이가 클 수록 메모리 사용량도 크다. 잘 참고해서 사용하자.

• 백준, Codeforces에서는 print가 sys.stdout.write보다 메모리 사용량이 높다. 예를 들어 print를 많이 사용할 수록 메모리도 많이 사용됩니다.
• 파이썬은 기본적으로 Big Integer를 지원하기 때문에 별도의 코드 없이 큰 수의 연산도 할 수 있지만 연산 속도가 느리다.

파이썬의 재귀 깊이

파이썬의 재귀 깊이는 기본적으로 최대 1,000으로 설정되어 있다. 하지만 sys.setrecursionlimit 함수로 재귀 깊이를 조절할 수 있다. 대부분 재귀를 이용한 풀이에서는 재귀 설정이 거의 필수다. 일반적으로 10 ** 6 정도로 설정하는 듯하다.

숫자 자료형

• 두 정수를 입력하여 비교할 때는 반드시 정수형(int)으로 변환한다.
• 부동 소수점을 잘 알고 사용하자.
  • 부동 소수점의 연산은 정수 연산보다 연산 속도가 느리다.
  • 두 정수의 나누기 몫을 구할 때에는 int(a / b) 가 아니라 a // b 를 사용하는 것이 안전하다.
  컴퓨터 과학 전반적으로 주목 받는 주제인 부동 소수점은 동작 방식을 잘 알고 사용해야 한다. 부동 소수점은 표현할 수 있는 수의 범위가 넓지만 그 범위 내의 모든 수를 정확하게 표현할 수는 없다. a / b 연산은 부동 소수점을 만들어내므로 안정성의 차이가 존재한다.
  • 항상 부동 소수점의 오차를 조심한다. 아래 기재한 항목은 특히나 위험하다.
    • 절대값이 아주 작은 수의 나눗셈
    • 값이 거의 비슷한 두 수의 비교
    • 정수에 아주 가까운 수를 정수로 형 변환하기

빠른 입출력

• input 보다는 sys.stdin.readline 을 사용하자. 내장 함수 input 은 prompt에 출력할 prompt message를 인자로 받고, 입력 이전에 prompt 메시지를 출력한다. 또, 입력 값 반환 이전에 개행을 제거하여 추가적인 과정이 있다. 반면 sys.stdin.readline 은 prompt message를 받거나 출력하는 과정이 없고, 개행 문자를 포함하여 입력 값을 문자형 그대로 반환한다. 따라서 일반적인 상황에서는 sys.stdin.readline 함수가 훨씬 더 빠르다. 코드 첫 부분에 input = sys.stdin.readline 을 작성하면 더 편하게 사용할 수 있다.
• sys.stdin.readline 사용 시 개행을 제거하지 않아도 되는 경우가 있다. 보통 개행 문제를 제거하기 위해 rstrip 메서드를 사용한다. 하지만 개행 문자가 맨 끝에 들어와도 숫자 변환이나 split 메서드를 그대로 사용할 수 있다. 즉, int(sys.stdin.readline()), sys.stdin.readline().split() 와 같은 형태도 전혀 문제 없다. 따라서 문자열을 그대로 저장하고 싶은 경우에만 개행 문자를 제거하면 된다.
• 백준의 빠른 A+B 문제를 참고하자.

내장 모듈

• 대부분의 코딩 테스트 환경에서는 외장 모듈을 지원하지 않는다. 지원하는 모듈을 잘 확인하자.
• 내장 함수, 자료 구조의 시공간 복잡도를 미리 숙지한다.
  • 참고: Python 공식문서, TimeComplexity
• 내장 정렬 함수를 사용하자.
  • 정렬 함수를 만들어서 사용하는 것은 시간도 많이 소모되고, 내장 정렬 함수보다 불완전할 가능성이 높다. 또 내장 정렬 함수는 최악의 경우에도 O(nlogn) 수행 시간을 보장하므로 효율성도 보장되어 있다.
  • list.sort 는 원본 리스트를 수정하는 파괴적 정렬 함수이다. sorted 내장 함수는 모든 iterable에 사용할 수 있고, 정렬된 새로운 객체를 반환하는 비파괴적 정렬 함수이다. 따라서 그만큼 연산 수행 시간도 느리다. 상황에 따라 두 가지 정렬 함수 중 하나를 선택하여 사용한다.
• list는 배열 리스트이다.
  • list.append 는 Table Doubling 기법으로 구현되어 O(1)에 수행된다.
  • list.pop(idx) , list.insert , del list[idx] 는 배열의 재배치가 수행되므로 O(n)에 수행된다.
  • min(list), max(list), x in list, list.count, list.index 는 배열의 순회가 수행되므로 O(n)에 수행된다.
  • list.extends 는 기존 list(L)에 확장할 list(M)의 원소를 순회하여 append하므로 O(|M|)에 수행된다.
  • list 합 연산은 두 리스트의 원소를 각각 모두 순회하며 새로운 리스트에 추가하므로 O(|L| + |M|)에 수행된
  • Slicing은 범위 내(i:j)의 리스트를 순회하여 수행되므로 O(j - i + 1)에 수행된다.
  💡 위의 이유로, **list를 큐 또는 덱으로 사용하면 절대, 절대, 절대, 절대, 절대 안 됩니다!! 반드시 `collections.deque`를 써야 합니다. *** 중요성을 강조하기 위해 백준 Online Judge의 자주 틀리는 요인 내용을 그대로 인용한다.
• 스택, 큐 자료 구조 파이썬의 내장 모듈 queue.Queue는 멀티 스레딩을 위해 만들어진 큐이고, 속도 또한 매우 느리다. 따라서 스택이나 큐 자료구조를 사용해야 한다면, collections.deque를 사용해야 한다.
• 힙 자료 구조 queue.Queue와 마찬가지로 queue.PriorityQueue는 멀티 스레딩을 위해 만들어진 heapq 기반 우선 순위 큐이므로, 속도가 느리다. 힙 자료구조가 필요하다면 heapq 모듈을 사용한다.
• dict은 해시 테이블이다. 따라서 대부분의 연산이 O(1)에 수행된다.
• set보다는 dict을 사용하자.
  • set은 연산 수행 시간이 천차만별이다.
  • x in set 연산은 평균적으로 O(1)에 수행되지만, 최악의 경우 모든 요소를 순회하여 O(n)에 수행된다.
  • set1 | set2 연산은 O(|set1| + |set2|)에 수행된다.
  • set1 & set2 연산은 O(min(|set1|, |set2|))에 수행된다.
  • set1 - set2 연산은 O(|set1|)에 수행된다.