글 읽기 - 파이썬 메모리초과... 선생님들 고견으로 구제 부탁드립니다.

wjdgh12392 2년 전 0

파이썬으로 돌리면 메모리초과가 자꾸 나옵니다... 혹시 몰라 pypy로 돌리면 되는경우도있다기에 pypy로 돌리려해봐도 제출언어에 python3밖에 없는데 pypy로는 어떻게 제출하는지도 알려주시면 감사하겠습니다.

from itertools import permutations

n = int(input())
cnt = 0
arr = list(permutations(list(range(n)),n))
new_arr = []

for i in arr:
    for  j in range(n-1,0,-1):
        if abs(int(i[j]) - int(i[j-1])) >= 2:
            cnt += 1
    if cnt >= n-1:
        new_arr.append(i)
    cnt = 0

f_cnt = len(new_arr)

for arr in new_arr:
    for i in range(len(arr)):
        for j in range(len(arr)-1,i,-1):
            if abs(arr[i] - arr[j]) == abs(i-j):
                cnt += 1
                break
    if cnt > 0:
        f_cnt -= 1
    cnt = 0    
print(f_cnt)

kdyfloat 2년 전 0

n = 14일때, arr의 크기는 14! x 14 x 4byte = 4,881,984,307,200 byte 입니다. 메모리 제한이 128 Mb이므로 매우 초과합니다.

순열을 임시로 생성하면서 순회하는 방식을 사용하면 좋을 것 같네요.

wjdgh12392 2년 전 0

kdyfloat 선생님, 조언 매우 감사드립니다.

선생님 말씀은 순열을 변수로 저장하지말고 생성되자마자 바로 if 조건으로 거른 후에 크기가 줄어든 내용을 변수로 저장하시라는 말씀 같은데, 변수 저정하지않고 for문이나 이중 for문을 쓰는 방법이 따로 있을까요? 리스트 컴프리헨션도 이중으로 쓰려니 답이 나오질 않습니다..

아쉽게도 제가 무지하여 다시 한번 질문 요청드리는 점 양해부탁드립니다. 감사합니다.

kdyfloat 2년 전 1

아래처럼 비트마스킹과 재귀로 순회 가능합니다.

하지만 이 방법을 사용하면 메모리는 초과하지 않겠지만, 모든 경우를 순회하는 방식은 그대로이므로,

14! 가지의 경우를 모두 탐색하면 14! x 14 x 14 시간이 필요하므로, 시간초과가 발생할 가능성이 있습니다.

http://boj.kr/5c68cb23298e4477... 의 코드처럼

대각선에 퀸이 놓여있는지 판정하는 배열을 만드는 방법이 좋을 것 같네요.

arr = list(range(n))
def func(selected, seq):
    if selected == (1<<n)-1:
        #seq = 순열.
        #검사.
        return
    for i in range(n):
        if (1<<i)&seleccted:
            continue
        seq.append(i)
        func(selected|(1<<i), seq)
        seq.pop()
f(0, [])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 메모리초과... 선생님들 고견으로 구제 부탁드립니다.

wjdgh12392 2년 전 0

kdyfloat 2년 전 0

wjdgh12392 2년 전 0

kdyfloat 선생님, 조언 매우 감사드립니다.

아쉽게도 제가 무지하여 다시 한번 질문 요청드리는 점 양해부탁드립니다. 감사합니다.

kdyfloat 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말