수리링의 데이터교실

https://school.programmers.co.kr/learn/courses/30/lessons/12945

오랜만에 피보나치 수열 문제 풀이를 했습니다. 처음에 간단한 재귀함수를 적용해서 풀이를 했더니 테스트는 모두 통과하는데 효율성 테스트에서 시간 초과로 계속 실패를 하는 문제가 발생했습니다. 그래서 효율성을 올리기 위해 메모화를 적용해서 풀이를 했더니 효율성 테스트도 모두 통과할 수가 있었습니다 :-)

간단하게 풀이방법을 설명해 보겠습니다!

1. 메모화 없이 기본 피보나치 수열 함수 작성하기

def basic_fibonacci(n):
    if n in [1, 2]:
        return 1
    if n == 3:
        return 2

    return basic_fibonacci(n-2) + basic_fibonacci(n-1)

만약 주어진 정수가 1 또는 2라면 바로 1을 리턴,

주어진 정수가 3이라면 바로 2를 리턴하도록 초기 설정을 해 줍니다.

4 이상의 정수 n이 주어졌을 때 재귀함수 형식으로 n-2와 n-1에 basic_fibonacci 함수를 적용한 값을 구해 더한 값을 리턴합니다.

basic_fibonacci(8), basic_fibonacci(9), basic_fibonacci(10), basic_fibonacci(11)
# (21, 34, 55, 89)

위 함수는 제대로 작동하지만, n의 값이 커질수록 효율성이 급격하게 떨어진다는 단점이 있어요. 메모화를 이용해서 함수의 효율을 높여보겠습니다.

2. 메모화를 적용한 피보나치 수열 함수 작성하기

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
    if n in [2, 3, 4, 5, 6]:
        return memo[n]
    
    if n > 6:
        for i in range(7, n+1):
            if i in memo: pass
            else:
                memo[i] = memo[i-2] + memo[i-1]
    
    return memo[n]

하나씩 뜯어보겠습니다 :)

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):

가장 먼저 함수를 선언할 때 파라미터 값으로 memo라는 이름으로 딕셔너리를 포함해 주었습니다. 저는 간단하게 n이 1부터 6번째일때 피보나치 수열 값을 딕셔너리에 초기값으로 미리 메모를 해 두었습니다.

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
    if n in [2, 3, 4, 5, 6]:
        return memo[n]

내가 구하고자 하는 것은 피보나치 수열의 n번째 값입니다. 만약 n이 2, 3, 4, 5, 6인 경우 (문제 조건에서 n은 2 이상의 정수라고 했으므로 1은 제외합니다) memo 딕셔너리의 해당하는 value 값을 바로 리턴하고 함수를 종료하게 됩니다.

    if n > 6:
        for i in range(7, n+1):
            if i in memo: pass
            else:
                memo[i] = memo[i-2] + memo[i-1]
    
    return memo[n]

만약 n이 6보다 크면 어떻게 해야 할까요?

주어진 n의 값이 50일 때를 예시로 생각해 봅시다. 우리는 50번째 값을 구하기 위해 48, 49번째 값이 필요합니다.

49번째 값을 구하기 위해서는 47, 48번째가 필요하고

48번째 값을 구하기 위해서는 46, 47번째가 필요합니다.

결국 50번째 값을 구하기 위해서는 1부터 49번째까지 피보나치 수열 값을 모두 알아야 합니다.

그럼 메모화는 어떻게 작동할까요?

제가 만약 50번째 피보나치 수열 값을 구하기 전에,

40번째 피보나치 수열 값을 먼저 구했다고 생각해 보겠습니다.

fibonacci(40)
# 102334155

우리는 40번째 피보나치 수열 값을 구하기 위해 지금 1번째~39번째 피보나치 수열의 값을 열심히 구했습니다.

이제 다음으로 50번째 피보나치 수열 값을 구하려고 합니다.

먼저 메모화를 해놓지 않은 경우를 생각해 봅시다.

우리는 이미 1번부터 40번째까지의 값을 이전에 미리 구한 전적이 있지만

따로 기록을 해 두지 않았기 때문에 같은 계산을 또 반복해야 합니다.

1번째~49번째 피보나치 수열 값을 열심히 또 구하는 거죠.

하지만 제가 기록을(메모화를) 해 두었다면 얘기가 달라집니다.

즉 처음에 fibonacci(40)을 계산했을 때

memo 딕셔너리에 1번부터 40번까지 피보나치 수열 값을

key(n) : value(값) 형식으로 미리 저장을 해 두었다면,

우리는 fibonacci(50)을 구할 때 

1. 1번부터 40번까지는 간단히 딕셔너리에서 값을 찾아 가져올 수 있습니다.

2. 41번부터 49번째 값은 새로 구하고 딕셔너리에 값을 추가해주는 방식으로 계속해서 메모를 해나갈 수 있습니다.

+ 참고로 함수를 여러번 작동하면서 메모장에 추가하는 key와 value 값은 매번 초기화되지 않고 계속해서 누적 기록을 보관합니다.

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
    # 주어진 정수가 2-6중 하나일 경우 바로 메모장에서 수열값을 찾아 리턴, 함수종료
    if n in [2, 3, 4, 5, 6]:
        return memo[n]
    
    # 주어진 정수가 6보다 큰 경우(7 이상)
    if n > 6:
    	# 7부터 n까지의 정수 i에 대해서
        for i in range(7, n+1):
            # 만약 메모장에 i값이 이미 메모되어 있다면 그냥 넘어가고
            if i in memo: 
                pass
            # 만약 메모장에 i값이 없다면 피보나치 수를 구해서 추가해주세요
            else:
                memo[i] = memo[i-2] + memo[i-1]
    
    # 메모장에서 n번째 피보나치 수열 값을 찾아 리턴해주세요
    return memo[n]

최종 피보나치 함수입니다 :)

내가 구하고자 하는 n의 피보나치 값을 찾기 위해 7부터 n-1번째의 수열값을 계속해서 차례대로 메모장에 누적 메모해나가는 방식입니다. 재귀함수랑 약간 비슷한듯 다른 느낌이네요!

3. 최종 문제풀이

마지막으로 문제 해결을 위해 피보나치 수열을 활용해서 soluton()함수를 작성했습니다. 저는 코딩테스트 문제를 풀 때 이렇게 함수를 나누어 작성하는것을 좋아합니다. 함수 안에 함수 작성하는거 시러요.....(개취)

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
    if n in [2, 3, 4, 5, 6]:
        return memo[n]
    
    if n > 6:
        for i in range(7, n+1):
            if i in memo: 
                pass
            else:
                memo[i] = memo[i-2] + memo[i-1]
    
    return memo[n]

def solution(n):
    fibo_num = fibonacci(n)
    
    # fibonacci(30)< 1234567 < fibonacci(31)
    # 만약 n이 30 이하라면 바로 fibo_num을 리턴하고(몫이 0이므로 나머지와 동일)
    if n <= 30 : 
        return fibo_num
    # 만약 n이 30보다 크다면 fibo_num을 1234567으로 나눈 나머지를 리턴
    else :
        return fibo_num % 1234567

풀이나 설명에 오류가 있다면 댓글로 알려주세요!

감사합니다! :-)