군만두의 IT 공부 일지

✅문제: 11057번📌문제풀이0부터 9까지의 숫자로 이루어진 오르막 수의 개수를 계산하는 문제임. 오르막 수는 각 자릿수가 이전 자릿수 이상인 수를 의미하며, n자리 오르막 수의 개수를 동적 계획법(DP)을 사용하여 계산함.DP 배열 초기화dp[i][j]: i자리 오르막 수 중 마지막 숫자가 j인 경우의 수를 저장하는 배열.초기값: dp[1][j] = 1: 한 자리 수는 0부터 9까지 각각 1개임.점화식dp[i][j]: i자리 오르막 수에서 마지막 자릿수가 j인 경우를 구하기 위해, 이전 자릿수에서 0부터 j까지의 값을 더함.dp[i][j] = dp[i−1][0] + dp[i−1][1] + ⋯ + dp[i−1][j]결과 계산모든 계산은 10007로 나눈 나머지를 저장함.n자리 오르막 수의 총 개수는 d..

✅문제: 17218번 📌개념정리(1) 동적 프로그래밍(Dynamic Programming)정의: 복잡한 문제를 간단한 하위 문제로 나누어 해결하고, 이를 통해 중복 계산을 최소화하는 방법서브문제의 결과를 저장하고 재사용함으로써 계산 시간을 효율적으로 단축함.(2) 최장 공통 부분 수열(Longest Common Subsequence, LCS)정의: 두 시퀀스에서 순서를 유지하면서 둘 모두의 부분 수열이 되는 가장 긴 수열을 찾는 문제LCS는 문자열 비교, 데이터 동기화, 생물학적 서열 분석 등 다양한 분야에서 활용됨.📌문제풀이두 문자열 사이의 최장 공통 부분 수열을 구하는 문제임. 각 문자열을 순차적으로 비교하면서 공통 문자를 발견할 때마다 결과 문자열에 추가함.1. 두 문자열의 길이에 대한 2차원 ..