bangdy   7년 전

이것 저것 시도도 많이 해봤는데, 

자꾸 시간초과가 뜨내요..

저 알고리즘 자체도, C++로 돌아가는거 참고해서 작성한건데...

고수님들의 도움을 부탁드립니다.

chogahui05   7년 전

알고리즘은 정말 잘 짜셨습니다. 근데 왜 시간초과가 될까요?

stack 구조체가 있습니다. 이것은 어떤 식으로 저장이 되어 있냐면요.

int형 배열 10만개, 그리고 index. 이렇게 해서 sizeof(int) * (10만 1)의 크기를 가집니다.

이걸 값 복사 하면 어떻게 될까요?

chogahui05   7년 전

엄밀히 따지면 c 같은 경우, 참조에 의한 호출은 없긴 하지만요.

s 자체를 그냥 넘겨버리면 이렇게 되어 버립니다.

[스택 s = 엄청나게 큰 데이터] = callee에 그대로 복사 붙여넣기 하고 가실게요~


s의 크기를 출력하는 코드를 넣어보면 알 수 있죠.


함수 호출이 되면 어떤 일이 일어날까요?

내가 넘겨준 인자들을 사아앜~ 복사해서, 쌓아놓습니다. 리턴 주소와 함께 말이죠. (이건 caller에 돌아가기 위해서 쓰는 거라 조금 중요해요)

스택. 통째로 넘기면 얼마나 걸릴까요? 물론 스택 포인터야. 넘긴만큼 빼야지~!! 이렇게 퉁칠 수 있겠지만..

int형 배열을 통째로 10만개를 복사하는 게 문제에요. memcpy 함수 복잡도가 O(n)이지요. 시간이 많이 걸려요.


이걸 n회 반복하면? 시간 복잡도가 O(n^2)고요. 시간초과가 안 나는 게 이상한 게 아닐까요?

포인터로 넘기면 sizeof(int *) 크기만큼 복사하면 그만입니다. 그러면 시간 복잡도가 O(n)으로 줄어들겠지요.


배열과 포인터의 차이점, 스택 프레임에 대해서 알아보시는 게 어떨까요?

mendou12   7년 전

알고리즘은 잘 짜신 듯 해여


님 코드 클래스로 바꿔서만 해도 통과하는 걸 보니깐..;


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