백준 2096 - 내려가기 [GOLD 5]

숫자 세 개의 입력이 n개 주어집니다. (1 <= n <= 100,000)

인접한 대각선 또는 바로 아래의 수를 계속 더해나가, 가장 밑으로 도달했을 때 가능한 최고의 수와 최저의 수를 출력하면 됩니다.

DP

DP 문제입니다.

특이한 점은 메모리가 제한이 빡빡하기 때문에,

list에 입력을 몰아 넣는 것만으로도 메모리 초과가 발생합니다.

DP 답게 한 단계식 처리하면 되므로, 시작값 리스트 한 개를 할당한 후에,

이후 반복마다 리스트에 입력을 갱신하며 DP로 풀어나가면 됩니다.

그런데 이러한 정답 코드 방법을 쓰지 않고도 문제 해결 자체는 가능합니다. (24/04/02 기준)

노잼 정답 코드

n = int(input())

n_l = list(map(int, input().split()))
dp_min = dp_max = n_l
for _ in range(n-1):
    n_l = list(map(int, input().split()))
    dp_min = [min(dp_min[0], dp_min[1]) + n_l[0],
                min(dp_min) + n_l[1],
                min(dp_min[1], dp_min[2]) + n_l[2]]
    dp_max = [max(dp_max[0], dp_max[1]) + n_l[0],
                max(dp_max) + n_l[1],
                max(dp_max[1], dp_max[2]) + n_l[2]]
print(max(dp_max), min(dp_min))

Array를 활용해봅시다.

처음에 입력을 한번에 받고 무지성으로 코드를 짜면서,

어떻게 메모리 줄타기를 해볼 수 없을까, 잔머리를 굴려봤습니다.

사실 위의 방법이 훨씬 빠르고 메모리 소모도 적은 좋은 코드입니다.

아래는 그저 Array 자료형에 대한 이야기입니다!

Python에도 array가 있다!

Python에는 array 자료형(배열)이 없다고 생각하는 사람들이 꽤 있습니다.

사실 엄밀한 의미의 진짜 array는 없는 게 맞습니다.

애초에 파이썬에는 원시 자료형을 지원한다고 볼 수 없기 때문에, 원시 자료형을 요소로 가지는 엄밀한 의미의 배열은 없습니다.

다만 array와 상당수의 개념을 공유하며, 편의성이 조금 뛰어난 array 모듈이 있긴 합니다!

동적으로 크기를 늘릴 수 있고, 자료를 삽입, 삭제, 추출이 자유롭습니다.

그래서 사실은 효율적인 숫자형 리스트라고 표현하는 게 맞긴 합니다... (공식 문서에도 그렇게 적혀있습니다.)

import array

# 정수형 배열 생성
arr = array.array('i', [1, 2, 3]) # integer

상세한 사용법은 공식DOCS에서 확인합시다! (한글 번역 되어있습니다.)

List와 array의 차이

통념상 list를 array 또는 배열이라고 퉁치긴 하지만, 엄연히 다른 자료형입니다.

List는 매우 편리하지만 진짜진짜 무거운 자료형입니다.

입력, 확장, 삭제가 매우 자유롭고, 자료형 내부에 여러 기본, 복합 자료형을 넣을 수 있습니다.

편의성을 위해서 성능이 상당히 저하된 자료형입니다.

List는 객체의 메모리 주소를 저장합니다.

그에 반해 array는 값 자체를 저장하기 때문에 배열 생성 시 지정한 타입의 객체만 들어갈 수 있습니다.

Python의 array 모듈은 이러한 속성을 갖고 있기 때문에

List나 tuple을 사용하는 것보다 메모리나 실행속도 면에서 효율적인 편입니다.

특히, 이번 문제에서는 더욱 그렇습니다!

array를 활용하는 문제 풀이

다시 한 번 말하지만, 그냥 정답 코드가 훨씬 빠르고 메모리 소모도 적습니다. (이 문제에 대해서는)

아주 단순하게 말하자면, array를 사용할 경우 메모리를 절반 수준으로 줄일 수 있습니다.

이 문제의 제한 사항에 따라 최대한의 입력을 구현하여,

이를 각각 list와 array에 담을 경우 다음과 같은 결과가 나옵니다.

import array, sys, random

arr = array.array('i', [])
list = []

for i in range(100000):
    x = random.randint(0, 9)
    list.append(x)
    arr.append(x)

print(sys.getsizeof(list)) >>> 800984
print(sys.getsizeof(arr))  >>> 408360

list는 기본적으로 정수형 자료에 4byte를 할당하지만,

array('i')의 경우, 2byte를 할당합니다.

이 문제는 입력을 한 번에 받을 경우,

똑같은 객체를 하나 더 만들어야 해서 메모리 소모가 두 배가 됩니다!(이런 거지같은 풀이를 봤나!)

그렇기 때문에 list에 입력을 한 번에 넣어서는 반드시 메모리 초과가 발생하는 문제입니다.

import array

n = int(input())
arr = array.array('i')

for _ in range(n):
    arr.extend(list(map(int, input().split())))
arr2 = arr.__copy__()

def find_m(route, func, mv):
    i = 1
    while i < n:
        for j in range(3):
            m = mv
            for k in range(-1, 2):
                if 0 <= j + k < 3:
                    m = func(m, route[(i-1)*3+(j+k)] + route[i*3+j])
            route[(i*3)+j] = m
        i += 1
    print(func(route[-3:]), end=' ')

find_m(arr, max, 0)
find_m(arr2, min, n*10)

거지같은 결과. 아래는 대부분 DP 방식의 풀이고, 가장 상단의 코드가 array를 활용한 방식입니다.

array 모듈을 불러오는 것 자체가 약 5000kb를 먼저 먹어버립니다.

결과적으로는 800kb 정도를 썼는데, 위의 계산에 거의 들어맞습니다.

애초에 백준의 메모리 소모 기준을 잘모르긴 하지만...

어쨌든, array를 쓰면 정수형 list의 메모리를 절약할 수 있다는 걸 알아둡시다!