인프런 커뮤니티 질문&답변

안녕하세요 찬민님 ㅎㅎ

반례는 다음과 같습니다.

7 4
7
1
7
5
1
3
5
2

재귀적으로 무한루프가 돌게 됩니다.

정답 : 7

디버깅 코드는 다음과 같습니다.

#include <bits/stdc++.h> // --- (1)
using namespace std;// --- (2)
int n, m, j;
int a[11];
int arr[11];
int ret;
int now;

void move2(int des)
{
	cout << "des :: " << des << "\n";
	if (arr[des - 1]) return;

	if (now + m - 1 < des - 1)
	{
		ret++;
		now++;
		fill(&arr[0], &arr[0] + 11 * 11, 0);
		for (int i = now; i < now + m; i++)
		{
			arr[i] = 1;
		}
	}
	else if (now > des - 1)
	{
		ret++;
		now--;
		fill(&arr[0], &arr[0] + 11 * 11, 0);
		for (int i = now + m -1; i >= now ; i--)
		{
			arr[i] = 1;
		}
	}
	else
		return;

	move2(des);
}


int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	cin >> j;
	for (int i = 0; i < j; i++)
	{
		cin >> a[i];
	}
	fill(&arr[0], &arr[0] + 11 * 11, 0);
	for (int i = 0; i < m; i++)
	{
		arr[i] = 1;
	}

	for (int i = 0; i < j; i++)
	{
		move2(a[i]);

	}
	cout << ret;
}

코드리뷰는 다음과 같습니다.

1.이 문제는 반복문으로도 가능한 코드입니다. 근데 반복문으로 해도될걸 재귀로 하게 되면 함수호출에 대한 cost가 생겨 좋지 않습니다.

2.arr를 사용해 fill하고 해당 영역을 칠해서 바구니를 구현하신 생각은 좋으나 그저 숫자와 범위로도 가능한 걸로 봤을 때 이 코드가 조금은 불필요한 로직으로 보입니다.

감사합니다.

안녕하세요, 인프런 AI 인턴이에요.

시간 초과가 발생한 문제에 대해서 알려드릴게요. 먼저, 재귀로 구현한 코드에서 시간 초과가 발생했다면, 재귀 호출의 깊이가 너무 깊어서 발생한 것일 수도 있습니다. 재귀 호출이 깊어졌을 때, 스택 메모리가 너무 많이 사용되는 경우에는 시간 초과가 발생할 수 있어요.

시간 초과를 개선하기 위해서는 다음과 같은 방법들을 고려해볼 수 있습니다.
1. Memoization: 중복 계산을 방지하기 위해 한 번 계산한 값을 저장하고 재사용하는 기법입니다. 이미 계산한 값을 저장해두면 재귀 호출 시에 중복 계산을 피할 수 있습니다.
2. 반복문으로 구현: 재귀 호출 대신 반복문을 사용하여 구현할 수 있습니다. 반복문은 스택을 사용하지 않기 때문에 재귀 호출로 인한 스택 메모리 부담을 줄일 수 있습니다.
3. 문제에서 원하는 결과를 얻기 위한 핵심 아이디어를 도출하고, 해당 아이디어를 활용하여 다른 방법으로 해결해보는 것도 좋은 방법입니다.

또한, 코드가 맞는지 확인하기 위해서 반례를 찾아보는 것도 좋은 접근 방법이에요. 여러 가지 경우의 수를 고려해서 코드를 검증해보는 것이 중요합니다.

하지만, 코드와 문제의 상세한 내용이나 예시를 알려주지 않으셔서 더 구체적인 도움을 드리기 어렵습니다. 코드와 문제의 내용을 자세히 알려주시면 더 정확한 답변을 드릴 수 있을 거예요.

더 도움이 필요하시면 언제든지 말씀해주세요. 좋은 결과 있으시길 바랄게요!