기록하는 습관 "기습"

문제 설명길이가 N인 계단 수의 개수를 구하는 문제이다. 계단 수란, 0으로 시작하지 않으며, 인접한 모든 자리의 차이가 정확히 1인 수를 의미한다. 예를 들어, N=2일 때 가능한 계단 수는 다음과 같다. 길이 2의 계단 수: 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 총 개수는 17개이다. 🔹 문제 요구사항N이 주어졌을 때, 길이가 N인 계단 수의 개수를 10^9로 나눈 나머지를 출력해야 한다. 문제 풀이동적 계획법과 재귀를 이용해 해결해야 한다.동적 계획법(DP)과 메모이제이션의 활용DP 테이블의 정의dp[loc][val]dp[loc][val]_은 **길이가 loc이고 마지막 자릿수가 val인 계단 수의 개수_를..

동적 프로그래밍 큰 문제에는 닮은 꼴의 작은 문제가 깃들기도 한다. 이를 해결한 것이 재귀적 알고리즘인데, 이 알고리즘은 잘 쓰면 효율적인 보약이지만 잘못 쓰면 치명적인 맹독이다. 재귀적 알고리즘 자체가 심한 중복 호출을 불러올 수 있기 때문이다. 이를 해결하기 위한 방법이 동적 프로그래밍이다. 심한 중복 호출이 일어나는 경우는 피보나치 수열과 행렬곱셈 최적순서 구하기가 있다. 이에 대해 알아보자. 피보나치 수 구하기 피보나치 수열의 정의는 다음과 같다. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 이를 프로그램으로 구현하면 fib(n) { if (n = 1 or n = 2) then return 1; else return (fib(n-1) +fib(n-2)); } 여기서 수가 ..