Baekjoon Online Judge #9251: LCS (URL)
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
Problem (문제 원문)
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때,
모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
Restrictions (제약사항)
시간 제한: 0.1초
메모리 제한: 256MB
Input (입력)
첫째 줄과 둘째 줄에 두 문자열이 주어진다.
문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
Output (출력)
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
Examples (예제)
| Input | Output |
| ACAYKP CAPCAK |
4 |
Design (프로그램 설계)
Algorithm Category (알고리즘 분류)
Dynamin Programming (DP) (동적 프로그래밍) (URL)
[Algorithms] Dynamic Programming (DP) | 동적 프로그래밍
Dynamic Programming (DP) 동적 프로그래밍 - 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 구조에 적용할 수 있는 알고리즘을 통칭하는 말이다. - 특히 이러한 "작은 문제의 해답"을 Optima
dad-rock.tistory.com
Longest Common Subsequence Problem (LCS) (최장 공통 부분 순서 문제) (URL)
[Algorithms] Longest Common Subsequence Problem (LCS) | 최장 공통 부분 순서 문제
Longest Common Subsequence Problem (LCS) 최장 공통 부분 순서 문제 - 두 문자열에 존재하는 가장 긴 공통 부분 순서*를 찾아내는 문제이다. - 단순히, 전체 문자열에서 부분 문자열을 찾아내는 문제는 문자
dad-rock.tistory.com
Implementations (구현)
* GitHub (URL)
GitHub - ByeongHeonLee/Algorithms: Implementation of fundamental algorithms
Implementation of fundamental algorithms. Contribute to ByeongHeonLee/Algorithms development by creating an account on GitHub.
github.com
Performance (성능)
성공..!
