[Java] 백준 9251번 : LCS <Gold 5>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

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

9251번: LCS

Code

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    void run() throws IOException {
        String first = bf.readLine();
        String second = bf.readLine();
        first = '0'+first;
        second = '0'+second;
        int[][] str = new int[first.length()][second.length()];

        for(int i = 1; i < first.length(); i++){
            for(int j = 1; j < second.length(); j++){
                if(first.charAt(i) == second.charAt(j)) {
                    str[i][j] = str[i - 1][j - 1] + 1;
                }else{
                    if(str[i-1][j] > str[i][j-1]){
                        str[i][j] = str[i-1][j];
                    }else{
                        str[i][j] = str[i][j-1];
                    }
                }
            }
        }

        System.out.println(str[first.length()-1][second.length()-1]);
    }

    public static void main(String[] args) {
        Main my = new Main();
        try{
            my.run();
        }catch(Exception e){}
    }

}

---

Code 필수 요소

1. Dynamic Programming(동적 프로그래밍) 사용

2. 규칙 찾기

 

// Dynamic Programming(동적 프로그래밍) 사용

한동안 계속해서 풀 예정인 Dynamic Programming문제의 핵심은 이 문제가 Dynamic Programming을 사용해야 한다는 것을 깨닫는 것이다. 

 

// 규칙 찾기

LCS알고리즘을 사용해야 한다.

 

LCS알고리즘이란?

조만간 LCS알고리즘 관련 글 업로드 해서 자세히 설명하겠다.

먼저 간단하게 설명하자면, LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다. 우리가 알고 있는 substring과 비교하면 substring은 연속된 부분 문자열이고 subsequence는 연속적이지는 않은 부분 문자열이다.

Ex)

ABCDEF

BCGEHF

Substring : BC

Subsequence : BCEF

 

이 특성을 활용해서 이전에 나왔다면 메모이제이션 해주고, 값들에 변화를 주면 된다.

 

https://naemamdaelo.tistory.com/35

알고리즘 - LCS (Longest Common Subsequence)

 

// 전체적 설명

LCS알고리즘을 잘 알고있냐를 묻는 문제.

 

동적 계획법이란? 

https://naemamdaelo.tistory.com/27

알고리즘 - Dynamic Programming(동적 계획법)

 

 

너 무 어 렵 다

 

-꿑-