백준 1003번
내가 처음으로 풀어본 백준 문제다.
아니 지금 24살인데 처음 풀어본다고..? (...)
군대 갔다오기 전 들은 c++ 수업을 다 까먹어서 지금 이러고 있다..
처음엔 그냥 피보나치 수열을 살짝 꼬아놨군 이라고 생각해서 그냥 바로 global variable 만들어가지고
int zero_count = 0;
int one_count = 0;이렇게 했는데 어? 안되네? 왜 시간 초과??
당황한 나는 문제 분류를 보았고 다이나믹 프로그래밍이라고 적혀있는 것을 보고 이게 뭐지 싶었다. 배운적 있나? 찾아보니 없다..
Dynamic Programming이란 무엇인가? 내가 여기저기 읽어보고 정리한 바는 다음과 같다.
어떤 문제 해결을 위해서, 문제를 작은 문제로 나눈 뒤 그 해답을 재활용하는 기법이다.
Dynamic.. 계속 생각하다 보니 왜 Dynamic이라는 이름이 붙은 것인지 궁금해졌다. Dynamic에 대해서 이해하려면 역시 Static 또한 알아야 한다.
Static은 말 그대로 정적, 이미 정해져 있다는 뜻이다. Compile time에 fixed / bounded 되어 있다고 생각하면 된다.
그렇다면 Dynamic은 반대로 이해하면 된다. Complie time에서 fixed / bounded 되어 있지 않은 것이다. 즉 언제나 바뀔 수 있는 것이고, 이는 우리가 익히 알고 있는 Dynamic의 의미와 통하므로 이제서야 이해가 된다. 아하!
그럼 빠르게 1003번 문제로 넘어가 보자.
이 문제는 시간 제한이 걸려 있어 Static 하게 접근하면 무조건 시간 제한에 걸린다. Dynamic하게 접근하면 그냥 바로 풀린다. Dynamic Programming에서 문제를 잘게 쪼개는 것이 가장 중요하고, 이를 우리는 Recursion이라고 알고 있으며, 이 분야의 대표적 예시는 당연히 피보나치 수열이다.
이 문제에서 요구하는 "f(0)"과 "f(1)"의 호출 횟수는 몇 번 적어보면 감이 온다.
위 그림을 보면 알 수 있듯이 호출 횟수 역시 피보나치 수열을 따르므로 그냥 피보나치 수열 D.P로 하나 짠 다음 출력하면 끝! 코너 케이스 조심해서 짜면 오케이!
내 코드
#include <iostream>
#include <vector>
using namespace std;
int fibonacci(int n) {
if (n == -2) return 1;
if (n == -1) return 0;
if (n == 0 || n == 1) {
return 1;
}
vector<int> dp(n + 1, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
int main() {
int T = 0;
cin >> T;
int n = 0;
for (int i = 0; i < T; i++) {
cin >> n;
cout << fibonacci(n - 2) << " " << fibonacci(n - 1) << "\n";
}
}