[알고리즘] 백준 9251 LCS -dp- 자바 코틀린

https://www.acmicpc.net/problem/9251

9251번: LCS

 

 

LCS란 Longest Common Subsequence 로 최장 부분 수열을 말합니다. 이전 dp 문제들에서도 부분 수열문제들을 풀었었는데 이번 문제는 하나의 문자열 또는 집합이 아닌 두개의 문자열 비교까지 했어야 했습니다.

 

풀다가 모르겠어서 다음 사이트를 참고하였습니다.

https://jaesungbong.tistory.com/21

백준 온라인 저지 LCS

https://ghkvud2.tistory.com/107

[백준 9251번] LCS :: 늦깎이 IT

 

그리고 학교에서 과제로 했었는데 그 이후로 알고리즘을 안해서인지 기억이 안나더라고요. 복습좀 해야겠습니다.

https://github.com/mtjin/University/tree/master/algorithm/8

mtjin/University

www.youtube.com/watch?v=nyXkaHUahHk

풀이는 다음과 같습니다. 중요하므로 꼭 기억하고 복습한번 해야겠습니다.

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        int[][] LCS = new int[a.length()+1][b.length()+1];
        for (int i=1; i<=a.length(); i++){
            for (int j=1; j<=b.length(); j++){
                if(a.charAt(i-1) == b.charAt(j-1)){
                    LCS[i][j] = LCS[i-1][j-1] + 1;
                }else {
                    LCS[i][j] = Math.max(LCS[i][j-1], LCS[i -1][j]);
                }
            }
        }
        System.out.println(LCS[a.length()][b.length()]);
    }

}

 

 

 

 

[2020-10-06 복습]

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line1 = sc.next();
        String line2 = sc.next();
        int[][] lcs = new int[line1.length() + 1][line2.length() + 1];
        for (int i = 1; i <= line1.length(); i++) {
            for (int j = 1; j <= line2.length(); j++) {
                if (line1.charAt(i - 1) == line2.charAt(j - 1)) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                } else {
                    lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
                }
            }
        }
        System.out.println(lcs[line1.length()][line2.length()]);
    }
}

import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val line1 = sc.next()
    val line2 = sc.next()
    val lcs = Array(line1.length + 1) { IntArray(line2.length + 1) }
    for (i in 1..line1.length) {
        for (j in 1..line2.length) {
            if (line1[i - 1] == line2[j - 1]) {
                lcs[i][j] = lcs[i - 1][j - 1] + 1
            } else {
                lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1])
            }
        }
    }
    println(lcs[line1.length][line2.length])
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!