글 읽기 - c++ 스택 오버플로우 질문입니다

plashdof 2년 전 0

이번엔 binary search 와 longlong 자료형을 맞췄는데도

예제 실행이 안되고 runtime error 가 발생합니다.

에러내용 구글링 해보니 stack overflow 라고 나오긴 하지만, 정확히는 모르겠네요,,, 답변 부탁드립니다!! ㅠㅠ

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
using ll = long long;

ll K = 0, N = 0;
vector<int> vec;

// 몇개의 랜선 나오는지 판별함수
int count_lan(ll max) 
{
	ll count = 0;
	for (int i = 0; i < K; i++)
	{
		count += vec[i] / max;
	}

	return count;
}

// 랜선길이 최댓값 구하는 binary search 재귀함수
void binary_lan(ll max, ll middle, ll min)
{
	int temp = 0;
	temp = count_lan(middle);
	if (temp >= N)
	// N보다 개수 많거나 같을때
	{
		if (count_lan(middle + 1) < N)
		{
			cout << temp;
		}
		binary_lan(middle, (max+middle)/2, min);
	}

	if (temp < N)
	{
		binary_lan(middle, (middle + min)/2 , min);
	}

}

int main()
{
	ll lan = 0;
	ll Max = -1, Min = LLONG_MAX - 1;
	cin >> K >> N;
	for (int i = 0; i < K; i++)
	{
		cin >> lan;
		if (lan > Max) Max = lan;
		if (lan < Min) Min = lan;
		vec.push_back(lan);
	}


	binary_lan(Max, Max, Min);

	
	return 0;
}

sunghyeck17 2년 전 0

stack overflow는 메모리의 stack 부분이 꽉 찼다는 뜻입니다.

stack 부분은 함수를 호출할 때 마다 점점 차고, 함수가 끝나면 다시 줄어듭니다. 보통 재귀 방식으로 구현한 함수에서 재귀가 끝나지 않아 함수가 무한히 호출될 때 많이 발생하는 오류입니다.

binary_lan 함수는 재귀를 끝내는 코드가 없습니다. 탐색하는 구간이 너무 좁으면 (min = middle이라면) 재귀를 멈춰야 하는데 계속해서 함수 호출을 하고 있습니다.

재귀를 멈추는 코드를 넣어주시면 에러를 해결하실 수 있을겁니다.

plashdof 2년 전 0

감사합니다!! 조언덕분에 해결 되었습니다 :)

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

문제

문제

출처

ICPC

c++ 스택 오버플로우 질문입니다

plashdof 2년 전 0

sunghyeck17 2년 전 0

plashdof 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말