-
99클럽(3기) - 코테스터디 9일차 TIL # DPAlgorithm 2024. 8. 13. 00:22
프로그래머스 - 피보나치 수
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 계산
- 피보나치 수와 같이 재귀적으로 수행해야하는 계산의 마지막 값의 나머지를 구해야 하는 경우, 매 계산 시 나머지 연산을 수행하는 것이 좋다. 큰 숫자를 다루는 과정에서 발생 가능한 스택 오버플로우나 처리 속도 지연을 방지하기 위해서!
'Algorithm' 카테고리의 다른 글
[LeetCode] 436. Find Right Interval # Binary Search (0) 2024.09.08 [프로그래머스] 전화번호 목록 # Hash (0) 2024.09.08 99클럽(3기) - 코테스터디 6일차 TIL # 이분탐색 (0) 2024.08.04 99클럽(3기) - 코테스터디 5일차 TIL # 이분탐색 (0) 2024.08.04 99클럽(3기) - 코테스터디 4일차 TIL # 정렬 (0) 2024.08.03