kalmiaa   9달 전

N^3 알고리즘밖에 나오질 않아서 자꾸 timeout이 나네요.

N^2으로 풀 수 있는 힌트 좀 부탁드려요.


너무 답답하네요 다들 잘 푸시는데 ;;

koosaga   9달 전

어떤 n^3 알고리즘을 짜셨나요?

kalmiaa   9달 전

단순히 정렬 한담에 
2차원배열에 caching을 하였는데요.
caching 과정에서 for(i = left; i <= right; i++)
로 재귀호출을 함으로써 N^3 으로 caching을 하게끔 되어있습니다.

이렇게 되면 작은 부분집합의 최적값을 구해도 계속 left -> right로 탐색하면서 같은 호출을 반복적으로 하게 되는건 알겠는데요.
어떻게 indexing을 해서, 이미 최적화가 끝난 부분의 호출을 건너뛸 수 있는지 찾지를 못하겠네요.

koosaga   9달 전

left - right 구간에 대한 식이 아니라 1 - right 구간에 대한 식을 정의해보세요! 저렇게만 정의해도 답이 나오고 알고리즘 최적화가 훨씬 쉽더라고요. 

kalmiaa   8달 전

해결되었습니다. 감사합니다.

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