BOJ 1342 메모리초과 관련

세계 대회 진출자가 알려주는 코딩테스트 A to Z (with Python)

브루트 포스 알고리즘 [문제풀이] : BOJ 1342

해결된 질문

작성

from itertools import permutations

infos = list(input())

ans = 0

for comb in set(permutations(infos)):

ok = True

for i in range(0,len(infos)-1):

if comb[i] == comb[i+1] :

ok = False

break

ans += ok

print(ans)

BOJ 1342번 문제를 다음과 같이 풀었는데 계속해서 메모리초과 때문에 오답처리가 나서 질문 남깁니다.

permutations가 한 번에 모든 순열을 생성하기 때문에 메모리 문제가 발생한다고 GPT의 답변을 얻을 수 있었으나, 강사님의 풀이 1번에도 permutations가 있는데도 메모리초과가 나지 않고 정답처리가 나서 왜 이런 차이가 나는 지 궁금합니다.

python 코딩-테스트 알고리즘

답변 2

알리 Ally

지식공유자

안녕하세요, gjwns2044님!

메모리 초과가 나는 이유는 이 질문글(링크)을 참고해주시면 좋을 것 같습니다.

크기가 n인 리스트에 대해, permutations를 사용해도 어차피 n!만큼의 원소들을 담고 있는 객체를 생성하므로 메모리적인 측면에서 set으로 둘러싼 것과 큰 차이가 없지 않나요?

이에 대한 답은 no입니다. 파이썬의 permutations 함수는 모든 순열을 한꺼번에 저장하지 않고, 필요할 때마다 하나씩 생성하는 제너레이터(generator)입니다.

재너레이너(generator)란 한 번에 모든 데이터를 메모리에 저장하지 않고, 필요할 때마다 값을 생성해서 반환하는 함수 또는 객체입니다. 따라서, 이러한 방식을 이용하면 메모리를 효율적으로 사용할 수 있습니다.

아래와 같은 형식으로 permutations 객체를 생성하면, next 함수를 통해서 다음의 원소를 접근하여 메모리 효율적으로 모든 순열의 원소를 살펴볼 수 있는 것입니다. (이러한 permuations를 for문에 이용해도 이와 같이 메모리 효율적으로 돌아가게 됩니다.)

from itertools import permutations

data = [1, 2, 3]
perm_gen = permutations(data, 2)  # 제너레이터 객체 생성

print(next(perm_gen))  # (1, 2) → 첫 번째 순열을 생성
print(next(perm_gen))  # (1, 3) → 두 번째 순열을 생성
print(next(perm_gen))  # (2, 1) → 세 번째 순열을 생성

이러한 방식을 lazy evaluation(지연 평가)라고 하므로 참고하시면 좋을 것 같습니다.

질문에 대해 만족스러운 답변이 되었기를 바랍니다!

추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

gjwns2044님께서 언급하신 BOJ 1342번 문제를 파이썬의 itertools.permutations를 사용하여 푸시는 과정에서 메모리 초과가 발생하는 이유에 대해 설명드리겠습니다.

문제 원인

itertools.permutations는 입력된 리스트의 순열을 모두 생성하여 반환합니다. gjwns2044님의 코드에서는 이 모든 순열을 set으로 중복 제거 후 리스트로 변환해 메모리에 저장하려고 시도하고 있습니다. 문자열의 길이가 증가할수록 순열의 수가 기하급수적으로 증가하기 때문에 메모리 사용량이 큰 폭으로 증가하게 됩니다.

이로 인해 메모리 초과가 발생하는 것입니다.

해결 방법

Lazy Evaluation 사용: itertools.permutations는 제너레이터를 제공하므로, 순열을 한 번에 모두 메모리에 저장하기보다는 필요한 순간에 하나씩 생성하여 사용하는 것을 추천드립니다.
효율적인 중복 제거 및 탐색 조건: 형식을 미리 정해서 불필요한 순열을 탐색하지 않도록 코드에서 ok 조건의 체크를 효율적으로 해야 됩니다. 필터링을 모든 순열에 대해 반복하기보다는 바로 필요 조건을 만족하는지 판단할 수 있는 선별 기준을 적용하십시오.
백트래킹 사용: 모든 가능한 문자열을 검사하기보다는 백트래킹을 통해 조건을 만족하지 않는 가지를 미리 차단하여 효율성을 높일 수 있는 부분이 있는지를 확인하여 최적화를 진행할 수 있습니다.

관련된 기존 답변에서 “저.. 시간복잡도 관련 질문입니다.(로직 거의 비슷한 거 같은데, 시간초과가 나서요)” 및 “브루토 포스 백준 1342 질문” 게시글을 참고하면 더욱 높은 효율성과 적절한 메모리 사용으로 문제를 해결할 수 있는 방안을 찾으실 수 있습니다.

해당 답변들에서는 특정 데이터 구조의 사용 및 효율적인 탐색 방법을 제시하고 있으므로 참고하여 최적화를 진행해 보세요.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변