🔍 문제링크https://www.acmicpc.net/problem/10844📌 문제 요약길이가 N인 계단 수의 개수를 구하는 문제이다.계단 수는 인접한 자리의 숫자 차이가 항상 1이어야 한다.첫 번째 자리는 0이 될 수 없다.정답을 1,000,000,000으로 나눈 나머지를 출력🛠 풀이 및 알고리즘DP 배열 정의`dp[i][j]`: 길이가 i이고 마지막 숫자가 j일 때 계단 수의 개수`dp[1][0] = 0` (첫 자리가 0이면 안됨)`dp[1][1] ~ dp[1][9] = 1` (한 자리 계단 수는 자기 자신)점화식 `dp[i][0] `= `dp[i+1][1]` (0은 이전 자리가 1인 경우만 가능)`dp[i][9]` = `dp[i-1][8]` (9는 이전 자리가 8인 경우만 가능)`dp[i][..

🔍 문제링크https://www.acmicpc.net/problem/2624📌 문제 요약목표 금액 n을 만들기 위해 k가지 종류의 동전이 주어진다.각 동전은 개수 제한이 있음.주어진 동전을 사용하여 목표 금액을 만드는 방법의 수를 구하는 문제🛠 풀이 및 알고리즘1️⃣ DP(동적 계획법) 활용dp[i] : i원을 만드는 경우의 수배낭 문제와 비슷한 접근 방식을 사용하여 동전의 개수 제한을 고려2️⃣ 점화식 유도기본적인 동전 문제는 개수 제한 없이 무한히 사용할 수 있는 경우→ dp[j] += dp[j - amount]그러나 이 문제는 개수 제한이 존재→ s개의 동전을 사용하는 경우를 고려해야 함for (int s = 1; s dp[j]는 현재 금액 j를 만들기 위해 s개의 동전을 사용했을 때 경우의 ..

🔍 문제링크https://www.acmicpc.net/problem/2225📌 문제 요약0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는  경우의 수를 구하는 문제.순서가 달라도 같은 경우로 인정 (1+2와 2+1은 같은 경우).한 개의 수를 여러 번 쓸 수 있음( 1+1 )결과를 1,000,000,000으로 나눈 나머지를 출력, 🛠 풀이 및 알고리즘dp[k][n] 정의`dp[k][n]`: n을 k개의 정수로 만드는 방법의 수.초기값 설정`dp[1][n] = 1` → 하나의 숫자로 n를 표현하는 방법은 1개 (n 자체).`dp[k][0] = 1` → 0을 k개로 만드는 방법은 0 + 0 + ... + 0 하나뿐.점화식 (DP)`dp[k][n] = dp[k-1][n] + dp[k][n-1]``d..

🔍 문제링크https://www.acmicpc.net/problem/9251📌 문제 요약두 문자열 str1과 str2가 주어졌을 때, 최장 공통 부분 수열(LCS: Longest Common Subsequence)의 길이를 구하는 문제.LCS는 연속되지 않아도 됨 -> 순서만 유지하면 됨.ACAYKP, CAPCAK에서는 `ACAK`가 LCS🛠 풀이 및 알고리즘dp[i][j] 정의dp[i][j]: `str1[0:i]`와 `str2[0:j]`의 LCS 길이.점화식 (DP)문자가 같으면 `dp[i][j] = dp[i-1][j-1] + 1`-> 두 문자가 같다면 이전 LCS 길이에 1증가.문자가 다르면 `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`-> 이전 문자열 중 더 긴 LC..

🔍 문제링크https://www.acmicpc.net/problem/11054📌 문제 요약바이토닉 수열: 증가했다가 감소하는 형태의 수열수열에서 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제.증가하는 부분 수열(LIS)과 감소하는 부분 수열(LDS)을 결합하여 해결🛠 풀이 및 알고리즘dp1[i]: nums[i]를 마지막 원소로 하는 가장 긴 증가 부분 수열 (LIS).dp1[i] = max(dp1[i], dp1[j] + 1) (nums[i] > nums[j])dp2[i]: nums[i]를 첫 원소로 하는 가장 긴 감소 부분 수열 (LDS).dp2[i] = max(dp2[i], dp2[j] + 1) (nums[i] > nums[j])바이토닉 부분 수열의 길이 계산dp1[i] + dp2[i] - 1..

🔍 문제링크https://www.acmicpc.net/problem/11053https://www.acmicpc.net/problem/11722📌 문제 요약1️⃣ 백준 11053 - 가장 긴 증가하는 부분 수열 (LIS)수열에서 "증가하는 부분 수열" 중에서 가장 긴 길이를 찾는 문제.2️⃣ 백준 11722 - 가장 긴 감소하는 부분 수열 (LDS)수열에서 "감소하는 부분 수열" 중에서 가장 긴 길이를 찾는 문제.🛠 풀이 및 알고리즘dp[i] 정의dp[i]는 nums[i]를 마지막 원소로 하는 증가/감소 수열의 최장 길이.점화식 (DP)LIS (Longest Increasing Subsequence)dp[i] = max(dp[i], dp[j] + 1) (단, nums[i] > nums[j])LDS ..

🔍 문제링크https://www.acmicpc.net/problem/1003📌 문제 요약fibonacci(n)을 호출할 때 0과 1이 몇 번 출력되는지 계산하는 문제.fibonacci(3) 호출 시,fibonacci(3) → fibonacci(2) + fibonacci(1)fibonacci(2) → fibonacci(1) + fibonacci(0)0은 1번, 1은 2번 호출됨.🛠 풀이 및 알고리즘dp[n][0]과 dp[n][1]을 사용하여 n일 때 0과 1의 호출 횟수를 저장dp[n][0]: fibonacci(n)에서 0이 호출된 횟수.dp[n][1]: fibonacci(n)에서 1이 호출된 횟수.재귀 + 메모이제이션(DP) 활용한 번 계산한 값은 저장하여 중복 연산 방지.반복문 방식으로 n ≤ 4..