dkwkekzz   7년 전

안녕하세요. 일단 제 글을 읽어주셔서 감사합니다. 

이해가 안 되는 부분이 있어 질문드리려고 합니다.

아래 코드와 같습니다.

꽤 많은 시도를 거쳐 성공했는데요. 

처음에 시도한 코드는 cache에 here을 추가하였습니다.

물론 캐시의 양이 줄면 시간복잡도가 줄겠지요. 

하지만 이 문제에서 입력 상한은 200이며 200*200*200은 시간내에 계산할 수 있는 양입니다.

문제가 될 수 있는 부분은 calcError이며 이 부분을 질문드리려 합니다. 

시간 초과가 된다는 의미는 calcError에서의 시간 복잡도가 합쳐져 200^3 * 200^3? 모르겠습니다. 

그런데 이건 있을 수 없지요. getMinError에서 calcError를 호출하긴 하지만 getMinError의 모든 부분 함수에 대하여 200^3만큼의 연산을 하는건 아니잖아요. 캐시로 인하여 결국에 모든 연산은 200^3내로 이루어질 것 같은 것이 제 생각입니다.

혹시 어떤 부분이 오류인지 알고 계신다면 답변 꼭 부탁드립니다.


감사합니다. 


yukariko   7년 전

우선 코드 수정 전의 calcError와 getMinError의 시간복잡도는 각각 O(N^3)으로, 둘을 같이 적용해도 똑같은 O(N^3) 코드입니다.

시간초과가 난 이유는 double형의 느린 연산 속도,

200 * 200 * 200 배열의 낮은 지역성으로 인한 캐시 효율 감소

여러개의 테스트케이스

가 원인으로 생각됩니다.


참고로 말씀드리자면 현재 코드는 조금 위험한 코드입니다.

그 이유는 cache에 here, there, _c가 담기지 않고 here이 빠지게 되었는데,

이것이 제대로된 중복처리를 할 수 없기 때문입니다.

1 0 1 일때의 답과 100 0 1일때의 답은 달라야하는데

there과 _c가 똑같은 0 1 이므로 둘은 같은 값을 가지게 됩니다.

실제로 return 위에 ret = 0; 같은 코드를 추가하게 되면 이 코드는 틀리게됩니다.

다만 의도하신건지는 모르겠지만 점화식의 특수성으로 인해 위 코드가 오답을 내진 않을것같습니다.

yukariko   7년 전

추가적으로 수정된 코드의 getMinError의 시간복잡도 역시 O(N^3)입니다.

cache배열은 N^2이지만, 초기화를 하지 않아 중복계산이 제대로 이루어지지 않기 때문에

반복이 한차원 더 실행되어 O(N^3)의 시간복잡도를 갖게 됩니다.

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