swj0324   1년 전

다른 사람 ac코드는 4~8ms 인데 반해서

제 코드는 800ms가 나오는데. 어떻게 해야 실행속도를 향상 시킬 수 있을까요?

질문1. 제 코드가 동적계획법을 잘 이용해서 풀었나요?

질문2. 동적계획법을 이용해서 풀었다면 실행속도가 다른 사람ac코드보다 느린이유가 겹치는 부분문제가 별로 없어서 인가요? 

질문3. 실행속도 향상 시킬 수 있는 힌트 또는 제 코드의 비효율적인 점을 말씀해주세요.





       

Green55   1년 전

O(N^2)의 시간복잡도에 해결 가능한 풀이가 있습니다.

bamgoesn   1년 전

원하시는 구현이 일반적으로 알려진 LCS 알고리즘이라 가정했을 때, LCS DP의 정의는 잘 잡으셨지만 각 항을 계산할 때 평균 O(n^2)의 시간복잡도로 계산하고 계시네요. 물론 27행의 루프에서 대부분의 i, j는 그냥 스킵하니까 통과는 됐지만 실제로는 여기서 루프가 돌아가니까 굉장히 느려지는 거라고 볼 수 있습니다.

일반적인 LCS 알고리즘은 각 DP값을 계산하는 데에 시간이 O(1) 정도밖에 안 걸립니다. 한번 LCS 다시 검색해서 알아보세요.

herdson   1년 전

1. 동적계획법을 이용하긴 했지만 해당 문제에 적합한 점화식은 아닙니다.  

2, 3. LCS 문제는 O(N2)로 푸는 방법이 널리 알려져있습니다. LCS를 풀 때 사용하는 dp를 배우시는 것을 권고합니다.

댓글을 작성하려면 로그인해야 합니다.