Programmers Coding Quiz #35 피보나치 수

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한사항

• n은 1이상, 100000이하인 자연수입니다.

입출력 예

n	return
3	2
5	5

풀이

def fibonacci(n):
    idx = 2
    result = [0, 1]
    while idx < n + 1:
        num = result[idx-2]+result[idx-1]
        result.append(num)
        idx += 1
    return result[-1] % 1234567

1. 피보나치 수열이 적용되는 범위는 index = 2부터 이므로 index를 2로 설정해둡니다. index = 0과 1은 무조건 0, 1이 되므로 결과 리스트를 [0,1]로 세팅하고 while문을 돌립니다.
2. 새로 추가될 수는 피보나치 수열에 따라 결과 리스트의 전 인덱스와 전전 인덱스입니다. 이를 이용해 새로운 수를 만들고 이를 추가하고, 인덱스를 늘려줍니다. 인덱스는 n번째까지 모두 돌려야 되므로 while idx < n + 1로 세팅해줍니다.
3. 최종적으로 완성된 결과리스트의 가장 마지막 번째 수가 n번째 피보나치 수열이 되며 이를 조건에 따라 1234567로 나머지 나눗셈(%)을 해주면 원하는 결과가 반환됩니다.

다른 풀이

def fibonacci(num):
    a,b = 0,1
    for i in range(num):
        a,b = b,a+b
    return a

다중대입문(multiple assingment)을 활용한 파이써닉하고 간단한 풀이입니다. a, b 를 b, a+b로 n번째까지 계속 대입시켜줘서 풀어내는 방식입니다.
이전 문제에서 다중 대입문을 본 적이 있었는데, 막상 적용하려니 생각이 나지 않았네요. 역시 단순히 아는것에 그치지않고 응용시점에서 그것을 기억해내는것이 효율적 알고리즘 풀이를 위해선 매우매우 중요하네요. 😫