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

안녕하세요 honn님 ㅎㅎ

cnt가 찾은 ret 이상이면 (제 코드에서는 mn) return하는 코를 안 적으면 왜 시간초과가 나는지 잘 모르겠습니다.
문제를 풀 때 최악의 상황을 생각해서 그 최악의 상황을 돌렸을 때 제한 시간안에 돌아가야 한다고 생각합니다.
만약 정답이 가로선 3개를 추가하는 것인 최악의 상황에서 이 코드가 유의미한 시간복잡도 차이를 만들어내지 못하는게 아닌가 하고 생각합니다. 이 문제 같은 경우 테스트케이스가 그러한 방식으로 짜여져있어서 통과와 시간초과라는 차이를 만드는 것인지 궁금합니다.

>>

먼저 이 알고리즘의 유형은 백트래킹인데 백트래킹의 시간복잡도를 잡는 것은 어렵습니다. 물론 문제 시작전에 시간복잡도 최악으로 잡고 드가야 하고 -> 어? 이거 이부분에서 return 하게 되면 불필요한 정점은 탐색하지 않게 되네? -> 하면서 수정하는게 백트래킹인데 이 백트래킹까지 고려하면서 시간복잡도를 잡는게 어렵습니다.

문제를 풀 때 최악의 상황을 생각해서 그 최악의 상황을 돌렸을 때 제한 시간안에 돌아가야 한다고 생각합니다. 라는 말씀은 맞습니다만 백트래킹의 경우 백트래킹을 넣은 최악의 상황잡기가 어려워서 대략적으로 판단하셔야합니다.

	com++;
	if (cnt > 3) return; // || cnt >= mn 생략했더니 시간초과 

이부분에서 mn을 넣게 되면 당연히 불필요한 부분은 줄일 수 있기 때문에 시간을 줄일 수 있는 부분이고 TC가 그런 부분에서 차이를 많이 두게 설계된 것 같습니다.

전에 선생님께서 가르쳐주신 조합 코드를 생각해보면 한번 확인한 위치는 다시는 확인을 안 하도록 start+1을 해서 코드를 작성했던 기억이 납니다. 하지만 이 코드는 확인했던 행 - 1까지는 확인을 안하도록 here을 사용하지만 열, 즉 j는 1부터 확인함으로써 중복으로 검사하고 있습니다. 왜 무한루프가 안 생기는지 이해가 잘 되지 않습니다.

	for (int i = start; i <= h; i++) {
		for (int j = 1; j < n; j++) {
			if (v[i][j] || v[i][j - 1] || v[i][j + 1]) continue;
			v[i][j] = true;
			go(i, cnt + 1);
			v[i][j] = false;
		}
	}

>>

이부분 말씀이신가요?

저거는 근데 어쩔 수 없는게 v[1][2]를 탐색하고 -> v[1][3]을 탐색하려면 i = start로 잡을 수 밖에 없어요.

그리고 if(v[i][j])를 걸어서 v[1][2] 중복 탐색은 막습니다. 검사는 하지만 -> 탐색은 막습니다.

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

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

감사합니다.

강사 큰돌 올림.

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

질문자님께서 제시하신 코드와 관련된 질문, 특히 “cnt가 찾은 ret 이상일 때 return하는 로직이 왜 필요한지”와 “왜 중복 검사에서 무한루프가 발생하지 않는지”에 관한 두 가지 주요 포인트에 대해 고민하셨군요. 이와 비슷한 주제로 선생님이 답변해주신 사례를 찾았습니다.

해당 질문은 “3-O 15684 사다리조작 질문입니다.”에서 논의되었습니다. 이 사례에서는 가로선을 추가하는 과정에서의 최적화와 중복 처리 방법에 대해 논의되었습니다. 귀하의 질문에서 언급된 “시간 초과를 방지하기 위한 코드 작성 방법” 및 “중복 검사를 방지하며 무한 루프를 어떻게 피하는지”와 관련 있는 내용이 포함되어 있습니다.

1. 시간 초과를 방지하기 위한 조건: 문제를 풀 때, 이미 찾은 해의 경계값(ret) 이상의 경우를 계속 탐색하지 않도록 중단하는 것은 시간 효율을 극대화하기 위한 전략입니다. 이는 더 이상의 탐색이 최적 해를 찾는 데 도움이 되지 않을 때 불필요한 연산을 줄이기 위함입니다.

2. 중복 검사와 무한 루프 방지: 특정 조건에서 다시 확인하지 않도록 하는 로직(예: here를 이용한 행 제어)은 무한 루프를 막기 위한 장치로, 조합 탐색이나 백트래킹에서 자주 사용되는 테크닉입니다. 각 단계에서 이미 확인한 영역을 다시 탐색하지 않도록 제한하여 효율적인 탐색을 가능하게 합니다.

위 링크에서는 j의 값에 따라 탐색을 제어하는 과정에서 n까지 포함시킬 필요성에 대한 세부적인 논의가 있었으며, 같은 맥락으로 이해될 수 있습니다.

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