https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
풀이
문제를 보았을때 알수있는 힌트
LCS -> 최장 공통 부분 수열을 찾는 문제이다. 이는 DP를 활용하여 푸는 것이 빠르게 답을 찾을 수 있다.
최장 공통 수열을 구글에 검색해보면 위키 백과에 어떻게 이용하는지 알수있다.
그 중 하나의 이미지를 가져왔는데 위 그림 처럼
1. 행과 열이 같은 경우 이전에 행, 열에 있던 값에 1을 더하는 형식
2. 비교하는 행과 그 위에 있는 열중에 큰 값을 또 집어 넣는다.
이렇게 구현된 리스트에 마지막 값이 최대의 길이가 된다.
이를 DP로 크게 2차 배열로 할수있고 하나의 리스트로도 가능하니 참고하고 생각하며 코드를 짜면 구현할 수 있다.
이 LCS에 대해서는 알고리즘을 남겨놓아야할듯하다.
https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon9251.py
GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리
코딩테스트 공부한 내용 정리. Contribute to dydwkd486/coding_test development by creating an account on GitHub.
github.com
'Coding Test > baekjoon' 카테고리의 다른 글
| [백준 9461] 파도반 수열 - python (solved.ac - 실버 3) (0) | 2022.05.02 |
|---|---|
| [백준 14891] 톱니바퀴 - python (solved.ac - 골드 5) (0) | 2022.05.01 |
| [소프티어] 슈퍼바이러스 - python (레벨 3) (0) | 2022.04.29 |
| [백준 3190] 뱀 - python (solved.ac - 골드 5) (0) | 2022.04.28 |
| [백준 1987] 알파벳 - python (solved.ac - 골드 4) (0) | 2022.04.27 |