백준 자바 9251 LCS

이 문제도 예전에 수학문제로 풀었던 적이 있었는데, 알고리즘으로 해결하려고 하니 좀 익숙하면서도 헷갈려서 당황스러웠다.
우선, 이 문제는 입력받은 두 개의 단어를 서로 비교하면서
만들 수 있는 공통으로 겹치는 부분 수열의 최장거리를 구하는 것이다. 즉, 두 개의 단어를 각각 가로 세로에 두고,
겹치는 부분을 체크하면서 문제를 해결하였다

대충 결과물은 이렇고, 코드를 보면서 설명하겠다.

package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Ox13_Q5_1 {
	
	static char [] char1;
	static char [] char2;
	
	// 백준 9251 G5 
	public static void main(String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		// 받은 문자열들 각각 단어배열로 변경
		char1 = br.readLine().toCharArray();
		char2 = br.readLine().toCharArray();
		
		// 공집합 생각해서 비교하는 판 1씩 크기 증가
		int [][] dp = new int[char1.length +1 ][char2.length+1];
		
		
		// 0은 공집합이니 넘기고 1부터 진행
		for(int i = 1; i<=char1.length; i++) {
			for(int j = 1; j<=char2.length; j++) {
				// 같은 경우 +1
				if(char1[i-1]==char2[j-1]) {
					dp[i][j] = dp[i-1][j-1] + 1;
				}
				// 다른경우 (이전 행 or 이전 열) + 1
				else {
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}// for fin
		}// for fin
		
		// 제일 마지막 값 출력
		System.out.println(dp[char1.length][char2.length]);

	}
}

우선, 입력 받은 두 개의 문자열을 편하게 비교하기 위해 바로 단어열로 변경해주었다. 다음으로, 두 집합을 비교하여 최종 값을 구하는 배열을 생성하는데, 두 부분집합이 아예 안겹치는 경우도 존재할테니, +1하여 공간을 생성해주었다.

다음으로, 첫 번째 문자열을 기준으로하여 두 번째 문자열을 하나씩 비교하는데, 가로, 세로가 서로 같은 경우 그 기준 왼쪽 대각선 값 + 1을 해주고, 만약 다른 경우엔
해당 좌표를 기준으로 세로열과 가로행중 더 큰 값을 그대로 물려받아 지정하게끔 구현하였다.

문제를 해결한 후 다른 분들은 어떤 방식으로 해결했는지 궁금해서 좀 알아봤는데, 필자는 이 문제 같은경우엔 두 문자열의 최대길이가 각각 1,000이길래 그냥 이중 반복문을 해도 1,000,000 이므로 진행했었다.
단, 이와같은 방식은 길이가 더 길어지면 오류가 발생하므로,
값이 커질 땐 재귀를 활용해서 해결해야한다.
물론 그럴 경우 메모리를 많이 잡아먹기에, 지금처럼 주어진 값이 작은 경우엔 단순히 이중반복문을 진행하고, 값이 클 땐 재귀를 활용하면 좋을 것 같다.

굿