문제 : https://www.acmicpc.net/problem/1003
코드(자바) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.java
코드(파이썬) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.py
코드 (C#) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.cs
Memoization 개념에 대해 익힐 수 있는 아주 좋은 문제이다. 피보나치의 경우 문제에 제시된 기본적인 방식으로 짜게 되면 재귀적으로 호출되는 함수가 기하급수적으로 늘어난다. ->O(2^N)
이 때, 이미 계산된 피보나치 수에 대해 Memoization을 통해 저장해두면 기하급수적으로 늘어나던 함수 호출이 엄청나게 줄어든다. -> O(N)
문제에 제시된 코드를 살짝 바꿔 Memoization을 적용시킨 코드는 다음과 같다.
int fibonacci(int n) {
if (memoization[n] != -1)
return memoization[n];
if (n == 0) {
printf("0");
return 0;
} else if (n == 1) {
printf("1");
return 1;
} else {
return memoization[n] = fibonacci(n‐1) + fibonacci(n‐2);
}
}
그리고 위 함수 구조를 벗어나 DP로도 풀 수 있는데, 올려둔 코드는 모두 DP로 푼 경우이다. DP로 푼 경우도 O(N) 이므로 별다른 차이는 없다.
사실 피보나치 최적화에는 하나가 더 있는데, 행렬을 이용해 계산하는 방식이다. 이 경우 위의 모든 경우보다 더 빠르게 계산을 할 수 있지만, 사실 너무 대회를 위한 알고리즘 같은 느낌이라 크게 알 필요는 없을 것 같다. 나중에 생각나면 따로 피보나치 최적화에 대해 써봐야겠다.
'PS > BOJ' 카테고리의 다른 글
백준 22728 자바 - Amida, the City of Miracle (BOJ 22728 JAVA) (0) | 2021.10.30 |
---|---|
백준 1004 자바 - 어린 왕자 (BOJ 1004 JAVA) (0) | 2021.10.29 |
백준 2696 자바 - 중앙값 구하기 (BOJ 2696 JAVA) (0) | 2021.10.29 |
자바 6137 자바 - 문자열 생성 (BOJ 6137 JAVA) (0) | 2021.10.29 |
백준 3409 자바 - 문자 방정식 (BOJ 3409 JAVA) (0) | 2021.10.28 |
댓글