99클럽(3기) - 코테스터디 9일차 TIL # DP

프로그래머스 - 피보나치 수

1. 문제 설명

n번째 피보나치 수를 1234567로 나눈 나머지를 리턴하는 함수 solution을 완성하라.

 

2.  제한 사항

• 2 <= n <= 100,000

 

3. 입출력 예

 

---

 

4. 첫 번째 풀이(런타임 에러) - Python

런타임 에러가 발생했다. 재귀를 사용했기 때문에 n이 100,000에 가까운 숫자일 경우 스택 오버플로우가 발생했을 것이다.   

 

1) 메모이제이션과 피보나치 수 계산을 위한 F 클래스 생성

초기화 함수 __init__에서 F(0) = 0, F(1) = 1로 메모이제이션을 위한 딕셔너리를 초기화한다. 피보나치 수열을 계산하기 위한 함수 fibo에서는 self.memo에 있는 키인지 먼저 확인 후 없으면 피보나치 수를 재귀적으로 계산한다. 이 때, n이 충분히 커졌을 경우 발생 가능한 오버플로우 방지 및 처리 속도 향상을 위해 fibo 수행 시마다 나머지 연산을 수행했다. 

 

2) solution 함수 작성

F 클래스의 인스턴스를 생성하고 n번째 피보나치 수를 반환한다. 문제에서는 n번째 피보나치 수에 1234567을 나눈 나머지를 반환하라고 했는데, 이미 fibo() 실행과 함께 연산을 수행했으므로 결과값 그대로 반환하면 된다.  

 

class F:
    def __init__(self):
        self.memo = {0: 0, 1: 1}  # F(0) = 0, F(1) = 1로 초기화

    def fibo(self, n):
        if n in self.memo:
            return self.memo[n]
        
        # 메모이제이션을 사용해 피보나치 수를 재귀적으로 계산
        self.memo[n] = (self.fibo(n-1) + self.fibo(n-2)) % 1234567
        return self.memo[n]

def solution(n):
    fn = F()  # F 클래스의 인스턴스를 생성
    return fn.fibo(n)  # n번째 피보나치 수를 반환

 

5. 두 번째 풀이 - Python

재귀 대신에 for문을 사용해서 풀었더니 런타임 에러 없이 정답으로 처리되었다.

class F:
    def __init__(self):
        self.memo = {0: 0, 1: 1}  # F(0) = 0, F(1) = 1로 초기화

    def fibo(self, n):
        if n in self.memo:
            return self.memo[n]
        
        # 재귀 대신 for문 사용
        for i in range(2, n + 1):
            self.memo[i] = (self.memo[i-1] + self.memo[i-2]) % 1234567
        
        return self.memo[n]

def solution(n):
    fn = F()  # F 클래스의 인스턴스를 생성
    return fn.fibo(n)  # n번째 피보나치 수를 반환

 

6. 다른 사람의 풀이 - Python

 이렇게 간단할 수가.. a는 F(n-1), b는 F(n)으로 생각하고 2부터 n까지의 범위를 순회하며 a에는 b를 할당하고, b에는 현재 피보나치 수를 계산한 값을 할당한다. 이미 계산한 값이면 기존 값을 사용하고 기존에 없는 값이면 새로 계산한 값을 할당 후 for문이 끝났을 때의 b값을 반환한다. 

def solution(n):
    memo = {0: 0, 1: 1}
    MOD = 1234567
    
    a, b = 0, 1 # a = F(n-1), b = F(n)
    for i in range(2, n + 1):
    	# 이미 계산한 값이면 기존 값 사용
    	if i in memo:
            a, b = b, (memo[i]) % MOD
        
        # 기존에 없는 값이면 새로 계산
        a, b = b, (a + b) % MOD
    
    return b

 

 

7. 네 번째 풀이 - Java 

import java.util.*;

class Solution {
    public int solution(int n) {
        int MOD = 1234567; 
        int a = 0, b = 1;
        Map<Integer, Integer> memo = new HashMap<>();
        
        for (int i = 2; i <= n; i ++) {
            if (memo.containsKey(i)) {
                a = b;
                b = memo.get(i) % MOD;
            }
            int temp = (a + b) % MOD;
            a = b;
            b = temp;
            memo.put(i, b);
        }
        return b;
    }
}

 

 

8. 개념 정리

• 메모이제이션
  • 중복된 계산을 피하기 위해 이전에 계산한 결과를 저장해두고, 필요할 때 저장된 값을 재사용하는 기법이다. 메모이제이션을 사용하면 동일한 계산을 반복하지 않아 효율적으로 문제를 해결할 수 있다.
  • 주로 해시테이블을 사용해서 구현한다.
  • 예를 들어, 피보나치 수열을 재귀적으로 계산할 때, 해시 테이블에 키와 값을 저장 후 계산해야 할 피보나치 수가 이미 해시테이블에 있다면 해당 값을 재사용하는 식이다.
  • 하지만 메모리에 특정 값을 저장하기 때문에 남용하면 오히려 성능을 저하시킬 수 있으니 주의해야 한다.

 

• MOD 계산
  • 피보나치 수와 같이 재귀적으로 수행해야하는 계산의 마지막 값의 나머지를 구해야 하는 경우, 매 계산 시 나머지 연산을 수행하는 것이 좋다. 큰 숫자를 다루는 과정에서 발생 가능한 스택 오버플로우나 처리 속도 지연을 방지하기 위해서!