본문 바로가기
728x90

LCS

문제 풀이/Baekjoon 2022. 7. 2. [백준] G5 LCS (JAVA) 문제 출처 - Baekjoon Online Judge 문제는 여기 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [문제] LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. [입력] 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대..
[알고리즘] 최장 공통 부분 수열 (LCS, Longest Common Subsequence)
Algorithm/정리 2022. 7. 2. [알고리즘] 최장 공통 부분 수열 (LCS, Longest Common Subsequence) 최장 공통 부분 수열 LCS (Longest Common Subsequence) 주로 최장 공통 부분수열(Longest Common Subsequence)을 나타내지만 최장 공통 문자열(Longest Common Substring)을 말하기도 한다. 최장 공통 문자열(Longest Common Substring)은 반드시 부분 문자열이 연결된 형태여야한다. banana, vbankn 최장 공통 부분수열(Longest Common Subsequence)은 떨어져있어도 상관없다. bdanvv, vbkkanm 이번에 다룰 LCS 알고리즘은 최장 공통 부분수열(Longest Common Subsequence)이다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종..
728x90

티스토리툴바