[백준/JAVA] 9251번: LCS
🔺 문제
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 BufferedReader(new InputStreamReader(System.in));
char[] c1 = br.readLine().toCharArray();
char[] c2 = br.readLine().toCharArray();
int len1 = c1.length;
int len2 = c2.length;
int[][] dp = new int[len1 + 1][len2 + 1];
for(int i = 1 ; i <= len1 ; i++) {
for(int j = 1 ; j <= len2 ; j++) {
if(c1[i - 1] == c2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
System.out.println(dp[len1][len2]);
}
}
|
cs |
✅ 해결 아이디어
✔ DP(Bottom-Up)
- LCS : 유사도
🔺 다른 풀이들
- 설명 굿..
[백준알고리즘-JAVA]9251번 풀이(LCS) - 초보도 이해하는 풀이
안녕하세요 인포돈 입니다. 백준 알고리즘 9251번 풀이입니다. * 참고사항 - 개발환경은 eclipse을 기준으로 작성되었습니다. - java언어를 이용하여 문제를 풀이합니다. - 알고리즘 문제는 풀이를 보
infodon.tistory.com
💬 느낀 점
이제 LIS, LDS, LCS는 좀 감이 잡혔다고 한다....
다른 블로거 분들 너무너무 감사합니다....
이로써 일단 이번 일주일간 <동적 계획법 1> 1회독 끝...
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 240319 |
(참고)
✔ 항상 무한한 감사를 드리는.. 풀이 참고 & 복습용 굿.
[백준] 9251번 : LCS - JAVA [자바]
www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAP
st-lab.tistory.com
✔ LCS 정리 글
[알고리즘] 최장 공통 부분 수열 LCS - DP & 이진탐색 LIS (Java)
최장 공통 부분 수열 LCS (Longest Common Subsequence) LCS(Longest Common Subsequence)는 LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 나타내지만 최장 공통 문자열(Longest Common Substring)을 말하기도 한다
loosie.tistory.com