[G5] 백준 9251 - LCS (python3)
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 해결방법 2차원 배열의 캐시값을 만들어 해결했다. - 백준 사이트의 [예제 입력 1] A C A Y K P [0, 0, 0, 0, 0, 0, 0] C [0, 0, 1, 1, 1, 1, 1] A [0, 1, 1, 2, 2, 2, 2] P [0, 1, 1, 2, 2, 2, 3] C [0, 1, 2, 2, 2, 2, 3] A [0, 1, 2, 3, 3, 3,..
2023. 8. 20.
[G5] 백준 5582 - 공통 부분 문자열 (python3)
https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 해결방법 LCS(Longest Common Subsequence, 최장 공통 부분 수열)에서 아이디어를 빌려왔다. 풀이👀 A B R A C A D A B R A E [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] C [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] A [1, 0, 0, 1, 0, 2, 0, 1, 0, 0, 1] D [0, 0, 0, 0, 0, 0..
2023. 8. 19.
