[Python] 프로그래머스, 피보나치 수 Lv.2 (feat.for loop, recursion, 파이썬)

반짝반짝 알고리즘, 인프준

 

 

 

피보나치 수

문제 링크

프로그래머스

 

문제 설명

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

• 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'로 나눈 나머지를 리턴하는 함수를 완성해 주세요.

 

제한 조건

n은 2 이상 100,000 이하의 자연수입니다.

 

 

입출력 예

n	return
3	2
5	5

 

입출력 예 설명

피보나치의 수는 0번째부터 0, 1, 1, 2, 3, 5,... 와 같이 이어집니다.

 

 

 

해결 과정

For loop 활용

먼저 재귀를 사용하지 않고 코드를 구현해 보았습니다. F( 0 )과 F( 1 )을 각각 a, b로 선언해 주었습니다. 그리고 문제에서 n은 2 이상이라는 조건에 따라 2부터 n까지 for문을 돌립니다. 그럼 F( 2 )부터 진행될 텐데 공식에 따라 a + b로 만들어줍니다. 그리고 다음 루프에서 사용할 a, b를 세팅해 줍니다. 이때 F( n ) = F( n - 1 ) + F( n - 2 ) 공식에 따라 answer = a + b의 다음 루프는 i + 1 = b(a) + answer(b)입니다.

 

즉 a는 다음 루프에서 b가 되고 b는 다음 루프에서 answer가 됩니다.

 

이렇게 n까지 반복하고 나면 F(n)의 값이 answer에 담기게 됩니다. 문제에서 answer를 1234567로 나눈 나머지 값을 반환하는 함수를 만들라고 했으니 % 연산자를 써서 나머지 값을 반환해 줍니다.

def solution(n):
    a, b = 0, 1             # F(0) = a, F(1) = b
    
    for i in range(2, n+1): # n은 2 이상이므로 2부터 n까지
        answer = a + b      # F(n) = F(n-1) + F(n-2)
        a, b = b, answer    # b = a + 1, answer = b + 1
    
    return answer % 1234567 # 1234567로 나눈 나머지 반환

 

비교적 빠른 실행 결과를 확인할 수 있습니다. 이외에도 list를 활용한 방법과 재귀함수를 활용한 방법들과 실행 시간을 알아보겠습니다.

 

 

List 활용

로직의 개념은 위 for loop문제와 같지만 변수 선언이 아닌 list에 append를 진행하면서 담긴 수를 활용하여 연산하고 마지막에 담긴 수를 나머지 연산하여 리턴하는 코드입니다.

def solution(n):
    answer = [0,1]                              # F(0) = a, F(1) = b

    for i in range(2,n+1):                      # n은 2 이상이므로 2부터 n까지
        answer.append(answer[i-1]+answer[i-2])  # F(n) = F(n-1) + F(n-2)

    return answer[-1] % 1234567                 # 1234567로 나눈 나머지 반환

 

list를 활용하면서 코드는 간결해졌습니다. 하지만 작은 수가 입력되었을 때 큰 차이가 없지만 큰 수가 입력되면서 실행시간이 비교적 커지는 걸 확인할 수 있습니다.

 

 

재귀 활용

재귀호출을 활용해서 구현한 코드입니다. 코드가 훨씬 더 간결해졌지만 시간 초과가 발생합니다. recursive하게 구현하여 많은 실행 시간이 걸리는 경우가 생긴다면 짧은 코드가 시스템을 죽게 만들 수도 있기 때문에 문제를 이해하고 적절한 상황이 아니라면 쓰지 않는 것이 중요합니다.

def solution(n):
    if n < 2:
        return n
    else:
        return (solution(n - 1)+solution(n - 2)) % 1234567

 

 

 

또 다른 풀이

def solution(n):
    a, b = 0, 1          # F(0) = a, F(1) = b
    for i in range(n):
        a, b = b, a + b  # F(n) = F(n-1) + F(n-2)
    return a % 1234567   # 1234567로 나눈 나머지 반환

 

 

위 For loop을 활용한 코드를 좀 더 리팩터링 한 코드입니다. 머릿속에 있는 문제가 아니면 처음부터 완벽하고 효율적인 코드를 구현하기는 어렵습니다. 문제를 차근차근 직관적으로 써서 결과가 나오게끔 구현한 뒤 변경 가능한 곳들을 찾아 효율적으로 리팩토링하는 습관을 가져보면 어떨까 합니다.

 

 

 

 

 

---

 

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습,https://school.programmers.co.kr/learn/challenges