문제를 출제할 때 c++을 많이 이용하는데요. window의 mingw와 notepad++을 많이 씁니다. 제가 출제한 문제의 솔루션을 작성하였는데, 일부 테스트 케이스에서 빈 값이 나와버렸습니다. 이는 stack size를 초과했기 때문인데요. mingw stack size 늘리는 방법을 이 글에서 알아보겠습니다.
실습해 보기
재귀 함수가 있는 프로그램을 가지고 실습해 보겠습니다.
위 코드는 union-find 알고리즘의 일부 코드입니다. a와 b가 같은 집합에 속하는지를 판단하기 위해 해당 알고리즘을 쓰는데요. 보통 find 함수를 재귀로 많이 구현합니다. 제가 출제한 문제인 30797번 문제는 노드 갯수 제한이 20만이였습니다. 30만까지 늘려서 테스트 해 보겠습니다.
그림 1의 부모 정보는 아래와 같습니다.
이 상태에서 f(30만)을 호출하면 어떻게 될까요? 30만의 부모는 299999입니다. k의 부모는 k-1입니다. 이렇게 부모가 1이 될 때 까지 계속 올라가게 됩니다. 따라서 아래와 같이 재귀적으로 호출될 겁니다.
그런데, 함수를 쌓을 때 공간이 거저 주어지는 것이 아닙니다. 인자도 저장해야 하고, 함수가 끝났을 때 복귀 주소도 저장해야 합니다. 만약에 계속 함수를 호출하다가 stack 제한을 넘어가 버리면 곤란해 지는 상황이 발생합니다.
아무 옵션 없이 컴파일 하고 실행시켜 보겠습니다.
그랬을 때, x = 235210 에서 종료되었습니다. 처음에 30만부터 시작했으므로, 64790개의 f 함수가 재귀적으로 쌓였을 때 중간에 종료되었습니다. stack size를 늘려보겠습니다.
옵션이 조금 많아 보이는데요. 링커 옵션으로 stack size를 16메가로 주어서 컴파일 했다는 의미입니다.
- -Wl
- 링커 옵션을 줍니다.
- –stack,16777216
- 스택의 크기를 16777216byte (16mb)로 설정합니다.
즉 mingw stack size 늘리는 방법은 -Wl,–stack,[stack_size] 옵션을 주는 것입니다. [stack_size]는 byte 단위입니다.
실행시켜 보니, 아까와는 다르게 정상적으로 종료되었음을 알 수 있습니다. 프로그램이 사용한 stack size가 16메가를 초과하지 않았다는 의미입니다.
그러면, 아무런 옵션도 주지 않았을 때, stack size를 얼마나 크게 잡았을까요? 이것도 간단하게 알 수 있습니다. 스택 크기를 1메가로 설정한 뒤에 컴파일 해 보겠습니다.
역시, 중간에 종료되는데요. 267978에서 종료되었다는 것을 볼 필요가 있어요. 약 32030개의 f 함수가 쌓였을 때 종료되었다는 것을 볼 수 있습니다. 6.4만의 1/2이므로, 아무런 옵션을 주지 않았을 때, default로 2메가를 잡았다는 것을 알 수 있습니다.
비재귀로 바꾸기
여담이지만, 이 프로그램을 비재귀로 바꿀 수 있습니다. 그러면 굳이 stack size를 확장하지 않아도 됩니다.
f(30만)이 수행된 후, 경로 압축이 되었으므로, 위와 같이 바뀝니다. f(30만)이 수행되기 전 상태를 봅시다.
그림 10은 f(30만)이 수행되기 전입니다. 30만에서 root인 1로 올라가면서 경유하는 것들은 30만부터 2까지입니다. root는 -1을 부모로 가지는 1입니다. 그러면, 파란색 부분의 parent를 1로 바꾸기만 하면 됩니다.
처음 7번째 for loop에서, root를 구합니다. 그리고, x에서부터 root까지 타고 올라가면서 root가 아니라면, 부모를 root로 바꿉니다. 그리고 root를 돌려주면 됩니다.