92511 [백준 9251번 LCS] 오늘의 문제는 LCS이다. #고민의 흐름처음엔 무조건 완전탐색! 최악의 경우 길이가 1000인 2개의 문자열을 각자 만들어지는 모든 문자열의 종류를 비교해 준다면..?당연히 시간 초과가 날 것이라 생각했다.(애초에 문제 이름이 LCS이기도 하고,,) 그렇다면 LCS란 무엇일까?문제에 나와있듯이, LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제란문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 과거에 이미 다른 문제(공통부분문자열)로 LCS를 다룬 적이 있다!(한번 설명했던 내용기반이라 해당 문제가 보다 설명이 자세할 수 있다. 부족한 부분은 해당 문제로 채워보자.)기억이 가물가물하지만 이참에 제대로 혼자 풀어보려 했다.메.. 2024. 8. 15. 이전 1 다음
