학부 연구생 민상 새벽까지 계속 고치고 고쳐봐도 문제가 풀리지 않는다.
문제는 빡구현이라고 할 수 있는 귀찮은 dfs? 문제라고 생각했고 어쨌든 구현은 다 했다.
그런데 59%에서 시간 초과도 아니고 자꾸 메모리 초과가 발생한다.
처음에는 배열 index를 넘어간다거나 그런게 있나? 하고 찾아봤는데 아무것도 없다.
문제 제한을 봐도 메모리 제한이 512mb라 어지간해서 터질리도 없는데..
그렇게 삽질이 시작됐다.
함수가 호출될 때 함수에 포함되어 있는 지역변수 + 함수 스택이 메모리에 저장되긴 하지만
각각 4byte~8byte 정도라고 알고 있고, 재귀 함수 안에 배열 선언 같은 것도 한 것이 없다.
많이 해본 dfs기도하고 59%까지 맞았다는 것은 로직 상에 오류도 없을 확률이 높다고 생각한다.
최악의 경우를 대충 생각해봐도 2000*2000번의 재귀니까 4백만번 도는데, 함수에서 선언하는 변수를
넉넉하게 잡아도 50byte를 넘어가지 않는다.
그러면 계산상으로 사용하는 메모리가 200mb도 넘지 않는 것이 아닌가..?
그래서 문제의 메모리 제한과는 별개로 스택 메모리 제한이 따로 있는 것인가 찾아봤다.
1
2
3
4
5
https://www.acmicpc.net/board/view/35086
https://www.acmicpc.net/board/view/28085
https://programmers-story.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%B4%88%EA%B3%BC-%EB%B0%9C%EC%83%9D-%EC%9D%B4%EC%9C%A0-%EB%B0%8F-%ED%95%B4%EA%B2%B0-%EB%B0%A9%EC%95%88
비슷한 질문들이 있는데, 명확하게 백준의 메모리 스택 제한에 대한 이야기는 없다.
우선 계속 틀리던 코드를 같은 로직으로 반복문으로 바꾸니까 바로 AC가 됐다.
일단 내린 결론은 스택 메모리의 제한은 따로 있지 않을까? 인데 확실하지 않다.
제일 쉬운 A+B 문제에서 재귀 함수를 돌리며 어느정도 크기에서 터질까 테스트 해보려고 했는데
간단한 재귀 함수를 의미없이 반복한다는 것을 컴파일러가 알았는지 최적화해버려서 원하는 것이 안 나온다.
재귀 함수를 사용할 때 주의해야겠다고 생각했고 백준 스택 메모리를 알아볼 좋은 아이디어가 생각난다면
블로그의 호기심 탐구에다 실험해보고 정리해서 올려놔야겠다.