목록2025/02/19 (1)

AtraFelis's Develop Diary

[99클럽 코테스터디 23일차 TIL / 백준] 9251 - LCS (DP)

99클럽 코테스터디 23일차 TILKeyWord : DP문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.풀이DP 문제에 익숙하지 않다면 아이디어를 떠올리는 것이 힘들었을 법한 문제였다.시간제한이 0.1초이니 완전탐색으로는 절대 불가능해 보인다. 또 그리디로 해결하는 것도 잠깐 고민해보니 불가능할 것 같다. 그래서 DP로 ..
Algorithm/백준 2025. 2. 19. 18:20
이전 Prev 1 Next 다음