코딩테스트 연습> 연습문제> 피보나치 수

 

<문제링크: https://programmers.co.kr/learn/courses/30/lessons/12945>

코딩테스트 연습 - 피보나치 수

 

문제설명: n번째 피보나치 수를 구해서 1234567로 나눈 나머지를 return하면 된다.

               n번째 피보나치 수는 (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수이다.

 

[1차 시도]

def fibo(n):
    if n <=1:
        return n
    else:
        return fibo(n-1)+fibo(n-2)

def solution(n):
    return fibo(n)%1234567

 

풀이: 먼저 처음에는 피보나치 수를 재귀함수로 구현했다.

 

피보나치 수는 처음 0부터 시작해서

 

fibo(0) = 0

fibo(1) = 1

fibo(2) = fibo(1)+f(0)= 1

fibo(3) = fibo(2)+fibo(1) = 2

fibo(4) = fibo(3)+fibo(2) = 3

fibo(5) = fibo(4)+fibo(3) = 5

...

의 규칙으로 현재 숫자의 앞 숫자 + 앞 앞 숫자가 현재 n번째 피보나치 수이다.

 

따라서 피보나치 수를 구하는 재귀함수는 n이 1이하일 경우, 그대로 n이 나오고 2이상부터는 (n-1) + (n-2)을 반환하면서 재귀를 반복하면 된다. 즉, 현재 숫자 n부터 차례로 줄어들면서 n이 0 또는 1까지 도달 했을 때 n을 반환하고, 다시 n만큼 위로 거슬러 올라가면서 합계를 구하는 형태이다.

 

따라서 재귀함수 실행 후 n번째 피보나치 수를 구한 뒤 1234567로 나눈 나머지를 구했다.

 

채첨결과: 정확성 test case14개 중 7번부터 시간초과와 런타임 에러가 나왔다.

 

해결방법: 피보나치 수는 덧셈을 반복하면서 기하급수적으로 증가하기 때문에 제한사항의 *n은 1이상, 100000이하 자연수의 범위 내에서 표현할 수 있는 피보나치 수가 컴퓨터로 표현할 수 있는 숫자의 범위를 넘어가기 때문에 n번째 피보나치 수를 구할 수 없고, 이렇게 구할 수없는 숫자에서 1234567을 나눈 나머지는 당연히 구할수 없게 된다.

 

따라서 재귀함수 대신 for문을 사용하여 숫자를 증가시키면서 현재 피보나치 수를 구하기 위한 기준점을 갱신해주는 방법을 생각해 봤다.

 

[2차 시도]

def solution(n):
    bin = []
    for i in range(n+1):
        if i<=1:
            bin.append(i)
        else:
            bin.append(bin[-1]+bin[-2])
    return bin[-1]%1234567

 

풀이: 먼저 빈 배열을 만든 후 n까지의 값(n+1)을 for문으로 돌아 i가 0 또는 1이면 bin 배열에 바로 append 한다.

 

2 이상이라면 bin값의 마지막 값 + 두 번째 마지막 값의 합을 append 해준다.

마지막으로 n번째 피보나치 수를 구하려면 bin의 마지막 인덱스로 찾아서 1234567로 나눈 나머지 값을 return 한다.

 

채첨결과: 정확성 테스트 케이스 14개 모두 정상적으로 통과한다.

 

[3차 시도]

def solution(n):
    answer =[0]*(n+1)
    for i in range(n+1):
        if i <=1:
            answer[i]=i
        else:
            answer[i]= answer[i-1]+answer[i-2]
    return answer[n]%1234567

 

풀이: 또 다른 풀이로는 append 방식 말고 인덱스를 고려해 n+1개만큼의 0으로 채워진 answer배열을 만든다.

 

그리고 n+1까지 for문으로 돌면서 i가 0 또는 1이면 answer의 인덱스로 접근해 해당 숫자로 바꿔준다.

 

2 이상부터는 현재 위치에서 앞 숫자와 앞 앞 숫자의 값을 더해준 값으로 answer의 현재 인덱스 자리를 변경해 주면된다.

마지막으로 n번째 피보나치 수에서 1234567을 나눈 나머지 값을 return 한다.

 

 

채첨결과: 정상적으로 잘 통과한다.