9251: LCS(JAVA)

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

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

코드 설명

• fir : 첫번째 문자열
  • firLen : fir의 길이

• sec : 두번째 문자열
  • secLen : sec의 길이

• lcs : LCS를 구현한 함수
  • LCS란?

    Longest Common subsequence : 최장 공통 부분 서열

    두 서열이 주어졌을 때 두 서열 중 공통인 부분 서열 중 가장 길이가 긴것

    example

    ACAYKP

    CAPCAK

    ⇒ ACAK (최장공통부분서열)

  public static int lcs(char[] fir, char[] sec,int firLen, int secLen){
          int[][] lcs = new int[firLen+1][secLen+1];
          for(int i =0;i<=firLen;i++){
              for(int j =0; j<=secLen; j++){
                  if(i == 0|| j == 0){
                      lcs[i][j] = 0;
                  } else if (fir[i-1] == sec[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]);
                  }
              }
          }
          return lcs[firLen][secLen];
      }

---

문제풀이(그림ver)

---

전체코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] fir = br.readLine().toCharArray();
        int firLen = fir.length;
        char[] sec = br.readLine().toCharArray();
        int secLen = sec.length;
        int ans = lcs(fir,sec,firLen,secLen);
        System.out.println(ans);
    }
    public static int lcs(char[] fir, char[] sec,int firLen, int secLen){
        int[][] lcs = new int[firLen+1][secLen+1];
        for(int i =0;i<=firLen;i++){
            for(int j =0; j<=secLen; j++){
                if(i == 0|| j == 0){
                    lcs[i][j] = 0;
                } else if (fir[i-1] == sec[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]);
                }
            }
        }
        return lcs[firLen][secLen];
    }
}

---

고찰

LCS문제는 전형적인 틀이 존재하는 문제이다. 이전 전공수업때 LCS에 대한 풀이를 이해하는데 어려움이 있었으나, 풀이 순서만 이해해도 함수는 고정이기에 쉽게 해결할 수 있다.

Uploaded by N2T