[코딩테스트] 백준(BAEKJOON) - LCS(Java, 9251번)

안녕하세요.

오늘은 사실 혼자서 풀지는 못했고 강의를 듣고난뒤에 푼 문제입니다.

 

그러나 이제는 제가 공부한걸 남기고 다시까먹지 않고자 공부내용까지 같이 남겨보고자합니다.

 

오늘 같이 볼 문제는 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 입니다.

'두 수열이 주어졌을때, 공통되는 수열중 가장 긴것을 찾자!' 입니다.

문제 링크 먼저 남겨드립니다.

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

9251번: LCS

 

저는 Youtube에서 해당 영상을 참고하며 공부했습니다.

https://www.youtube.com/watch?v=z8KVLz9BFIo&t=810s 

 

그럼이제 제가 작성한 코드를 남겨드리겠습니다.

매우 단순합니다.

 

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


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
			
			BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
			
			String a=bf.readLine();
			String b=bf.readLine();
			
			int[][] dp=new int[a.length()+1][b.length()+1];
			
			for(int i=1;i<=a.length();i++)
			{
				for(int j=1;j<=b.length();j++)
				{
					char aChar=a.charAt(i-1);
					char bChar=b.charAt(j-1);
					
					if(aChar==bChar)
						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[a.length()][b.length()]);
	}

}

 

다음은 문제예시를 직접 풀어본 내용입니다.

네 이렇게 직접 풀어봤습니다.

 

 

제가 생각한 핵심은 바로

 

즉 비교하는 두문자가 같다면 dp테이블에서 i-1, j-1번째의 값에 +1을

다르다면 i-1,j번째 혹은 i,j-1번째의 값 중 최대값을 가져와 i,j값을 업데이트 해주면 되겠습니다.

 

이런식으로 제가 생각한 핵심을 하나씩 적어보고자 합니다.

오늘은 날씨가 제법 따뜻했네요.

그럼에도 감기! 조심하시기 바랍니다!

 

감사합니다~:D