![]()
24416 알고리즘 수업 - 피보나치 수 1 - 브론즈1 https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 그냥 하라는대로 따라가면 된다. 의사코드만 잘 구현하면 될듯 dp가 재귀호출보다 성능이 좋다는 걸 알려주려는 듯 하다 한 번 구한 값을 재활용하는 dp와 달리 필요할 때마다 계속 값을 구해야하는 재귀호출이 훨씬 성능이 나쁜 것을 알 수 있음 풀이 class Main { static int cnt1 = 0; static int ..
![]()
Dynamic programming(동적계획법)이란? 1950년대 Richard Bellman에 의해 개발된 알고리즘 패러다임 복잡한 문제를 더 간단한 하위 문제로 분해하여 단순화하는 것을 의미 간단한 문제의 해를 구하고, 이를 이용하여 복잡한 문제를 푼다 동적계획법 문제는 두 가지 특성을 가진다 1. 최적의 하위 구조 최적화 문제에 대한 솔루션이 해당 하위 문제에 대한 최적 솔루션의 조합으로 얻어낼 수 있다 작은 문제로 큰 문제를 해결할 때 사용되는 관계가 존재하고, 이를 함축적 순서라고 한다 2. 중첩되는 하위 문제 동적계획 알고리즘은 분할 정복 알고리즘과 구분된다 분할 정복 알고리즘은 해결이 어려운 문제를 분할하여 문제를 해결한다는 점에서 동적계획법과 비슷하지만 차이점이 존재한다. 동적계획법은 하위..
