말하는대로

🧠 TIL - DP로 N초 동안 가능한 스킬 조합 수 구하기 오늘은 스킬의 사용 시간 제약이 있는 조합 문제를 DP로 해결해봤다. 핵심은 dp[i]가 “i초를 채우는 방법의 수”를 의미한다는 점이다. 📌 문제 요약 스킬 A: 1초 스킬 B: m초 총 N초를 정확히 채울 수 있는 모든 조합의 수를 구하라 결과는 1,000,000,007로 나눈 나머지 출력 📄 핵심 점화식 dp[i] = dp[i - 1] + dp[i - m] (단, i ≥ m) 🔍 코드 설명 nanoom = 1_000_000_007dp = [0] * (n + 1)dp[0] = 1 # 0초는 아무 것도 안 쓰는 1가지 방법for i in range(1, n + 1): dp..

🧮 백준 14495번: 피보나치 비스무리한 수열오늘은 피보나치를 DP로 풀어내는 문제를 풀어볼 거에요.🧩 피보나치 수열?피보나치 수열이란 첫째, 둘째 항이 1이고 그 뒤의 항은 바로 앞의 두 항의 합인 수열입니다.F(n): 1, 1, 2, 3, 5, 8, 13, ...일반적으로 피보나치를 구하는 알고리즘을 코드로 구현할 때는 재귀함수를 사용합니다.def fivo(n): if n 이렇게 재귀함수로 피보나치 수열을 구할 경우 시간복잡도는 O(2^N) 이 됩니다.해당 시간복잡도는 O(n^2)보다도, n^3보다도 성능이 좋지 않습니다.그래서 우리는 이 경우를 피하기 위해, 그리고 DP를 배우기 위해 피보나치를 DP로 구현하게 됩니다.💡 DP(다이나믹 프로그래밍 | 동적 계획법)?자료들이 생각보다 많은..