b9295. LCS2

2024. 12. 27. 17:36·Algorithm & Data Structures/BOJ

 

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

 

 

 

두 문자열 간의 최장 공통 부분 수열(Longest Common Subsequence, LCS)을 구하는 문제다. LCS는 두 문자열에서 순서를 유지하면서 삭제 가능한 가장 긴 공통 부분 문자열을 의미한다.
이를 동적 계획법(DP)을 사용하여 효율적으로 계산하고자 했다.

먼저 두 문자열 s1과 s2를 입력받고, 두 문자열의 길이를 기반으로 DP 배열을 초기화한다.
dp[i][j]는 문자열 s1의 첫 i글자와 s2의 첫 j글자 간의 최장 공통 부분 수열의 길이를 저장한다.
DP 테이블을 채우는 과정에서,
현재 문자 s1.charAt(i - 1)와 s2.charAt(j - 1)이 같으면
dp[i][j]는 dp[i - 1][j - 1] + 1로 갱신된다.
문자가 다르면, 이전 단계의 값 중 더 큰 값을 가져온다
(즉, dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])).

DP 테이블이 완성된 후, dp[s1.length()][s2.length()]에는
최장 공통 부분 수열의 길이가 저장된다.
이를 출력한 뒤, 실제 공통 부분 수열을 추출한다.
이를 위해 문자열의 끝에서부터 DP 테이블을 역추적하며
공통된 문자를 찾아 StringBuilder에 추가한다.

공통된 문자는 테이블 값이 증가한 경우에 해당하며,
이 과정을 반복하여 LCS를 역순으로 저장한 후,
최종적으로 뒤집어 올바른 순서로 출력한다.

 

 

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

public class b9252 {
    static String s1, s2;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s1 = br.readLine();
        s2 = br.readLine();

        int s1Size = s1.length();
        int s2Size = s2.length();

        dp = new int[s1Size + 1][s2Size + 1];

        for (int i = 1; i <= s1Size; i++) {
            for (int j = 1; j <= s2Size; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        System.out.println(dp[s1Size][s2Size]);

        StringBuilder sb = new StringBuilder();
        int i = s1Size, j = s2Size;
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                sb.append(s1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        System.out.println(sb.reverse());
    }
}

'Algorithm & Data Structures > BOJ' 카테고리의 다른 글

Lv 2. 이모티콘 할인행사  (0) 2025.01.01
b9466. 텀 프로젝트  (0) 2024.12.31
b7579. 앱  (0) 2024.12.26
b7453. 합이 0인 네정수  (1) 2024.12.20
b2623. 음악프로그램  (0) 2024.12.17
'Algorithm & Data Structures/BOJ' 카테고리의 다른 글
  • Lv 2. 이모티콘 할인행사
  • b9466. 텀 프로젝트
  • b7579. 앱
  • b7453. 합이 0인 네정수
Geisha
Geisha
개발 일기
  • Geisha
    Geisha
    Geisha
  • 전체
    오늘
    어제
    • 분류 전체보기 (326)
      • Algorithm & Data Structures (246)
        • BOJ (104)
        • SWEA (1)
        • Programers (137)
        • Data Structures (3)
      • DB (27)
        • SQL (21)
        • RDBMS (2)
      • Java (1)
        • Class (1)
      • Spring (5)
        • Spring MVC (1)
        • Annotations (1)
      • CS (36)
        • 운영체제 (13)
        • 네트워크 (5)
      • Tool (6)
        • Git (5)
        • AWS (1)
      • Project (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    동적계획법
    binarySearch
    Union-Find
    구현
    유니온파인드
    백트래킹
    알고리즘
    programmers
    스택
    PriorityQueue
    algorithm
    전위순회
    투포인터
    Java
    SQL
    dp
    경로압축
    baekjoon
    다익스트라
    unionfind
    후위순회
    골드
    Stack
    이분탐색
    BFS
    dfs
    Dijkstra
    프로그래머스
    DynamicProgramming
    백준
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
Geisha
b9295. LCS2
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.