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

안녕하세요 종욱님 ㅎㅎ

계속 무한루프를 돌게되는 이유가 무엇인지 궁금합니다.

-> 계산양이 너무나도 크기 때문입니다.

void go(vector<int> v, int cnt) {
	int cn = 0;
	for (int i = 0; i < v.size(); i++) {
		if (v[i] <= 0) cn++;
		if (cn == v.size()) {
			ret = min(ret, cnt);
			return;
		}
	}
	do {
		vector<int> nv = v;
		for (int i = 0; i < nv.size(); i++) {
			nv[i] -= damage[i];
		}
		go(nv, cnt + 1);
	} while (next_permutation(v.begin(), v.end()));

이 코드의 시간복잡도는 얼마가 될까요?

go함수마다 순열이 작동합니다.

저기서 순열은 n이 3, 즉, 3!이기 때문에 6이죠?

그러면 6^n의 시간복잡도를 가지는 함수라는 건데요

n이 10 정도만 되어도 6000만정도가 됩니다.

뮤탈리스크의 경우 최대 체력은 60이고 이 코드의 경우 체력이 적은 SCV가 아닌

그냥 순열을 돌려가며 -를 하는거기 때문에

최악의 경우

60 -1 -1 .. 순으로 진행되며

60^60이 되게 됩니다.

이는 매우 큰 경우의 수기 때문에 출력이 안되게 됩니다.

case 경우에 어떤 식으로 시간복잡도를 예측하고 들어가면 좋을지 문의드립니다.

-> 음.. 2가지를 고려해야 합니다.

1. 일단 재귀함수를 짜실 때 3^n까지는 괜찮은데 그 이외에는 좀 클거같다. 라는 생각을 가지고 들어가는게 좋습니다.

2. 최악의 경우를 가정해야 합니다. 지금 이 코드의 경우 얼핏보면 괜찮은 코드 같지만 최악의 경우 60^60라는 수를 가지게 됩니다. 만약 최적화를 진행하더라도 n은 최대 14정도를 가지는데 그 경우에도 6^14기 때문에 78,364,164,096라는 7천억 정도의 경우의 수를 가지기 때문에 크구나 하면서 -> 다른 풀이 방법을 생각해보자 -> BFS 이런식으로 로직의 흐름을 갖는게 중요합니다.

여기서 6^N이라는게 사실 코테 보면서 쉽게 계산하기 어려울 수 있습니다.

이 때는 좀 더 간단하게 생각하는게 중요합니다.

4^n과 8^n 사이정도다 -> 2^2n ~ 2^3n 사이다. 이런식으로 놓고 계산해보면

n이 14일 때 -> 2^28 ~ 2^56 ... 아... 이거 크네.. 라는 느낌이 오실 겁니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다.

시간 초과 문제는 특히 재귀 함수를 사용하는 경우 빈번하게 발생할 수 있는 문제입니다. 재귀 호출이 깊어질수록 시스템의 스택 메모리를 소모하게 되며, 특정 케이스에서는 상당한 시간 소요와 함께 무한루프처럼 보일 수 있습니다. 이는 애초에 알고리즘이 비효율적이라기보다는 문제의 규모가 재귀 호출로 감당하기에 너무 커서 발생하는 현상입니다.

주제와 관련된 유사한 질문과 답변을 통해 개선 방법을 찾아보실 수 있습니다:

1. 3-E 재귀 시간초과 - 이 게시물에서 재귀 + 백트래킹 방식으로 문제에 접근했음에도 시간 초과가 발생한 사례를 다루고 있습니다. 백트래킹보다는 BFS(Breadth-First Search) 같은 알고리즘을 활용하여 효율적인 탐색이 필요하다고 설명합니다.

2. 재귀 함수의 시간 복잡도를 예상하고 처리하기 위해서는 문제의 크기와 재귀 호출의 깊이를 고려해야 합니다. 또한, 메모이제이션을 통해 이미 계산된 부분 문제의 결과를 저장하여 같은 부분 문제를 중복 계산하지 않도록 최적화할 수도 있습니다.

일반적으로, 무한루프에 빠지는 경우는 종료 조건이 적절하지 않거나, 케이스에 따라 모든 재귀 호출이 종결되지 않는 경우가 많습니다. 이런 부분을 점검하고, 가능한 경우에는 재귀 호출을 반복적(Iterative)으로 변환하여 문제의 복잡성을 낮출 수도 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.