Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처공통 부분 문자열 골드 5 📖 문제 최장 공통 부분 수열 문제로 str1의 i번째 문자와 str2의 j번째 문자가 공통이라면 (같다면)이전 문자까지 연속된 공통 부분 수열 + 1 (현재 공통 부분) 점화식LCS[i][j] = LCS[i-1][j-1] + 1; (i >= 1, j >= 1) 🔅 문제 풀이import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR..

🧫 문제 분석 ✔️ 출처LCS 골드 5 📖 문제 최장 공통 부분 수열로 알고리즘 시간에 배웠었다. 근데 배운거랑 직접 구현해본거랑 차이가 심한 것을 느꼈다. 이 문제를 못푸니 배낭문제도 못푼다. LCS에 대한 이해가 있었다면 배낭 문제를 쉽게 풀 수 있을 것이다.  현재 비교하는 두 문자가 같다면 이전 최장 공통 부분 수열 길이에 + 1을 하여 LCS를 갱신한다. 두 문자열의 길이를 각각 n과 m이라 할 때,DP 테이블 dp는 인덱스 i∈[0,n]  j∈[0,m] 범위를 기반으로 구성된다. i-1, j-1까지 진행 했을때 LCS 길이 + 현재 공통 문자가 나왔으므로 길이가 1 증가때문에 dp[i-1][j-1] + 1이 된다.  같지 않다면 dp[i-1][j], dp[i][j-1] 중 큰 값을 유지한다..