[ 프로그래머스 Lv.2 ] 피보나치
알고리즘
익히 알고있는 피보나치 수열을 구현하면 된다.
예상했던대로 recursion으로 구현하면 시간초과가 떠서 다이나믹 프로그래밍의 memoization을 활용하려고 했다.
# 일반적인 Recusion에 memoization을 더한 소스코드
def fibonacci(n, memo):
if memo[n] != -999:
return memo[n]
else:
result = fibonacci(n-1, memo) + fibonacci(n-2, memo)
memo[n] = result
return memo[n]
def solution(n):
memo = [-999]*(n+1)
memo[0], memo[1] = 0,1
result = fibonacci(n, memo)
answer = result % 1234567
return answer그런데 문제가 생겼다.
런타임 에러가 생겨서 입출력에 예외사항이 있는지 찾아보려고 했다.
문제 설명에 있는 1234567로 나눠주는 부분이 이해가 안되서 찾아보니 모듈러 연산 성질을 이용하기 위한 것이라는 것을 알 수 있었다.
그런데 나는 Python을 사용하기 때문에 overflow가 난 문제는 아니었다.
결국 한 블로그에서 이유를 찾을 수 있었다. 👉🏻참고한 블로그
재귀호출에는 호출 가능한 깊이가 정해져있는데 테스트 케이스에서 해당 깊이를 초과했기 때문이다.
repl.it에서 돌려보니 실제로 그러했다.
아예 recursion을 사용하지 않는 방법을 택하기로 했다.
(왜 처음부터 이 방법은 생각하지 못했을까..)
n이 주어지면 n만큼 for loop를 돌면서 memoization을 채워나가는 방식이다.
이렇게하면 동일한 값을 두번 이상 찾을 일도 없고, 재귀함수의 리밋에도 걸릴 일이 없다.
피보나치 수열은 굉장히 유명한 문제라서 다들 풀이법을 알고 있다는데, 다음부터는 헤매지 말아야지❗️
Lessoned Learn
1. 모듈러 연산
숫자 A, B, C가 있다고 하면 (A + B) % C의 값은 ( ( A % C ) + ( B % C) ) % C와 같다는 성질이다.
이 외에도 모듈러 연산의 성질에는 여러가지 있다.
조만간 한꺼번에 정리해보겠다.
N으로 나눈 나머지를 반환하는 문제는 십중팔구 "int64도 버티지 못할만큼 숫자가 엄청 커지니까 적당히 나눠라"는 늬앙스이다.
중간에 모듈러 연산을 안해주면 오버플로우가 발생했을 것이다.
2. Recursion Runtime Error
재귀 함수가 돌 수 있는 재귀의 깊이를 초과한 경우 시간초과뿐만 아니라 런타임 에러가 발생할 수 있다.
최종 소스코드
def solution(n):
memo = [0,1]
for i in range(2,n+1):
memo.append((memo[i-1]+memo[i-2])%1234567)
answer = memo[n]
return answer