기록하는 습관 "기습"

https://www.acmicpc.net/problem/9184문제 설명재귀 함수를 사용해 정의된 함수 w(a, b, c) 를 효율적으로 계산하는 문제를 해결한 코드이다.해당 함수는 다음과 같은 규칙을 따른다.기저 조건:만약 a, b, c 중 하나라도 0 이하이면, w(a, b, c) = 1이다.상한 조건:만약 a, b, c 중 하나라도 20보다 크면, w(a, b, c) = w(20, 20, 20)로 계산한다.특수 조건:만약 a 그리고 b 인 경우,w(a, b, c) = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)로 계산한다.일반 조건:위의 조건에 해당하지 않는 경우,w(a, b, c) = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b,..

문제 설명길이가 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인 계단 수의 개수_를..

동적 프로그래밍동적 프로그래밍에 대해서 다시금 공부하고 있다. 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제들로 나누어 해결한 후, 그 결과를 저장하여 재사용함으로써 문제 해결의 효율성을 높이는 기법이다. 이는 주로 하위 문제가 반복해서 나타나는 경우에 사용되며, 각 하위 문제의 결과를 기록(memoization)하거나 테이블 형식으로 정리하여 중복 계산을 방지한다. DP는 최적화 문제에서 자주 사용되며, 두 가지 주요 접근 방식이 있다: 상향식(Bottom-Up)과 하향식(Top-Down). 단순히 말하자면, 동적 프로그래밍은 "이전에 계산한 값을 저장해 두었다가 필요할 때 재사용하는 방법"이다. 이는 중복 계산을 줄이고 문제를 더 빠르게 해결할 수 있..