Python은 알고리즘 문제를 해결 하는데에 강력한 언어 입니다. 하지만, Python으로 문제를 해결 하는 데에 익숙치 않다면, 많은 시행착오를 겪게 됩니다. 우리가 대부분 원래 사용 했던 C++은 컴파일 언어 입니다. 하지만, Python은 스크립트 언어이다 보니, 여러 가지 컴파일 에러를 겪을 수 있고, 타입리스 언어기 때문에, 타입 체킹이 제대로 되지 않아, 어려움을 겪을 수도 있습니다. 하지만, 우리는 이러한 타입리스 언어, 스크립트 언어의 장점을 잘 이용해야 합니다. 타입리스 언어이자 스크립트 언어이기 때문에, 빠르게 무언가를 구현 할 수 있도록 우리에게 제공된 구현체들을 잘 이용하여야 합니다. 이제 시작하겠습니다.
RuntimeError: maximum recursion depth exceeded 에러가 발생합니다.Python에는 함수 호출 스택이라는 것이 존재합니다. A 라는 함수에서 B 라는 함수를 호출하면, B 함수가 종료 될 때 까지 A 함수를 종료 하지 않는 것이죠. 아마 백트래킹 문제, 브루트 포스 문제를 해결하는 중이라면, 재귀 함수를 사용 하고 있을 가능성이 높습니다. 그럼 아마 높은 확률로 두 가지 경우의 수로 해결이 가능합니다.
이런 경우에는 print() 함수를 이용하여, 재귀 함수가 어떻게 돌아가는지 확인 하고, 일차적으로 문제의 접근 방법이 잘못 되었는지 체크 해 봐야 합니다.
기본적으로 Python 에서 재귀 함수가 무한정 실행 되었을 때 문제가 발생 할 것을 대비하여, 최대 재귀 호출 횟수를 1000회로 제한 했습니다. 사용자가 임의적으로 최대 재귀 호출 횟수를 늘리고 싶다면 sys 모듈의 setrecursionlimit() 함수를 이용하여 조정 할 수 있습니다.
import sys
sys.setrecursionlimit(10**6) # 10^6 만큼 최대 재귀 호출 횟수 늘림그래도 안된다면... 1번으로 돌아가고, 그래도 안되면 다른 방법 찾는게 정신 건강에 좋습니다.
list를 정렬 하고 싶어요!list.sort() 의 key 파라미터로 lambda 함수를 넘겨 주어, element의 정렬 조건을 설정 할 수 있습니다. lambda로 구현이 힘들다면 함수를 구현하고, key 파라미터로 functools.cmp_to_key(함수명)을 넘겨주면 됩니다. 내림차순 정렬을 원하면, reverse 파라미터로 True를 넘겨 주면 됩니다.
from functools import cmp_to_key # cmp_to_key가 필요한 경우 import
arr = [(1, 2), (2, 3), (1, 3), (2, 4), (3, 4)]
arr.sort(key=lambda x: x[1], reverse=True) # 튜플 1번째 값으로 정렬
print(arr)
def func(x, y): # 튜플 1번째 값으로 정렬
if x[1] != y[1]: # 만약 1번째 값이 같다면, 0번째 값 내림차순으로 정렬
return x[1] - y[1]
else:
return y[0] - x[0]
arr.sort(key=cmp_to_key(func))
print(arr)여담으로 알려드리자면, sort()의 알고리즘은 Tim Sort 를 사용하며, 시간 복잡도는 O(n log n) 입니다.
dict의 시간 복잡도dict는 해시 테이블을 사용 하는 자료 구조이기 때문에, 시간 복잡도가 매우 작습니다. 삽입, 삭제 등의 평균 시간 복잡도가 O(1) 입니다. 하지만, 데이터의 용량이 비대하게 클 경우에는 해시 테이블의 수행 속도가 급격히 낮아지고, 공간 복잡도 또한 안 좋아 지기 때문에, 신중하게 사용해 주세요.
collections 모듈은 당신의 손목과 손가락을 보호해 줄 좋은 친구 입니다. Python 기본 라이브러리 이기 때문에, 속도 또한 검증 되었습니다. 구현 상의 편안함을 위한 친구이니, 굳이 찾아 보지 않아도 됩니다. 하지만, 뜨거운 프로그래머들에겐 그딴거 필요없습니다. (deque는 필요 합니다... 하하...)
Python으로 문제를 푸는게 속도가 느릴 수 있다고 생각 할 수 있지만, 대부분의 대회에서는 Python 같은 경우 프로그램 실행 시간 제한을 조금 늘려 주는 경우도 많고, 일단, 구현체를 구현 함에 있어서 코드의 가독성 이 높기 때문에, 디버깅 및 논리적 오류를 발견 하는데에 강력합니다. 알고리즘 문제를 해결 하는데에 파이썬... 한 뚝배기 어떻습니까...?