peter1201   9달 전

분할정복밖에 생각이안나서 분할정복으로 짜봤는데요!

자꾸 시간초과가 뜨네요!

q1.혹시 제가 실수한부분이 있나요??!!

q2.다른방법으로 해야하나요??!!

hokma   9달 전

스택을 이용해서 O(n)으로 해결할 수 있는 방법이 있다고 합니다.

peter1201   9달 전

아 그렇군요 감사합니다.!

그런데 분할정복 시간복잡도가 nlogn인걸로 알고있는데요! 

 왜 시간초과가 나는지 궁금합니다!

cubelover   9달 전

크기가 항상 절반으로 줄어드는 것이 아니기 때문입니다. 예를 들어 높이가 모두 같은 경우 시간복잡도가 O(n^2)이 되네요.

peter1201   9달 전

아 정말 그렇네요 감사합니다!! 

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