Dynamic ProgramingDynamic Programing(DP)는 복잡한 문제를 작은 부분 문제(sub problem)로 나누고,그 결과를 저장하여 재활용하는 방식으로 문제를 푸는 알고리즘 기법이다. 즉, DP는 큰 문제를 작은 부분 문제로 쪼개고, 그 답을 저장해가면서 큰 문제를 푸는 방법이다. DP가 필요한 이유단순 재귀의 한계 (중복 계산)같은 부분 문제를 여러 번 푸는 비효율 → 예: 피보나치 수열에서 fib(3)이 중복 호출 됨. 시간 복잡도 개선DP를 쓰면 한 번 계산한 결과를 저장해서 O(N) 수준으로 줄일 수 있음. DP의 두 가지 핵심 조건중복되는 부분 문제 (Overlapping Subproblems)큰 문제를 해결하는 과정에서 동일한 작은 문제가 반복적으로 등장해야 함. 최..

https://www.acmicpc.net/problem/1904피보나치수열 문제와 비슷하지만, 재귀(Top-down)하를 사용하지 않고동적 계획법(DP; Dynamic Programing) 기법 중 하나인Bottom-up을 사용하여 해결해야한다.▷ 풀이한 키워드동적 계획법(DP)Bottom-up▷ Bottom-up위(큰 문제)에서 아래(작은 문제)로 내려가는 Top-down(재귀)와 반대로,작은 문제부터 차근차근 쌓아 올려서 큰 문제를 푸는 방법. DP에서 흔히 쓰이는 방식으로,기저 조건(Base Case)에서 출발해서 (ex; 피보나치의 f(0), f(1) )반복문으로 위로 계산해나간다. ( f(3) f(4) .... f(n) ) ▷ 전체 코드import sysinput = sys.stdin.re..