lcs3 [백준] 1958번 - LCS 3 [Java] https://www.acmicpc.net/problem/1958 1. 아이디어 이전 LCS 문제에서 문자열의 개수가 3개가 된 문제로 3차원 dp 배열을 활용하면 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 9251번 - LCS [Java])2. 문제풀이 문자열이 하나 추가된만큼 3중 for문과 max를 확인할 위치 하나만 추가하는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 2025. 1. 13. [백준] 9252번 - LCS 2 [Java] https://www.acmicpc.net/problem/9252 1. 아이디어 이전 LCS 문제에서 실제 문자열 출력이 추가된 문제로 LCS를 구했던 규칙을 통해 dp 배열을 거슬러가며 실제 문자열을 구할 수 있다.([코딩테스트 준비/백준] - [백준] 9251번 - LCS [Java])2. 문제풀이 기존 dp 배열에서 실제 LCS에 포함되는 문자열인 경우 dp[i-1][j-1] + 1로 dp 배열을 갱신했었다. 이를 활용해서 dp 배열의 끝에서 두 포인터를 r, c를 배치하고 출발시켜서 dp[r-1][c] 또는 dp[r][c-1]과 dp[r][c]가 같은 경우 해당 위치는 LCS를 이루지 못했던 경우이므로 해당 위치로 이동하고 dp[r-1][c] 와 dp[r][c-1] 와 다를 경우 해당 위치는 L.. 2025. 1. 13. [백준] 9251번 - LCS [Java] https://www.acmicpc.net/problem/9251 1. 아이디어 문제 이름처럼 다이다믹 프로그래밍을 활용한 LCS 알고리즘으로 해결할 수 있다.2. 문제풀이 두 문자열의 길이만큼 행과 열을 갖는 2차원 dp 배열을 만들어준다.2차원 배열의 두 인덱스는 각 문자열의 문자와 매핑시킬 수 있는데 두 문자가 서로 같을 경우 두 문자가 없었던 dp[i-1][j-1]일 때 LCS의 길이에서 +1 이 되고 두 문자가 서로 다르면 dp[i-1][j]와 dp[i][j-1] 중 큰 LCS를 갖는다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { Buff.. 2025. 1. 13. 이전 1 다음
