문제
풀지 못한 이유
- 이 문제는 풀긴 풀었는데 1시간이나 걸렸고, 메모이제이션 기법을 너무 버벅거려서 정리해 보려고 한다.
풀이) 메모이제이션
메모이제이션(memoization)은 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 제거하는 기법이다. 따라서, 실행 속도를 빠르게 하며 동적 계획법의 핵심이 되는 기술이다.
def superSum(k, n):
# SuperSum(0,n)=n
# k가 0이면 memo 리스트에 값을 n으로 갱신
if k == 0:
memo[k][n] = n
# 메모이제이션 한 적없으면
# memo리스트에 값을 함수 실행 결과값으로 갱신
if memo[k][n] == -1:
res = 0
# SuperSum(k,n)=SuperSum(k−1,1)+SuperSum(k−1,2)+...+SuperSum(k−1,n)
for i in range(1, n + 1):
res += superSum(k - 1, i)
memo[k][n] = res
return memo[k][n]
# 입력이 없을 때까지 수행
while True:
try:
k, n = map(int, input().split())
# 메모이제이션을 위한 2차원 리스트 초기화(원소는 모두 -1)
memo = [[-1 for _ in range(n + 1)] for _ in range(k + 1)]
print(superSum(k, n))
except EOFError:
break위 코드를 하나씩 살펴보자.
먼저, 입력값을 받아야 하는데 입력될 값의 개수가 주어지지 않는다. 즉, 입력이 끝날 때까지 값을 받는다.
이는 while 문으로 무한 반복문을 만들고, 안에서 try와 except으로 예외를 처리하면 된다. 입력이 있을 땐 입력을 받아와서 수행하고 EOFError가 발생하면 반복문을 빠져나온다.
# 입력이 없을 때까지 수행
while True:
try:
k, n = map(int, input().split())
...
except EOFError:
breakEOFError는 입력 도중에 파일의 끝을 만났을 때 발생하는 에러다. (EOF: 파일의 끝(End of File))
그리고 while 문의 try 문안에 메모이제이션을 위한 2차원 리스트를 만든다. 2차원 리스트인 이유는 처리해야 할 값이 k와 n으로 2 개여서다. superSum 함수의 결과값을 memo[k][n] 자리에 갱신해 줄 거라서 초기값은 모두 -1로 정의했다.
# 메모이제이션을 위한 2차원 리스트 초기화(원소는 모두 -1)
memo = [[-1 for _ in range(n + 1)] for _ in range(k + 1)]
print(superSum(k, n))이제 superSum 함수를 살펴보자. 지금 메모이제이션을 사용하고 있다는 것을 잊지 말아야 한다. 문제에서 SuperSum에 대한 설명을 참고하면 k가 0일 때와 0이 아닐 때를 나눠서 처리해 줘야 한다.
그리고 k가 0이 아닐 때는 memo 리스트에서 값을 가져왔을 때 이전에 갱신된 값인지 아닌지에 따라 처리해 줘야 한다. 즉, 메모이제이션 한 적 있는지 없는지에 따라 다르게 처리해야 한다. 아직 메모이제이션 한 적 없으면 superSum 함수 계산 결과로 값을 갱신해야 하고, 이미 메모이제이션한 적 있으면 값을 그대로 가져오면 된다.
def superSum(k, n):
# SuperSum(0,n)=n
# k가 0이면 memo 리스트에 값을 n으로 갱신
if k == 0:
memo[k][n] = n
# 메모이제이션 한 적없으면
# memo리스트에 값을 함수 실행 결과값으로 갱신
if memo[k][n] == -1:
res = 0
# SuperSum(k,n)=SuperSum(k−1,1)+SuperSum(k−1,2)+...+SuperSum(k−1,n)
for i in range(1, n + 1):
res += superSum(k - 1, i)
memo[k][n] = res
return memo[k][n]메모이제이션을 한 적 없을 때, 즉 memo 리스트의 값이 -1일 때를 더 살펴보자. 문제 설명에 따라 SuperSum(k,n)=SuperSum(k−1,1)+SuperSum(k−1,2)+...+SuperSum(k−1,n) 을 구현하기 위해서 for 문으로 반복하여 계산 결과의 합을 구한다.(= res) 그럼 이 값을 memo 리스트에 갱신해 주는 것이다.
# 메모이제이션 한 적없으면
# memo리스트에 값을 함수 실행 결과값으로 갱신
if memo[k][n] == -1:
res = 0
# SuperSum(k,n)=SuperSum(k−1,1)+SuperSum(k−1,2)+...+SuperSum(k−1,n)
for i in range(1, n + 1):
res += superSum(k - 1, i)
memo[k][n] = res풀이 회고
메모이제이션의 개념에 대해서는 알고 있었지만, 이렇게 구현해 본 적은 없었다. 이번에 확실히 알고 넘어갈 수 있었다. 메모이제이션으로 구현하지 않았다면 계속 값을 새로 계산해야 하기 때문에 정말 오랜 시간이 걸릴 것이다. 하지만 메모이제이션 기법을 이용하면 이미 계산한 값은 가져오면 돼서 시간이 엄청 단축된다. 동일한 수행을 반복하여 수행해야 할 땐 메모이제이션을 꼭 기억하자!
💙 참고한 블로그
https://pchild.tistory.com/2
