728x90
public class Main {
public static void main(String[] args) {
String x = "abcdedc";
String y = "bbbcec";
int c[][] = new int[x.length()][y.length()];
String lcs[][] = new String[x.length()][y.length()];
for(int i = 0;i< lcs.length;i++)
for(int j = 0;j<lcs[i].length;j++)
lcs[i][j] = "";
for(int i = 1; i < x.length();i++)
{
for(int j = 1;j < y.length();j++)
{
if(x.charAt(i) == y.charAt(j))
{
c[i][j] = c[i-1][j-1]+1;
lcs[i][j] = lcs[i-1][j-1] + x.charAt(i);
}
else
{
if(c[i-1][j] > c[i][j-1])
{
c[i][j] = c[i-1][j];
lcs[i][j] = lcs[i-1][j];
}
else
{
c[i][j] = c[i][j-1];
lcs[i][j] = lcs[i][j-1];
}
}
}
}
System.out.println(c[x.length()-1][y.length()-1]);
System.out.println(lcs[x.length()-1][y.length()-1]);
/*결과 :
4
bcec
*/
}
}
동적 프로그래밍 사용
728x90
'Algorithm > 알고리즘 설명' 카테고리의 다른 글
[알고리즘] 위상 정렬 (Topological Sorting) (0) | 2020.09.17 |
---|---|
[알고리즘] 이분 탐색 (Binary Search) (0) | 2020.08.31 |
[알고리즘] 최대공약수, 최소공배수 구하기 (0) | 2020.08.22 |
[알고리즘] 각 자리 수의 합 구하기 (0) | 2020.08.22 |
[알고리즘] 문자열 → int 형 변환 (0) | 2020.08.22 |
댓글