피보나치

[BOJ/Java] 2748_피보나치 수 2 || Dynamic Programing

2748번: 피보나치 수 2피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net문제 설명더보기피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을..

[BOJ/Python] 2747_피보나치 수 || 구현(Implementation)

2747번: 피보나치 수피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net문제 설명더보기피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때..

[Algorithm] DP(Dynamic Programming), 동적 계획법

다이나믹 프로그래밍(Dynamic Programming)은 동적 계획법이라고도 불린다. 이 알고리즘은 똑같은 연산을 계속 반복하지 않고, 한 번의 풀이만으로 해결하고자 하는 알고리즘이다. 큰 문제 하나를 여러 개의 작은 문제로 나누어서 해결하고자 하는 방법이다. ❗ 분할 정복 vs. 다이나믹 프로그래밍 둘의 공통점은 큰 문제 하나를 여러 개의 작은 문제로 나누어서 해결한다는 것이다. 분할 정복과 다이나믹 프로그래밍의 차이점은 DP의 경우, 나누어진 부분 문제가 중복되기 때문에, 재활용할 수 있다는 것이다. 분할 정복의 경우, 나누어진 부분 문제가 중복되지 않는다. ❗ 탑다운(Top-Down) vs. 바텀업(Bottom-Up) 탑다운 방식은 큰 문제를 해결하기 위해서 작은 문제를 호출하며 풀어나가는 방식 ..