20040번 - 사이클 게임
안녕하세요, Python3 및 PyPy3 로 제출해보면서 풀 때, 저를 포함한 많은 분들이 이와 같은 에러를 겪지 않을까 싶어 남겨봅니다.
1. 런타임 에러
Union Find 를 구현할 때 재귀로 구현하다 보면, 런타임에러가 발생할 수 있습니다.
재귀로 인한 런타임 에러의 경우 코드 맨 윗줄에 아래와 같이 추가를 해주시면 됩니다.
import syssys.setrecursionlimit(10**6)
혹은 재귀함수를 while 문으로 변경하는 방법도 있습니다.
(참고: https://www.acmicpc.net/board/...)
while x != parent[x]: x = parent[x]
return x
2. 메모리 초과
PyPy3 로 제출시 메모리 초과, Python3 로 제출시 시간 초과가 나는 현상은 아래와 같이 Union Find 최적화 방법으로 해결할 수 있습니다. Union Find 최적화 방법은 (1) Path Compression (경로 압축) 과 (2) Union by Rank 가 있습니다.
(참고: https://algorithms.tutorialhor...)
(1) 경로압축은 find 함수에서 최상위 부모를 찾을 때마다, 부모를 이 때 찾은 최상위 부모로 업데이트하는 방식입니다. 이렇게 하면 나중에 동일한 값의 최상위 부모를 찾을 때, 시간이 엄청나게 절약됩니다.
def find(a): if parent[a] == a: return a parent[a] = find(parent[a]) return parent[a]
(2) Union by Rank 는 아래와 같이 구현할 수 있습니다. 항상 작은 값 기준으로 혹은 항상 큰 값 기준으로 합치도록 하면, 트리의 높이가 낮아져서 시간이 빨라지는 효과가 있습니다.
// Union 함수 내부
if parent[a] < parent[b]: parent[parent[a]] = parent[b] else: parent[parent[b]] = parent[a]
3. 시간 초과
시간초과가 나는 경우, 2번에서와 같이 (1), (2) 최적화 방법이 모두 적용되었는지 확인이 필요합니다. 그래도 시간 초과인 경우 input 함수로 입력을 받는게 시간이 오래 걸렸기 때문일 수 있습니다. 코드 맨 윗줄에 아래와 같이 추가하여 해결할 수 있습니다.
import sysinput = sys.stdin.readline
댓글을 작성하려면 로그인해야 합니다.
choko100 4년 전 11
안녕하세요, Python3 및 PyPy3 로 제출해보면서 풀 때, 저를 포함한 많은 분들이 이와 같은 에러를 겪지 않을까 싶어 남겨봅니다.
1. 런타임 에러
Union Find 를 구현할 때 재귀로 구현하다 보면, 런타임에러가 발생할 수 있습니다.
재귀로 인한 런타임 에러의 경우 코드 맨 윗줄에 아래와 같이 추가를 해주시면 됩니다.
import sys
sys.setrecursionlimit(10**6)
혹은 재귀함수를 while 문으로 변경하는 방법도 있습니다.
(참고: https://www.acmicpc.net/board/...)
while x != parent[x]:
x = parent[x]
return x
2. 메모리 초과
PyPy3 로 제출시 메모리 초과, Python3 로 제출시 시간 초과가 나는 현상은 아래와 같이 Union Find 최적화 방법으로 해결할 수 있습니다. Union Find 최적화 방법은 (1) Path Compression (경로 압축) 과 (2) Union by Rank 가 있습니다.
(참고: https://algorithms.tutorialhor...)
(1) 경로압축은 find 함수에서 최상위 부모를 찾을 때마다, 부모를 이 때 찾은 최상위 부모로 업데이트하는 방식입니다. 이렇게 하면 나중에 동일한 값의 최상위 부모를 찾을 때, 시간이 엄청나게 절약됩니다.
def find(a):
if parent[a] == a:
return a
parent[a] = find(parent[a])
return parent[a]
(2) Union by Rank 는 아래와 같이 구현할 수 있습니다. 항상 작은 값 기준으로 혹은 항상 큰 값 기준으로 합치도록 하면, 트리의 높이가 낮아져서 시간이 빨라지는 효과가 있습니다.
// Union 함수 내부
if parent[a] < parent[b]:
parent[parent[a]] = parent[b]
else:
parent[parent[b]] = parent[a]
3. 시간 초과
시간초과가 나는 경우, 2번에서와 같이 (1), (2) 최적화 방법이 모두 적용되었는지 확인이 필요합니다. 그래도 시간 초과인 경우 input 함수로 입력을 받는게 시간이 오래 걸렸기 때문일 수 있습니다. 코드 맨 윗줄에 아래와 같이 추가하여 해결할 수 있습니다.
import sys
input = sys.stdin.readline