🔺 문제
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
'코테 > 백준' 카테고리의 다른 글
| [백준/JAVA] 15649번: N과 M (1) (0) | 2023.06.05 |
|---|---|
| [백준/JAVA] 1874번: 스택 수열 (0) | 2023.06.04 |
| [백준/JAVA] 2565번: 전깃줄 (0) | 2023.06.04 |
| [백준/JAVA] 11054번: 가장 긴 바이토닉 부분 수열 (0) | 2023.06.04 |
| [백준/JAVA] 12865번: 평범한 배낭 (0) | 2023.06.03 |
