알고리즘 공부/문자열
백준 9251번 with Kotlin
_우지
2021. 9. 2. 11:05
LCS
시간 제한메모리 제한제출정답맞은 사람정답 비율
| 1 초 | 256 MB | 38775 | 16009 | 11724 | 40.549% |
문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
예제 입력 1 복사
ACAYKP CAPCAK
예제 출력 1 복사
4
출처
- 문제를 만든 사람: baekjoon
- 데이터를 추가한 사람: qpwoeiruty
|
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
|
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Integer.max
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main()=with(br){
val str1 = readLine()
val str2 = readLine()
val lcs = Array(str1.length+1,{IntArray(str2.length+1,{0})})
for(i in 1 until str1.length+1){
for(j in 1 until str2.length+1){
if(str1[i-1]==str2[j-1]){
lcs[i][j] = lcs[i-1][j-1]+1
}
else{
lcs[i][j] = max(lcs[i][j-1],lcs[i-1][j])
}
}
}
bw.write("${lcs[str1.length][str2.length]}")
bw.flush()
bw.close()
}
|
cs |
[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence
LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.
velog.io
https://happylsm76.tistory.com/entry/%EB%B0%B1%EC%A4%80-9251%EB%B2%88LCS-with-Python