백준 1904번 : 01타일

문제 링크 : www.acmicpc.net/problem/1904

풀이에 참고한 링크 : lollolzkk.tistory.com/5

내 풀이(2021.1.7.) :

#include <iostream>

using namespace std;

int cache[1000000 + 1];

int search(int rest) {
	if (rest < 0) return 0; // 해가 없음
	if (rest == 0) return 1; // 해 발견
	if (rest > 0) {
		if (cache[rest] != 0) { // 캐시에 값이 존재하면
			return cache[rest];
		}
		else { // 캐시에 값이 존재하지 않으면
			int temp = search(rest - 2) + search(rest - 1);
			if (temp >= 15746) temp -= 15746;
			return cache[rest] = temp;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N; cin >> N;
	cout << search(N);

	return 0;
}

이 코드로 Visual Studio에서 실행을 하면, N=10000일 때 아래와 같은 오류 화면이 뜬다.

 

그런데 똑같은 코드를 백준 시스템에 제출했을 때는 '맞았습니다'가 떴다.

 

이에 대해서 구글링을 해보았더니

Visual Studio의 default 스택 사이즈는 1MB이어서, 재귀 함수로 인한 Stack Overflow가 일어난 것이라고 했다.

 

이를 해결하기 위해서 Visual Studio에서 '속성 - 링커 - 시스템 - 스택 예약 크기'를 통해
스택의 사이즈를 수동으로 늘릴 수 있었다.

 

위와 같이 스택 예약 크기를 500MB로 설정하니까

이 문제에서 N의 최대 크기인 1000000를 입력해도, 스택 오버플로우가 일어나지 않았다.

 

이와 같은 Stack Overflow는 지역 변수 할당을 통해서도 일어날 수 있다고 한다.

지역 변수도 스택에 할당되기 때문이다.

 

예를 들어, int 타입의 배열을 지역 변수로 할당하면

스택의 사이즈는 1MB이고 int 1개당 4byte이므로

배열의 크기는 약 250,000개(경우에 따라 오차 발생)까지 가능하고

이보다 큰 배열을 선언하면 Stack Overflow가 발생한다.

 

지역 변수는 스택 영역에 할당되고

전역 변수는 데이터 영역에 할당되고

동적 할당은 힙 영역에 할당되므로

프로그래밍을 할 때 스택/데이터/힙 영역의 사이즈를 염두에 두고 알고리즘을 짤 필요가 있다.

 

 

출처 : https://ghgus0702.tistory.com/11