백준 9252 LCS 2
-
백준 9252 LCS 2Algorithm/BOJ 2021. 4. 20. 11:25
출처: www.acmicpc.net/problem/9252 분류: LCS 접근방식 최장 증가 수열을 찾는 전통적인 LCS 문제입니다. 문자열을 그대로 사용하면 시간초과가 나서 길이 테이블을 완성하고 백트래킹을 통해 문자열을 찾아주는 방식으로 해결했습니다. LCS는 다음과 같이 두 문자열로 이차원 행렬을 완성시켜 나가는 방식으로 찾아줄 수 있습니다. 현재 칸의 두 문자열의 문자가 같다면 왼쪽 대각선 위의 문자열에 현재 문자를 붙여나갑니다. 다르다면 위나 왼쪽 중에서 더 큰 문자열을 가져옵니다. 같다면 모두 가능한 문자열이겠죠? 이 원리를 이용해 저희 예제로 만들어보면 가로 CAPCAK 세로 ACAYKP 로 두면 다음과 같은 LCS 테이블을 만들 수 있습니다. 이제 마지막으로 마지막부터 백트래킹으로 문자열을..