메모리 초과가 나는 이유가 궁금합니다!

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

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

해결된 질문

작성

106

안녕하세요, 강의를 듣고 계신 여러분!

여러분의 학습을 돕기 위해 질문 안내를 드리고자 합니다.

1. chatGPT를 이용해보기

단순한 의문은 chatGPT를 이용해도 해답을 찾을 수 있는 경우가 종종 있습니다!

2. 강의의 어떤 부분에 대한 질문이고, 어떤 부분이 궁금한지 명확히 알려주세요!

강의의 어느 파트에서 의문을 느끼고, 어떤 부분이 궁금한지를 명확히 제시해 주시면 답변에 도움이 됩니다!
자신은 어떻게 이해했는지 또한 적어주면 좋습니다!

ex) 섹션5의 '그래프 순회 (DFS & BFS) [개념]' 강의에서 DFS와 BFS 모두 그래프의 모든 노드를 탐색하는 알고리즘이라고 하셨고 시간 복잡도 또한 똑같다고 이해했습니다. 그러면 DFS와 BFS 중에서 어떤 알고리즘이 더 효율적인지 구별하는 것은 의미가 없는 것일까요?

어느 파트
- 섹션5의 '그래프 순회 (DFS & BFS) [개념]' 강의
자신은 어떻게 이해했는지
- DFS와 BFS 모두 그래프의 모든 노드를 탐색하는 알고리즘이라고 하셨고 시간 복잡도 또한 똑같다고 이해
어떤 부분이 궁금한지
- DFS와 BFS 중에서 어떤 알고리즘이 더 효율적인지 구별하는 것은 의미가 없는 것일까요?

안녕하세요 선생님!

[브루트 포스 알고리즘 : BOJ 1342 행운의 문자열] 문제를 혼자 풀었는데, 메모리 초과를 해결하지 못해 질문합니다..!

permutations를 이용하여 풀고, set 함수를 사용하여 중복되는 것이 없도록 했습니다.

혹시 set 함수를 사용해서 메모리 초과가 나온 걸까요..?

from itertools import permutations

S = input()
answer = set()

for x in permutations(S, len(S)):
    ok = True

    for i in range(len(x)-1):
        if x[i] == x[i+1]:
            ok = False
            break


    if ok:
        answer.add(x)

print(len(answer))

python 코딩-테스트 알고리즘

답변 2

알리 Ally

지식공유자

안녕하세요. jinii915님!

풀이 과정에서 행운의 문자열을 answer set에 추가하고 있으신데요.

행운의 문자열 S의 최대 길이는 10으로 최대 10! 만큼 answer에 원소가 추가되면서 메모리 초과가 나는 것으로 추정됩니다.

최대 10!만큼 set에 들어갈 수 있는데, 그 형태가 튜플이며 그 안에는 최대 10개의 문자열이 들어가 있으므로 메모리 초과가 날 확률이 큽니다.

따라서 정답으로 출력할 행운의 문자열을 별도의 set 자료구조에 저장하는 것이 아닌, 카운트하는 방식으로 풀이를 수정해주시면 메모리 초과 이슈를 해결하실 수 있으실겁니다.

정확한 메모리 계산이 궁금하실 수 있는데요.

정확한 메모리 계산은 파이썬이라는 프로그래밍 언어가 어떻게 돌아가는지 알아야 알 수 있는 부분이라 알기 어렵고, 실제로 코딩테스트 문제에서도 정확한 메모리 계산 능력까지 요구하지도 않습니다.

따라서 이번 문제와 같이 자료구조를 선언하고 해당 자료구조에 넣어야 할 원소가 백만, 천만 단위를 넘어가게 되는 경우는 메모리 초과에 유의할 필요가 있다는 정도로 알아두시면 될 것 같습니다.

추가적으로 시간복잡도 관련 강의에서 언급한 '5000만 정도의 크기의 간단한 자료형(ex) 리스트)은 사용해도 된다' 부분은 C++ 기준이며, 파이썬 메모리을 고려해 주지 않는 문제는 좀 더 보수적으로 메모리 크기를 계산할 필요가 있습니다.

파이썬으로 코딩테스트 문제를 풀 때 메모리 계산은 관련한 내용은 코딩테스트 준비에 있어 필요한 부분인 것 같아 추후 강의 자료에 정리해서 추가 및 공유드리겠습니다.

또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.

감사합니다. :)

인프런 AI 인턴

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

님의 질문에 대해 답변 드리겠습니다.

일단, 메모리 초과 문제는 입력하는 문자열 S의 길이가 커질 때, permutations 함수로 생성되는 모든 순열을 메모리에 저장하려고 할 때 발생할 수 있습니다. permutations 함수를 사용하면, S의 길이가 n일 때 n!만큼의 순열이 생성되므로, 문자열의 길이가 길어질수록 매우 빠르게 메모리 사용량이 증가합니다.

특히, 중복된 문자가 있을 경우 permutations 함수는 중복된 순열도 모두 생성하기 때문에, 이를 set 함수를 통해 중복을 제거하는 과정에서도 상당한 메모리를 소모합니다. 하지만, 중복 제거를 위해 set 함수를 사용하는 것 자체가 메모리 초과의 직접적인 원인이라기 보다는, permutations 함수로 생성된 모든 순열을 메모리에 저장하는 과정에서 발생하는 메모리 초과가 더 큰 원인으로 볼 수 있습니다.

메모리 초과 문제를 해결하기 위해서는, 모든 순열을 한 번에 메모리에 저장하는 것이 아니라 필요한 순열만을 생성하거나 메모리 사용량을 줄일 수 있는 다른 방법을 고려해야 할 것입니다. 예를 들어, generator를 이용하여 필요한 순간에만 순열을 생성하거나, 알고리즘을 최적화하여 순열 생성 자체를 줄이는 방법 등이 있을 수 있습니다.

문제를 해결하는 데 도움이 되기를 바랍니다.

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