반응형
문제
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
풀이
이 문제는 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 라는 잘 알려진 알고리즘을 사용하여 풀 수 있습니다.
다른 훌륭하신 분들이 설명을 기깔나게 해준 블로그들이 많아서.. 풀이는 생략하겠습니다..
소스코드
후기
잘 알려진 알고리즘이고, 저번에 한 번 공부를 했어서 복습을 하는 겸 풀었는데
잘 기억이 안났던..;; 문제였습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 11659 구간 합 구하기 4 (Swift) (0) | 2023.04.07 |
|---|---|
| [BOJ] 백준 12865 평범한 배낭 (Swift) (0) | 2023.04.07 |
| [BOJ] 백준 2565 전깃줄 (Swift) (0) | 2023.04.06 |
| [BOJ] 백준 11054 가장 긴 바이토닉 부분 수열 (Swift) (0) | 2023.04.06 |
| [BOJ] 백준 11053 가장 긴 증가하는 부분 수열 (Swift) (0) | 2023.04.06 |
