본문 바로가기

LCS1

백준 9251 파이썬 - LCS - 동적 계획법 백준 9251 파이썬 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이번 문제는 두개의 문자열이 주어졌을 때 LCS(Longest Common Subsequence, 최장 공통 부분 수열)를 구하는 문제다. 예를 들어 ACAYKP CAPCAK LCS는 ACAK 이다. 이전에 풀었던 동적 계획법이랑은 조금 다르게 2차원 배열의 캐시를 만들어서 해결할 수 있고... 누적 값을 구해서 해결할 수도 있다... 2021. 10. 18.

이전 1 다음

티스토리툴바