9252 LCS 2
https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
LCS DP테이블 작성법
- 문자열 A와 B를 입력받는다.
- 2차원 DP테이블, 그리고 0번 인덱스를 비워둔다, 크기는 A.length +1, B.length + 1
- 2중포문 순회를 하면서 테이블을 작성한다.
- A, B 문자열은 0번인덱스부터 사용하지만, DP 테이블은 1번 인덱스부터 사용하므로 이를 주의한다
- A[i - 1] == B[ j - 1] 일 경우 DP[ i ][ j ] = DP[ i - 1 ][ j - 1 ] + 1 을 해준다
- 다르다면 DP[ i - 1 ][ j - 1 ] = Math.max ( DP[i - 1][ j ], DP[ i ][ j - 1 ] )
LCS DP테이블 역추적 방법
- DP 테이블의 끝자락인 A.length, B.length 에서 순회를 시작한다.
- 순회용 정수인 x, y를 설정한다. x = A.length, y = B.length
- DP[x][y]를 DP[ x - 1][ y ] 과 DP[ x ][ y - 1 ] 이랑 비교한다.
- 만약 저 둘중 하나라도 같다면 해당 방향으로 순회용 정수를 조정해준다.
- 만약 둘다 다르다면 끝자락이라는 뜻이고, 이는 해당 DP테이블에서 최초로 문자가 같아서 조건 충족으로 정수가 증가 했음을 의미하므로, 해당 순회용 정수에 해당하는 문자를 스택에 넣던지 Stringbuilder에 추가한다. 순회용 정수랑 문자열의 인덱스 맵핑이 다르므로 주의해야한다. A[ x - 1 ] 을 넣거나 B [ y - 1 ] 을 넣는다. 어차피 둘이 같은 문자다
- DP[x][y] == 0 에 도달하면 순회를 종료한다
- 증명은 안했다
- 누가 해줘!
시간 줄이는 방법
- 스트링보다는 char[] 배열을 쓰면 시간을 줄일 수 있다.
- BufferedWriter 보다 System.out.println 을 이용 해서 바로 출력하면 시간을 줄일 수 있다. ( + "\n" 을 쓰는게 시간을 꽤 잡아먹는다.)
https://github.com/KimximyaFan/Random-Defense/blob/main/C0033.java