백준에서 맞힌 사람 목록은 실행 시간 → 메모리 → 코드 길이 순으로 정렬된다. 메모리 사용량을 줄여서 순위를 올리기 위해 시도해본 내용을 정리한다.
C/C++ 프로그램은 빈 main이어도 상당한 메모리를 사용한다.
scanf/printf를 사용하는 C: 약 1112KBcin/cout을 사용하는 C++: 약 2020KB
이는 작성한 코드가 아니라 런타임 초기화에서 비롯된다. main()이 호출되기 전에 glibc의 __libc_start_main 함수가 먼저 실행되면서 IO 버퍼, 글로벌 락, locale 등을 세팅하기 때문에, main 내부에서 아무리 절약해도 기본 사용량은 줄어들지 않는다.
런타임 레벨 최적화
__libc_start_main 재정의
__libc_start_main을 직접 재정의하면 libc 초기화를 통째로 건너뛸 수 있다.
#include <unistd.h>
int main() {}void __libc_start_main() { write(1, "Hello World!", 12); _Exit(0);}main은 링커가 심볼을 요구하기 때문에 빈 함수로 남겨두고, 실제 로직은 __libc_start_main 안에서 실행한다.
주의할 점은 printf나 puts를 사용할 수 없다는 것이다. 이 함수들은 내부적으로 IO 버퍼와 락에 의존하는데, 초기화를 건너뛰었으므로 해당 구조체가 세팅되지 않아 segfault가 발생한다. read/write는 커널 시스템콜을 직접 호출하는 것이라 문제없다.
종료 시에도 exit() 대신 _Exit()을 사용해야 한다. exit()은 atexit 핸들러를 호출하는데, 초기화되지 않은 상태에서 문제가 생길 수 있다.
0KB가 아니라 156KB인 이유는 동적 링커 때문이다.
BOJ에서 C 프로그램은 동적 링크로 컴파일되고, 동적 링크된 바이너리를 실행하려면 동적 링커 ld-linux.so가 메모리에 함께 적재되어야 한다. 이 동적 링커의 크기가 약 156KB이다. 정적 링크를 하면 제거할 수 있겠지만, BOJ에서는 컴파일 옵션을 제어할 수 없으므로 사실상 하한선이다.
iostream 사용하지 않기
C++에서 cin/cout을 사용하면 iostream 런타임이 통째로 적재되면서 약 900KB가 추가된다. ios::sync_with_stdio(false)를 호출해도 이미 적재된 부분은 해제되지 않는다. 메모리가 중요한 경우 scanf/printf를 사용하는 것이 낫다.
stdio 버퍼 줄이기
__libc_start_main 재정의까지는 하지 않더라도, stdio 버퍼 크기를 줄이는 것만으로 약간의 효과를 볼 수 있다.
setvbuf(stdin, NULL, _IONBF, 0);setvbuf(stdout, NULL, _IONBF, 0);다만 버퍼를 제거하면 IO 성능이 저하되므로 시간과의 트레이드오프가 존재한다.
read/write 직접 사용
scanf/printf 대신 read/write로 직접 IO를 수행하면 stdio 관련 내부 구조체가 적재되지 않는다. 다만 1바이트씩 read(0, &c, 1)을 호출하면 시스템콜 오버헤드가 크므로, 적절한 크기로 버퍼링하여 읽는 것이 좋다.
char ibuf[4096]; int ipos, ilen;char rc() { if (ipos >= ilen) ilen = read(0, ibuf, 4096), ipos = 0; return ipos < ilen ? ibuf[ipos++] : -1;}코드 레벨 최적화
자료형 크기 줄이기
int(4바이트) 대신 범위가 충분하면 short(2바이트)나 char(1바이트)를 사용한다. 배열이 클수록 차이가 커진다.
// int dp[10000] → 40KB// short dp[10000] → 20KB// char dp[10000] → 10KBbool 배열은 실제로 원소당 1바이트를 차지하므로, 참/거짓만 저장하는 경우 비트 배열로 8배 줄일 수 있다.
unsigned char visited[N/8 + 1];// set: visited[i>>3] |= 1 << (i&7);// get: visited[i>>3] & (1 << (i&7))전역 변수 활용
큰 배열을 지역 변수로 선언하면 스택에 올라간다. 스택 크기 제한(보통 8MB)에 걸릴 수 있고, 메모리 측정에서도 다르게 잡힐 수 있다. 전역이나 static으로 선언하면 BSS 영역에 배치되어, 실제 접근하기 전까지 물리 메모리를 사용하지 않는다(demand paging).
배열 재활용
DP 문제에서 이전 행만 참조하는 경우, 2차원 배열 대신 1차원 배열 두 개(또는 하나)로 롤링할 수 있다. BFS에서도 visited 배열을 거리 배열과 통합하면 배열 하나를 절약할 수 있다.