[백준]10989_수정렬하기3

문제

• 링크
• 보기엔 간단하게 주어진 수를 입력받아 sort하고 오름차순으로 정렬하면 되는 것 같은 문제지만, 메모리 8MB제한이 계속 걸린다.

CODE

import sys
input = sys.stdin.readline
n = int(input())
base = [0] * 10001 # Index는 0부터니까
for _ in range(n): # 숫자 저장
    num = int(input())
    base[num] += 1

for i in range(10001): # 출력 
    if base[i] != 0:
        for j in range(base[i]):
            print(i)

• 처음엔 당연히 위에 적은대로 list에 append하고 sort 후 출력 하려고 했으나 메모리 초과가 뜬다.
• 왜냐면 list의 append 기능은 메모리의 재할당이 일어나기 때문에 메모리를 많이 잡아먹기 때문이다! (자세한 내용은 아래 참고)
• 그래서 입력될 사이즈의 제한이 주어졌으니, 그만큼의 리스트를 먼저 만들어주고 값을 변경하는 방식으로 풀었다.

배운 것

👀중요 List append의 메모리 재할당

(사실 이전 공모전 할 때도 append 썼다가 속도때문에 혼난적이 있다. 그게 왜그런가 했더니 이런 이유였구만...!)

• Python의 list는 초깃값을 설정하지 않는 동적배열이다. 그래서 리스트가 꽉 채워지면 더블링(미리 초깃값을 작게 잡아 배열을 생성한 뒤 데이터가 꽉 채워지면 늘려주고 복사) 방식을 통해 크기를 늘려주는 동작을 계속해서 해줘야한다. 이렇게 더블링을 할 때 기존의 메모리 + 2배(혹은 1.12배) 늘어난 메모리를 동시에 잡아먹어서 메모리 누수가 일어난다. (기존 집 + 이사가는 집)

• 또한 이렇게 계속해서 데이터를 옮겨줌으로 속도가 느려지는건 당연하게 느껴진다.

• 그래서 나온 방법이 미리 N개의 공간을 만들어주고 그 공간의 값만 바꿔주는 식으로 진행하면 속도도 빨라지고, 메모리가 오버되는 것도 막아줄 수 있다. (그래서 ai모델만들때도 0 배열 만들어놓고 값을 바꾸는건가)

• 크 오늘도 하나 알아가서 기분이 좋다!

참고블로그

• Python의 List 구조 성능분석
• 파이썬 리스트 내부 구조
• 파이썬 - 메모리 관리와 좋은 습관
• 10_메모리 관련 요거 한번 쭉 읽어봐야겠다.