Python으로 Problem Solving 하기

제 모국어는 Python입니다.

 

0. 서론

PS를 한다면 KOI든 ICPC든, 그 외 다른 어떤 대회들이든 Python이 그렇게 권장되는 언어는 아닙니다. 당장(지금은 어떤지 모르겠지만 제가 KOI를 했을 때 기준으로)KOI는 Python을 아예 지원하지 않았고, ICPC도 올해 리저널에서야 처음으로 파이썬을 지원하기 시작했습니다. 그리고 그 모든 것을 뛰어넘는 결정적인 이유로는 Python이 C++에 비해 상당히 느리다는 점이겠네요. 아무리 최적화를 열심히 하고, Pypy를 쓴다고 한들, C++로 대강 짠 코드가 훨씬 더 빠르고, Python 코드는 시간을 꽉 채워서 겨우 맞거나 시간 초과(TLE)를 보는 경험은 Python으로 어느 정도 PS를 해보신 경험이 있으신 분들이라면 다들 있으실 겁니다.

 

이쯤에서 제 이야기를 해볼까요. 저는 고등학교 1학년 때 처음으로 프로그래밍을 배웠습니다. 당시엔 무려 Python 3도 아니고 2.7 기준으로 배웠었네요... 여하튼, 자연스레 제가 처음 배운 언어는 Python이 되었고 머릿속에서 코드를 만들어나가는 방식도 약간 그에 맞춰서 만들어졌습니다. 다익스트라 선생님께서 프로그래머가 자바로 처음 배우면 돌이킬 수 없이 뇌가 망가진다? 뭐 그런 말을 했다고 하던데, 그게 맞다면 제 뇌는 아주 망가지다 못해 잿더미가 됐겠네요... 프로그래밍 하기엔 글렀나,,

 

여하튼, 제가 PS를 처음으로(제대로)입문한 것은 고등학교 3학년 때였습니다. KOI의 존재도 그때쯤 처음으로 인지했고, 신청할 수 있었기에 자연스럽게 참가하게 됐습니다. 당시에는 지역 예선과 본선이 있었는데, 지역 예선은 C++ 코드 기준으로 출제된다고 하더라고요. 그래서 시험 전날에야 C++ 문법을 처음 공부하기 시작했습니다. 컴퓨터로 코드를 짜보기는커녕 그냥 아 이런식으로 연산되는구나 아 이건 파이썬이랑 비슷하구나...이런 느낌으로 공부했네요. 예선은 지필고사였기 때문에 코드 해독은 깔끔하게 해결해서 당시 지역 1등으로 대상을 수상했습니다.

 

그렇지만 문제는 결국 본선이겠죠. 지금은 어떤지 모르겠으나 당시에는 실기 시험에서 Python을 사용할 수 없었습니다. 자연히 어떻게든 C++로 코드를 짜려고 노력은 했지만, 한 1주일 가지고는 턱도 없더라고요. 결국 저는 1시간만에 1번을 100점 받고, 2번 로직이 다 나왔음에도 불구하고 구현조차 하지 못했습니다. 덧붙여서, 부분 점수도 C++에서의 문자열 비교를 어떻게 하는지 몰라서 전혀 긁지 못했고, 전국 동상이라는 미묘한 성적으로 제 짧은 KOI 경력은 끝났습니다.

 

그렇지만 이후로도 버릇 못 고치고 저는 계속해서 Python만을 고집했습니다. 그렇게 해서, 지금 BOJ에서 푼 문제들도 대부분 Python으로 풀었고, 언어별 랭킹은 Python2가 지원 중지되면서(고등학교 때 푼 문제들은 거진 Python 2입니다.)막 높지는 않지만, Python 2 랭킹을 들어가보면 제가 당당히 2등을 차지하고 있는 걸 볼 수 있습니다.

더는 바뀔 일 없는 랭킹이네요 ㅋㅋ...

 

잡설이 길었네요. 이번 포스팅에선 제가 오랜 기간동안 Python으로 PS를 하면서 느꼈던 점들과 소소한 팁들을 공유 드리도록 하겠습니다.

 

1. Python으로 PS할 때 꼭 주의해야 할 점들

여러 가지 주의할 점들이 많이 있는데, 대표적인 것들을 꼽아 보자면 다음과 같습니다.

 

-input()이 생각보다 많이 느려서, 입력 받는 줄이 몇천개 이상만 되어도 sys.stdin.readline()으로 읽어주는 걸 권장합니다. Python으로 PS를 입문한 수많은 분들이, 쉬운 문제들에서 시간 초과를 받는 주요 원인 중 하나입니다.

(저는 입력 큰 문제는 항상 코드 첫줄에 import sys;input=sys.stdin.readline()을 적고 시작합니다.)

-다만 sys.stdin.readline()은 input()과는 다르게 줄바꿈문자도 같이 입력받습니다. int(input())과 같은 상황이거나 split()을 한다면 어차피 상관 없겠지만, 그렇지 않은 경우(주로 문자열을 받는 경우)에서는 input().strip()으로 꼭 뒤에 오는 줄바꿈문자를 처리해줍시다.

-한 줄에 들어있는 여러 정수를 받아서 한번에 list로 만들려 한다면, list(map(int,input().split()))을 사용할 수 있습니다.

 

-마찬가지도 print() 또한 생각보다 느립니다. 출력을 정말 10만개씩 할 일이 생기신다면 sys.stdout.writelines()를 사용하시면 좋습니다. 다만 print()와는 달리, 기본적으로 끝에 줄바꿈문자 \n을 출력하지 않습니다.

 

-정수 나눗셈(//)에서 음수값이 나올 때, 버림을 C나 C++과는 다르게 0에 가까운 쪽이 아니라 작아지는 쪽으로 합니다. 예를 들어, -1//2는 0이 아니라 -1입니다.

-나머지를 구하는 연산도 제법 조심할 부분이 많은데, 나누는 수가 음수라면 음수 나머지가, 양수라면 양수 나머지가 나옵니다. 가령 3%-2는 -1이지만 -3%2는 1입니다.

 

-from queue import queue에서 나오는 queue는 많이 느립니다. queue나 stack이 필요하다면 가장 좋은 방법은 아무래도 from collections import deque를 통해 deque를 사용하는 것입니다.

 

-2차원 배열을 생성하려면 [[0]*M]*N과 같은 방식이 아닌, [[0]*M for i in range(N)]을 하셔야 합니다. 첫번째 방식대로 하면 배열 안에 들어있는 1차원 배열들이 모두 같은 메모리값을 참조하게 되어, 그 중 하나의 값만 바꿔도 다른 모든 것들의 값이 바뀝니다.

-비슷한 이유로, (특히 다차원)배열을복사할 일이 있다면 copy()만으론 부족합니다. copy.deepcopy()를 사용하셔야 합니다.

 

-현실에서 여러 수학 문제를 풀 때 numpy와 같은 유명한 모듈들은 큰 도움이 됩니다. 물론 적잖은 PS 문제들에 대해서도 해당되겠지만, 대부분의 저지 사이트와 거의 모든 대회에서는 외부 모듈을 사용할 수 없습니다. 다른 계기로 Python을 처음 사용하게 된 뒤로 PS를 하시게 되는 경우라면 은근히 주의하셔야 합니다.

 

-재귀를 사용하려고 한다면, sys.setrecursionlimit을 사용해서 최대 깊이를 조절할 수 있습니다. 기본값은 1000 언저리고(실제로 돌리면 920번 정도에서 멈추는 경우가 잦습니다.)이 한도를 넘어서면 당연히 에러가 납니다.

-재귀를 사용할 때 주의할 점이라면, 대부분의 경우 CPython보다 Pypy가 빠르지만, Pypy는 재귀에 약한 특징이 있습니다. 오히려 CPython으로는 간당간당하게 시간 안에 들어가는 코드가 Pypy로는 메모리 초과를 띄우는 경우도 가끔 있습니다.

 

-이 모든 것들을 고려했고, 시간복잡도까지 문제에서 요구하는대로 맞추었고 Pypy로 제출을 한다 하더라도, C++이라면 여유롭게 통과할 로직이 시간 초과가 나는 경우가 아주 많습니다. 특히 고난도 문제에서는 더더욱요. 이럴 때는 극한까지 최적화를 하거나, 그냥 포기하고 다른 언어로 짜시길 바랍니다.

-이와 같은 이유로, 2022년부터 Pypy3 옵션이 추가된 ICPC Seoul regional도 Pypy로 문제가 풀릴 수 있음은 보장하지 않는다는 단서를 달고 추가됐습니다. 

 

2. 그래서, Python으로 PS하면 뭔가 좋은 점이 있긴 한건가?

위의 설명들만 보면 Python은 이것저것 신경써줘야 할 부분들도 많고, 심지어 느려서 아예 풀 수 없는 문제들도 존재함을 알 수 있습니다. 그렇다면 Python은 정말로 PS에 장점이 아무 것도 없을까요? 저같이 이미 뇌가 Python에 완벽히 침식된 사람이 아니라면, 어서 C++로 갈아타는 게 좋을까요?

 

네, 갈아타세요. 저는 KOI할 때 그냥 C++로 갈아탔어야 했나하는 후회를 늘 하곤 합니다.

 

...농담이고, 특정한 경우에서는 Python이 강점을 가지고 있습니다.

 

-정수형의 범위 제한이 존재하지 않습니다. 오버플로우 걱정을 하지 않아도 되고, 입력받는 숫자가 지나치게 큰 경우에도 문제없이(시간은 조금 걸리겠지만)연산을 할 수 있습니다.

 

-Python이라는 언어 문법 특성상, 잘 작성한다면 다른 언어를 주로 사용하는 사람들도 편하게 읽을 수 있는 코드를 작성하기에 용이하고 쉬운 문제는 짧고 빠르게 짤 수 있습니다. 디버깅 또한 용이한 부분이 많습니다.

-비슷한 이유로, 까다로운 구현을 요하는 문제들을 비교적 빠르게 짤 수 있습니다. 특히 속도는 크게 중요하지 않고 구현이 메인인 문제라면,(물론 자신에게 익숙한 언어가 가장 좋겠지만)Python을 사용하는 것을 강력히 추천합니다. 이건 프로그래밍 언어로서 Python이 가지는 장점과도 이어지겠네요.

-많은 구현량을 요구하는 분야(기하 등)에서 어느 정도 구현량이나 속도에 우위를 점할 수 있습니다. 다만, 이런 문제들의 경우엔 시간 제한 또한 빡빡한 경우가 많고, 자칫하다간 구현 실수로 이어지기 쉽기 때문에 잘 알려진 C++의 구현체들을 익히는 것이 더 나은 선택지가 될 수 있습니다.

 

-문자열을 다루는 것이 C++에 비해서 상당히 간편합니다. 다만 당연히 C++보다 느리기 때문에 일정 수준 이상의 문제를 맞히기에는 조금 어려움이 있습니다.

 

-몇몇 내장 함수나 모듈은 문제 풀이에서 많은 도움이 됩니다. 간단하게는 pow와 같은 함수를 통해 ~를 998244353으로 나눈 나머지를 구하시오. 와 같은 문제에서 나오는 거듭제곱을 한결 편하게 처리할 수 있고, math.gcd처럼 구현을 해도 쉽지만 자칫 잘못하면 실수하기 쉬운 것들을 내장 함수로 사용할 수 있습니다.

-부동소수점 에러가 날 때 Decimal이나 Fraction 모듈을 통해 어느 정도 문제에서 벗어나실 수 있습니다. 다만, 시간 초과는 별개의 문제입니다.

-따라서, 수치해석과 관련된 문제를 풀 때에 큰 도움이 됩니다. numpy등을 사용할 수 없음에도 불구하고 말이죠.

 

-세그폴트니 변수 선언 시의 메모리 초과니 하는 문제에서 어느 정도 벗어나실 수 있습니다.

3. 그 외로는?

PS를 공부하면서 생겼던 소소한 문제로는, 문제가 도저히 풀리지 않아 다른 사람들의 알고리즘 포스팅 등을 참고할 일이 있더라도 대부분은 C++코드라서 Python에 그대로 적용하기에는 무리가 크다는 게 있습니다. 다만, 이건 오히려 저에게는 "글을 읽으면서 로직을 이해하고, 그 로직에 맞게 내 스타일대로 코드를 짜는" 연습을 하는 데에 큰 도움이 되었습니다. 어차피 코드를 그대로 베끼는 것은 치팅이기도 하고요. 공부할 때 다른 사람들이 구현한 것들을 바로 참고할 수 없는 것이 언제나 단점은 아니라 생각합니다. 

 

PS 커뮤니티와 같은 곳에서 도움을 곧바로 얻기 상대적으로 힘들다는 점 또한 언어 외적으로 힘든 부분이라 할 수 있겠네요. Python 사용으로 이름이 높은 분이라면 아무래도 jh05013 선배가 있고, 다른 몇몇 분들도 Python PS 경험이 제법 있으시지만, 아무래도 주 언어가 C++인 사람들의 비율이 월등히 높으니 디버깅 등 관련 과정에서 도움을 받기에 조금 힘든 구석이 있습니다.

4. 결론은?

혹시 이 글을 보고 PS를 Python으로 입문하시려 한다면, 지금이라도 늦지 않았으니 C++을 추천드립니다. 아무리 여러 부분에서 소소한 강점을 가지고 있다한들, 결국 PS를 하기에 가장 적합한 언어는 C++이라고 생각합니다.

 

다만, 그렇다고 해서 Python이 아주 무쓸모한 것은 전혀 아닙니다. 위에서 언급한 문제들을 잘 다루면서 사용한다면, 특정 상황에서 유용한 도구로 사용될 수 있습니다. 가령 극단적인 예시지만 큰 수 곱셈과 같은 문제는 C++로 풀려 한다면 FFT/NNT가 필수불가결하지만 Python이라면 한두줄 정도로 끝낼 수 있습니다. 언어가 문제를 풀기 위한 일종의 무기라고 생각하신다면, 한 가지 무기보다는 여러 무기를 적재적소에 사용하는 프로그래머가 더욱 숙련되었다고 할 수 있을 겁니다.(저는 못합니다.)

 

혹시 PS 문제를 Python으로 풀고 시간 초과 문제나 다른 디버깅에 어려움을 겪으시는 분이 계신다면 이 글이 조금이나마 도움이 될 수 있었으면 좋겠습니다. 위에 추가할만한 내용들이 있다면 댓글로 제안해주신다면 감사히 받겠습니다!