원하시는 구현이 일반적으로 알려진 LCS 알고리즘이라 가정했을 때, LCS DP의 정의는 잘 잡으셨지만 각 항을 계산할 때 평균 O(n^2)의 시간복잡도로 계산하고 계시네요. 물론 27행의 루프에서 대부분의 i, j는 그냥 스킵하니까 통과는 됐지만 실제로는 여기서 루프가 돌아가니까 굉장히 느려지는 거라고 볼 수 있습니다.
일반적인 LCS 알고리즘은 각 DP값을 계산하는 데에 시간이 O(1) 정도밖에 안 걸립니다. 한번 LCS 다시 검색해서 알아보세요.
swj0324 1년 전
다른 사람 ac코드는 4~8ms 인데 반해서
제 코드는 800ms가 나오는데. 어떻게 해야 실행속도를 향상 시킬 수 있을까요?
질문1. 제 코드가 동적계획법을 잘 이용해서 풀었나요?
질문2. 동적계획법을 이용해서 풀었다면 실행속도가 다른 사람ac코드보다 느린이유가 겹치는 부분문제가 별로 없어서 인가요?
질문3. 실행속도 향상 시킬 수 있는 힌트 또는 제 코드의 비효율적인 점을 말씀해주세요.