매일 백준이나 프로그래머스에서 문제를 풀고 브랜치로 관리한지 3주가 넘었다. 쉬운 문제라도 꾸준히 풀어주니 확실히 감이 유지되는 느낌..! 오늘은 프로그래머스에서 피보나치 수 문제를 다양하게 풀어본 김에 정리해보고자 글을 작성하게 되었다.
프로그래머스 - 피보나치 수
피보나치 수 문제는 일반적으로 볼 수 있는 피보나치 수 문제와 크게 다르지 않다.
수없이 접한 문제라 눈감고도 풀겠다.... 고 하고 제출했는데 실패가 나왔다. 읭?
그냥 피보나치 수만 생각하고 1234567로 나눈 나머지를 리턴하라는 조건을 잠깐 망각했던 것이다. 닭가슴살 먹다보니 머리가 안 돌아가는 것인지.....?
해당 조건을 적용해주니 당연히 통과가 나오긴했는데.... 여러가지 풀이로 해결해보고 싶었다. 총 3가지 풀이가 나왔는데, 하나하나 살펴보자.
공통사항 : 나머지 연산 분배법칙
살펴보기에 앞서, 3가지 풀이 모두 % 1234567 은 매번 적용해주었다.이게 가능한 이유는, (A + B) % p = ((A % p) + (B % p)) % p 와 같이 나머지 연산에 분배법칙이 성립하기 때문이다. 따라서 n번째 피보나치 수를 구할 때마다 그냥 (n-1번째 수 + n-2번째 수 ) % 1234567을 해주면, n-1번째 수 + n-2번째 수에도 % 1234567 이 적용된 것과 같은 효과이므로 편리해진다.
아무래도 숫자가 커질수록 연산의 비용 역시 커지기에, 다 구하고 마지막에만 % 1234567을 해주는 것보다는 그때그때 미리 적용해주는 것이 좋기도 하겠다.
풀이 1 - 재귀
def solution(n):
def fib(x):
if x in (1,2):
return 1
return (fib(x-1) + fib(x-2)) % 1234567
return fib(n)간단한 풀이지만, 재귀함수로 구현하면 수행시간이 너무 오래 걸린다.
n이 커질수록 동일한 x에 대한 fib(x)가 여러 번 중복호출되기 때문이다. 
위의 그림을 참고해보면, 당장 n이 5만 되더라도 fib(0)은 3번, fib(1)이 5번 등등으로 딱봐도 비효율적이며, 문제조건 상 n의 최댓값인 100,000이 들어온다고 생각하면...... 끔찍하다. 역시나 테스트를 통과하지 못한다. n이 비교적 작은 숫자인 초급자용 문제에만 통과하는 풀이일 것이다.
풀이 2 - DP
DP를 활용하니 당연히 테스트를 통과할 수 있었고, 시간도 우수한 편이다.
개인적으로 Bottom-up 방식이 더 마음에 들어서 그렇게 풀어보았다.
def solution(n):
DP = [0] * (n+1)
DP[1] = 1
for i in range(2, n+1):
DP[i] = (DP[i-1] + DP[i-2]) % 1234567
return DP[n]
다만 테스트 13과 테스트 14의 결과가 확연히 느린 것으로 보아, 이 2가지 테스트에 주어진 n값이 매우 높을 것으로 유추할 수 있었다.
풀이 3 - 파이썬 swap 활용
이번 글을 쓰게 만든 풀이이기도 한데, 파이썬의 swap을 활용해 풀이한 방식이다.
파이썬에서는 a,b = b,a와 같이 표기하여 간단히 값을 바꿔줄 수 있다. 다른 언어에서는 보통 temp라는 별도의 변수를 만들어 temp = a, a = b, b = temp 이런 식으로 해주어야 함을 생각하면, 정말 간편하다. 이러한 성질을 활용해서 간단히 식을 작성해보았다,
def solution(n):
a,b = 0,1
for i in range(n):
a,b = b,(a+b) % 1234567
return a최초에 a는 fibo(0)의 값과 같고, b는 장차 fibo(1)에 들어갈 값으로서 1로 초기화해준다. 그리고 n만큼 반복문을 수행하며 b에 있던 값은 a로 넣어주고, a+b를 b에 넣어준다. a가 fibo(n-2), b가 fibo(n-1)의 역할을 수행하며 그 합인 a+b를 b에 업데이트 해주는 방식이라고 보면 된다.
풀이 2와 비교해보면 테스트 13과 14에 비해 무려 4배 빠르며, 풀이 2에서의 DP테이블 역할을 변수 a,b 2개로 해결했기에 메모리도 훨씬 적게 사용한다. 파이썬에서만 가능한 풀이긴 하지만, 그래도 이렇게 더 효율적인 방법이 있다는 것은 반드시 기억할만 하다 :)
