LCS

📖 문제 https://www.acmicpc.net/problem/1958   💡  풀이 방식• LCS문자열이 3개이므로, 3차원 DP로 LCS 길이를 구하면 된다. - 3중 for문을 이용해 i == j == k인 지점을 찾아 갯수를 센다.(i, j, k) = max( (i-1, j, k), max( (i, j-1, k), (i, j, k-1) ) )   🔺 코드123456789101112131415161718192021222324252627282930313233import java.util.*;import java.io.*; public class Main {    static int[][][] dp;    // 3차원 DP    static char[] A,B,C;        public s..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🔺 해결 아이디어 1) 최장 공통 부분 수열 LCS (DP) • 최소 편집 거리로 두 문자열 같게 만들기 = A에서 삭제를 진행해 A와 B의 LCS를 만들고, 삽입을 진행해 B를 만드는 것 - dp[i][j] : 문자열 A의 i번째까지와 문자열 B의 j번째까지를 활용해 만들 수 있는 LCS 길이 • 삭제 횟수 = A 길이 - LCS 길이 • 삽입 횟수 = B 길이 - LCS 길이 ➡ 정답 = 삭제 횟수 + 삽입 횟수 2) 최소 편집 거리 String Matching (DP) 활용 ✅ - dp[i..

📍 정의 및 특징 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제 - DP의 일종 - 문제 유형 : 최장 공통 부분 수열 길이 구하기, 최장 공통 부분 수열 구하기 #DP 📍 필요 변수 ✔ 2차원 LCS 배열 - LCS 길이 찾기용 ✔ 2차원 result 배열 - LCS 배열 결과값 저장용 📍 실행 과정 Case 1) 최장 공통 부분 수열 "길이" 찾기 /* LCS 길이 구하기 */ if(i == 0 || j == 0) LCS[i][j] = 0; else if (ch1[i] == ch2[j]) LCS[i][j] = LCS[i - 1][j - 1] + 1; else LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]) 문자열 A와 B를 한 ..

🔺 문제 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffered..

🔺 문제 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 import java.util.*; import java.io.*; public clas..