0224_오늘 고생 좀 시킨 그 놈... 'SuperSum'(memoization 활용)

오늘 하루 종일 풀었는데 너무 힘들었다.

재귀미워ㅜ

리뷰는 내일 덧붙여야지

 

---

25일 추가,

그렇다 리뷰를 덧붙인다.

 

이번에 코드업 재귀함수 파트 문제들을 풀면서 재귀의 개념, 어떻게 코드를 작성하는 지에 대한 연습을 했다. 문제 풀다보니 조금은 감이 잡혔는데, 예상치 못한 문제가 나타났다. 바로 런타임 에러. 재귀함수를 쓰면 보통 연산 시간이 늘어나고 비효율적이라는 말을 들어본 적이 있을 것이다. 이 문제를 해결하기 위해서 'Memoization' 개념을 가져와 문제 풀이에 적용했다. 

 

Memoization(메모이제이션)은 나도 이번에 처음 알게 됐다. 이는 컴퓨터가 동일한 계산 과정을 반복하지 않도록 이미 계산한 값들을 따로 저장해두고 필요할 때면 그 값들을 불러와 사용하는 것이다. 즉, 계산 반복을 줄여 프로그램 실행 속도를 빠르게 하는 방법이다.

 

그럼 다음 문제와 함께 어떻게 사용했는지 살펴보겠다.

해당 문제는 codeup_재귀함수_1930번 문제_SuperSum

출처 : https://codeup.kr/problem.php?id=1930

SuperSum

SuperSumSuperSum 함수는 다음과 같이 정의된다. SuperSum(0,n)=nSuperSum(0,n)=n (nn은  모든 양의 정수)
SuperSum(k,n)=SuperSum(k−1,1)+SuperSum(k−1,2)+...+SuperSum(k−1,n)SuperSum(k,n)
=SuperSum(k−1,1)+SuperSum(k−1,2)+...+SuperSum(k−1,n)
kk와 nn이 여러개 주어진다. SuperSumSuperSum의 값을 각각 출력하시오.

import sys

def SuperSum(k, n):
    total=0
    if k == 0:
        total += n
        sum_lst[(k, n)] = n

    else:
        for i in range(1, n + 1):
            if (k - 1, i) not in sum_lst:
                sum_lst[(k-1, i)] = SuperSum(k - 1, i)
                total += sum_lst[(k-1,i)]
            else:
                total += sum_lst[(k - 1, i)]
    return total

for line in sys.stdin:
    k, n = map(int,line.split())
    total = 0
    sum_lst = {}

    print(SuperSum(k,n))

 

 

- 18번째 줄, 맨 아래 for문은 입력 값 여러개를 한 번에 받기 위해서 처리해준 코드

- 메모이제이션에서 메모리를 저장하는 공간을 보통 리스트, 딕셔너리로 두는 데 특히 이 문제는 많은 사람들이 2차원 배열을 활용한 거 같았다. 나는 딕셔너리 형태로 supersum(k,n)을 키로, 값을 밸류로 저장해두고 필요할 때마다 호출해서 계산하지 않고 바로 사용할 수 있게 처리해 주었다. 

- 길지 않은 코드이나 재귀, 메모이제이션 개념을 이해하고 활용하는 데 어려움이 있었다.