goonbamm   10달 전

제가 만든 예시로는 잘 돌아가는데, N = 100000에 가까워질 만큼 거대한 예시를 만들 실력이 없습니다.

제가 시도한 방법은 아래와 같습니다. 참고로 문제 메모리 제한 512MB 입니다.

1. 값이 변하지 않는 함수 인자들은 모두 call by reference 로 변경했습니다.

2. 제가 선언한 vector 들의 크기를 계산해봤습니다. 기본 자료형은 굳이 구하지 않았습니다.

    N 의 최대 크기인 100000 로 가정하고 구해봤습니다.

- 181번 라인 → rmq  : 1MB (232144 * 4 Bytes),  21번 라인에서 크기가 결정됨.    

- 75번 라인 → 총 5개의 1차원 벡터 (parent, depth, heavy, head, pos) 

   크기는 106번 라인에서 모두 크기가 N이 되어, 약 2MB (5 * 100000 * 4 Bytes) 다.

- 158번 라인 → 클래스 Edge 벡터 (e)

   structure member alignment 에 의해 1개 크기는 16 Bytes, 총 N - 1 개이므로 약 1.6MB 다.

   클래스 함수의 크기는 모르겠으나, 생성자와 GET 함수만 선언했으므로 미미할 것으로 예상한다.

사실 제 짧은 추리로는 이 녀석이 문제를 일으키는 것인지 궁금합니다.

- 157번 라인 -> vector<vector<int>> adj(N) ;

   N^2 가 되는 순간, 메모리 제한을 가볍게 뛰어넘을 것이나 160 ~ 164번 라인에 적어뒀듯, 

    push_back() 함수를 사용하여 값을 저장하고 있으므로, 실제 저장되어야 하는 크기는 2 * (N - 1) * 4 Bytes 다.

    그러므로 0.8MB 다.


모두 다 해봤자, 5.4 MB라 아무리 제가 계산을 근삿값으로 했다고 해도 초과될 리 없다고 생각합니다.

제 나름 구글링을 해봐도 도저히 밝힐 수 없는데다가, 제가 군인이라 온라인 컴파일러로 돌리고 있어서

해답을 얻기 힘든데, 혹시라도 도와주신다면 정말 감사드리겠습니다!!    

goonbamm   10달 전

아무리 생각해도 메모리 초과는 변수에 의해 발생하지 않다고 생각했어요.

함수인자도 call by reference를 사용했기 때문에 문제가 없다고 생각했는데,

혹시나 함수의 재귀적 호출에 의한 것은 아닐까 하고 틀렸습니다 10번을 통해 알아냈습니다.

95번째줄에 위치한 decompose 함수에 들어가고 난 뒤에 "메모리 초과"가 나타난 것입니다.

어떻게 재귀적 호출이 일어나는지는 잘 모르겠으나. 일단 원인을 찾아냈습니다!!

저 코드는 cp-algorithm을 그대로 가지고 왔는데도 어떤 부분에서 재귀를 일으키나 봅니다.

goonbamm   10달 전

추가로 발견한 것인데, decompose의 반환형이 int로 돌렸을 때는 메모리 초과가 발생하는데

void 형으로 바꾸니 메모리 초과가 발생하지 않았습니다. 그 이유는 모르겠지만 신기하네요.

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