파이썬은 경쟁 프로그래밍(알고리즘 대회) 분야에서 개발자들이 가장 선호하는 언어 중 하나입니다. 문법이 간결하고 생산성이 높아 대부분의 문제를 합리적인 시간 안에 해결할 수 있기 때문입니다.
하지만 일부 복잡한 문제에서는 '충분히 빠른' 파이썬 코드를 작성하는 것이 쉽지 않습니다. 제한 시간 안에 통과하기 위해서는 언어의 특성을 잘 이해하고 최적화된 코드를 작성해야 합니다. 아래에서 경쟁 코딩에서 실행 성능을 크게 개선할 수 있는 파이썬다운(Pythonic) 코드 작성 기법들을 소개합니다.
1. 문자열 연결은 join()으로
반복문 안에서 문자열을 += 연산자로 계속 붙이는 방식은 피해야 합니다. 문자열은 불변(immutable) 객체이기 때문에 매번 새로운 문자열 객체가 생성되어 상당한 시간 오버헤드가 발생합니다.
str1 = ""
some_list = ["Welcome ", "To ", "Tutorialspoint "]
for x in some_list:
str1 += x
print(str1)대신 join() 메서드를 사용하세요. 리스트의 모든 요소를 한 번에 효율적으로 하나의 문자열로 합칩니다.
str1 = "" some_list = ["Welcome ", "To ", "Tutorialspoint "] print(str1.join(some_list))
2. map() 함수로 입력 처리하기
경쟁 코딩에서는 보통 한 줄에 여러 숫자가 공백으로 구분되어 입력됩니다. 예를 들면 다음과 같습니다.
1234567
이런 입력을 숫자 리스트로 변환하려면 map()과 split()을 조합하는 것이 가장 깔끔합니다.
list(map(int, input().split()))
입력 형식과 관계없이 항상 input()으로 문자열을 받은 뒤, map()으로 원하는 타입으로 변환하는 습관을 들이세요.
>>> list(map(int, input("enter numbers:").split()))
enter numbers:1 2 3 4 5 6 7
[1, 2, 3, 4, 5, 6, 7]map() 함수는 파이썬의 가장 강력한 내장 함수 중 하나로, 다양한 상황에서 유용하게 활용되므로 반드시 익혀두는 것이 좋습니다.
3. set과 리스트 병합 테크닉
리스트에서 중복을 제거해야 할 때가 자주 있습니다. Java 같은 다른 언어에서는 HashMap 등 복잡한 자료구조를 사용해야 하지만, 파이썬에서는 set 하나면 충분합니다.
>>> print(list(set([1,2,3,4,3,4,5,6]))) [1, 2, 3, 4, 5, 6]
또한 두 개 이상의 리스트를 합칠 때는 extend()와 append()의 차이를 정확히 알아야 합니다. 두 메서드의 동작 결과는 완전히 다릅니다.
>>> a = [1, 2, 3, 4] # 리스트 1 >>> b = [5, 6, 7] # 리스트 2 >>> a.extend(b) # 요소가 펼쳐져 하나의 리스트로 합쳐짐 >>> a [1, 2, 3, 4, 5, 6, 7] >>> a.append(b) # 리스트 자체가 요소로 들어감 >>> a [1, 2, 3, 4, [5, 6, 7]]
4. 코드는 함수 안에 작성하기
파이썬은 절차적(procedural) 코드도 지원하지만, 경쟁 코딩에서는 코드를 함수 내부에 작성하는 것이 더 빠릅니다.
def main():
for i in range(2**3):
print(x)
main()위 코드가 아래처럼 최상위 레벨에 바로 작성된 코드보다 성능 면에서 유리합니다.
for x in range(2**3):
print(x)그 이유는 CPython의 구현 특성 때문입니다. 지역 변수(local variable)는 배열 기반으로 빠르게 접근할 수 있는 반면, 전역 변수(global variable)는 딕셔너리 조회를 거치기 때문에 접근 속도가 느립니다.
5. 표준 라이브러리와 내장 함수 적극 활용
내장 함수와 표준 라이브러리는 C 레벨에서 구현되어 있어 직접 작성한 파이썬 반복문보다 훨씬 빠릅니다. 예를 들어 아래 코드 대신,
newlist = []
for x in somelist:
newlist.append(myfunc(x))map()을 사용한 한 줄로 대체할 수 있습니다.
newlist = list(map(myfunc, somelist))
특히 itertools 모듈은 반복 작업을 매우 빠르게 처리해 주므로 적극적으로 활용하세요. 예를 들어 순열(permutation) 생성도 몇 줄이면 끝납니다.
>>> import itertools
>>> iter = itertools.permutations(["a","b","c"])
>>> list(iter)
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]6. 제너레이터(Generator)로 메모리 절약
제너레이터는 코드의 메모리 사용량과 평균 시간 복잡도를 동시에 줄여주는 훌륭한 구조입니다. 값을 미리 만들어 저장하지 않고 필요할 때마다 하나씩 생성(yield)하기 때문에, 무한 수열이나 대량의 데이터를 다룰 때 특히 효과적입니다.
def fib():
a, b = 0, 1
while 1:
yield a
a, b = b, a+b위 피보나치 제너레이터처럼 yield를 사용하면 전체 수열을 메모리에 저장하지 않고도 필요한 값만 순서대로 얻을 수 있습니다.
이 여섯 가지 테크닉만 익혀도 경쟁 프로그래밍에서 파이썬 코드의 실행 속도와 메모리 효율을 눈에 띄게 개선할 수 있습니다. 작은 습관의 차이가 시간 초과(TLE)와 통과의 갈림길을 결정짓는 만큼, 평소 연습부터 최적화된 코드를 작성하는 습관을 길러보세요.