jungri823   1년 전

정답 코드와 메모리 초과 코드입니다.

메모리 초과 코드는 가장 작은 값의 w를 0으로 유지하며 작은 쪽에 합쳐지게 했고,

정답 코드는 그룹의 갯수가 작은 그룹이 큰 그룹에 합쳐지도록 했습니다.


메모리 초과 나는 부분이 merge 함수 내에서 g를 순회하면서 다른 g에 넣을 때 말고는 없는 것 같은데

전체 g 안의 갯수는 n개로 항상 일정하고, 최대 2n개만 추가될 수 있는데 (그룹 사이즈가 n-1인 그룹이 그룹 사이즈가 1인 그룹에 합쳐질 때) 왜 메모리 초과가 나는지 모르겠습니다.

doju   1년 전

먼저 vector는 .clear()를 하더라도 할당받은 메모리를 해제하지 않습니다. 따라서 프로그램이 아주 많은 vector를 만들고 활발하게 사용한다면, 실제로 존재하는 원소는 몇 개 되지 않는데도 프로그램은 훨씬 많은 메모리를 점유하고 있는 상황이 벌어질 수 있습니다.
그러나 문제를 풀면서 이런 잉여 메모리를 신경쓸 일은 웬만하면 없습니다. 메모리 제한이 특별히 작지 않은 문제에서 메모리 초과가 발생했다는 것은 어쨌든 메모리 제한을 다 써 버릴 만큼의 메모리 할당 연산이 발생했다는 뜻이고, 이는 설령 메모리가 무제한으로 주어지더라도 다른 문제(특히 시간 초과)가 발생할 가능성이 높음을 시사합니다.

결론만 말하면 위쪽 풀이에서는 아래와 같은 패턴의 입력에서 O(N2)번의 .push_back() 연산이 일어납니다.

jungri823   1년 전

헉 몰랐던 내용인데 감사합니다.

메모리 초과가 아니더라도 시간 초과가 나겠네요. 감사합니다.

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