자료형, 메모리, 그리고 Python [0]

SWEA에서 Python의 메모리 계산 방식이 달라진 모양이다. 예전에 Pass한 풀이를 다시 집어넣었는데 총 20개의 테스트 케이스 중에서 7개만 통과하고 메모리 초과로 Fail을 받았다. 이때까지만 해도 별 생각이 없었다. 조금만 고치면 되겠지 뭐.

 

그렇게 데이터를 구겨넣는 여정이 시작되었다.

 

문제는 2차원 배열에서 각 좌표가 가져야 할 값을 구하는 전형적인 BFS. 주어지는 좌표가 1000 미만이라 큐에 (x, y) 좌표를 각각 집어넣는 대신 1000x+y의 형태로 바꿔보았다. 테스트 케이스를 10개까지 통과할 수 있었다.

 

각 좌표가 가지는 값의 상한은 1998. 2차원 배열을 1차원으로 이어붙인 다음 2k번째 좌표와 2k+1번째 좌표의 값을 value(2k)*10000+value(2k+1)로 표현함으로써(예를 들어 0번째 좌표의 값이 1324, 1번째 좌표의 값이 1234라면 컨테이너의 0번째 인덱스에 13,241,234를 집어넣는 식이다) 좌표가 가져야 할 값을 담는 컨테이너의 크기를 절반으로 줄였다. 테스트 케이스를 14개까지 통과할 수 있었다.

 

거기서 생각이 멈췄다. '이거 컨테이너를 더 줄여봐야 의미가 없지 않나?' 근거는 두 개였다.

 

1) 컨테이너를 더 줄이기 위해서는 3k, 3k+1, 3k+2번째의 좌표가 가질 값을 합쳐야 할 텐데, 원래 컨테이너의 크기가 1이라고 할 때 현재는 0.5, 세 좌표에서의 값을 합쳐봐야 길이는 0.33이다. 0.5의 차이로 4개의 테스트 케이스를 통과했으니 0.17로 남은 6개를 통과하기는 어려울 테고, 심지어 컨테이너의 길이가 0이 되더라도 마찬가지일 듯했다.

 

2) 그렇게 세 좌표에서의 값을 합친 수의 자릿수는 최대 12자리로, 여타 언어의 int 자료형이 갖는 범위인 2^31(~10^9)을 훌쩍 넘는 수치다. Python에서 int 자료형이 얼마나 되는 메모리를 차지하는지는 모르지만 아마 특정 길이를 벗어나면 메모리를 추가로 할당하는 방식일 거라고 생각했고(처음부터 커다란 메모리를 할당하는 것은 낭비이므로), 그렇다면 함부로 좌표의 값을 합쳐봐야 이득이 아닐 가능성이 높았다.

 

그렇게 자료형에 대해 고민하다가 달리 의아한 지점이 떠올랐다. '이거 테스트 케이스가 바뀔 때마다 메모리가 초기화되어야 하는 거 아닌가?' 입력값이 최대로 들어왔을 때를 견뎠다면 이후의 변수는 큐에 쌓이는 데이터뿐이다. 큐에 데이터가 너무 많이 쌓였을 가능성도 있긴 했지만, 어쩐지 할당된 메모리가 해제되지 않고 그대로 남아있을 거라는 느낌을 받았다. 강사분께 여쭤보니 그렇다는 대답이 돌아왔다. 아이고 맙소사.

 

'파이썬 메모리 할당 해제'로 검색하자 gc라는 모듈에 대한 정보가 나왔다. 하지만 아쉽게도 SWEA에서는 gc 모듈의 import를 금지하고 있었다. 생각 끝에 테스트 케이스마다 변수에 새로운 리스트를 할당하는 대신 빈 리스트를 만들어두고 그 내용물을 초기화하는 방식을 사용해봤다. 코드로 예시를 들자면 다음과 같다.

# 기존의 방식
t = int(input())
for case in range(1, t+1):
    field = [input() for _ in range(n)]
    move = [[0]*m for _ in range(n)]
    # ...


# 새로운 방식
field = ['']*1000
move = [0]*1000000

t = int(input())
for case in range(1, t+1):
    n, m = map(int, input().split())
    for i in range(n):
        field[i] = input()
        for j in range(m):
            move[i][j] = 0
    # ...

 

기존의 방식은 이전 테스트 케이스에서 사용한 리스트가 통째로 메모리 영역 어딘가를 떠돌 가능성이 있었지만, 새로운 방식을 쓰면 리스트의 내용물만 교체되고 끝날 거라고 생각했다. 바로 고쳐서 제출해봤다.

 

결과는?

 

야호!

 

가정이 맞아들어갔다! 내가 추측한 바의 전후 상황이 전부 올바르진 않겠지만, 그래도 맞물리는 부분이 있었다는 뜻이라고 본다.

 

동시에 Python에 대해서 "잘" 알고 있었다면 이 결론에 더욱 빠르게 도달했을 거라는 생각이 들었다. Python에서의 리스트란 무엇인지, 리스트는 무엇을 담는지, 스택 메모리는 뭐고 힙 메모리는 뭔지, 메모리 공간을 부유하는 쓰레기가 왜 생기는지 그리고 어떻게 생기는지, 그런 쓰레기를 Python은 어떻게 처리하는지 등등. 궁금한 부분이 많았다.

 

이 포스팅 시리즈는 그러한 질문들에 대한 나름의 이해를 늘어놓을 예정이다.