갓생사는 김초원의 개발 블로그
chocho_log
갓생사는 김초원의 개발 블로그
전체 방문자
오늘
어제
  • 분류 전체보기 (77)
    • 개발 (22)
      • Spring (4)
      • Java (3)
      • Database (2)
      • Elasticsearch (3)
      • ETC (3)
      • JPA (3)
      • 이슈 (1)
    • 코딩 테스트 (43)
      • 프로그래머스 (23)
      • 백준 (12)
      • TIP (8)
    • 자료구조 (2)
    • 알고리즘 (4)
    • 잡생각 (0)
    • 경험 (5)
      • AWS re:Invent 2024 (5)

블로그 메뉴

    공지사항

    인기 글

    태그

    • jpa
    • Spring Boot Embedded Tomcat
    • 지연로딩
    • Lazy Loading
    • jar
    • 디자인패턴 #SOLID 원칙
    • war
    • querydsl

    최근 댓글

    최근 글

    갓생사는 김초원의 개발 블로그

    chocho_log

    코딩 테스트/백준

    [백준][gold5] 9251번: LCS - JAVA

    2021. 5. 9. 15:49

    [문제]

    www.acmicpc.net/problem/9251

     

    9251번: LCS

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

    www.acmicpc.net

     

    대학교 알고리즘 수업때 들었지만 기억이 가물가물했다. 

    아래 유튜브를 보면서 다시 공부했다. 

    www.youtube.com/watch?v=EAXDUxVYquY

     

    [코드]

    package com.algorithm.baekjoon.gold5;
    
    import java.io.*;
    
    /**
     * 9251 - LCS
     */
    public class Test04 {
        public static int[][] LCS;
    
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
            String X = br.readLine();
            String Y = br.readLine();
    
            int xLen = X.length();
            int yLen = Y.length();
    
            LCS = new int[xLen + 1][yLen + 1];
    
            getLCS(X, Y);
            bw.write(LCS[xLen][yLen] + "\n");
    
            br.close();
            bw.flush();
            bw.close();
        }
    
        public static void getLCS(String X, String Y) {
            for (int i = 1; i < LCS.length; i++) {
                for (int j = 1; j < LCS[0].length; j++) {
                    if (X.charAt(i - 1) == Y.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]);
                    }
                }
            }
        }
    }
    

    '코딩 테스트 > 백준' 카테고리의 다른 글

    [백준][Gold5]1107 - 리모컨 -JAVA  (0) 2021.05.20
    [백준][Gold5] 12865 - 평범한 배낭 - JAVA  (0) 2021.05.16
    [백준][gold5] 14502번: 연구소 - JAVA  (0) 2021.05.08
    [백준][Gold1]11401-이항계수3-JAVA  (0) 2021.04.27
    [백준][Gold1] 구간 합 구하기 - JAVA  (0) 2021.04.13
      '코딩 테스트/백준' 카테고리의 다른 글
      • [백준][Gold5]1107 - 리모컨 -JAVA
      • [백준][Gold5] 12865 - 평범한 배낭 - JAVA
      • [백준][gold5] 14502번: 연구소 - JAVA
      • [백준][Gold1]11401-이항계수3-JAVA
      갓생사는 김초원의 개발 블로그
      갓생사는 김초원의 개발 블로그
      갓생사는 김초원의 개발 블로그 github: https://github.com/kimchowon

      티스토리툴바