3-O go 함수 질문 드립니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-O

작성

354

안녕하세요 강사님

풀이 해주신 코드 기준 go 함수의 이중 for loop 에서, 변수 i 가 가로선의 index 를 나타내는 것으로 이해하고있는데

for loop 에서 변수 i 의 시작이 왜 here 부터 시작해야하는지 이해가 잘 되지 않아서요.

cnt = 0 에서 가로선 1개를 놓고,
cnt = 1 에서 또 가로선을 1개 더 놓게 되는 상황에서
cnt = 0 에서 놓았던 가로선 보다 같거나 아래 위치에 가로선을 놓아야한다는 조건이 어떻게 도출된 것인지 궁금합니다.

(가로선을 놓을 때 접하거나 연속되지 않아야 한다는 조건은
이중 for loop 안에 if 문에서 걸러지는 것으로 이해하고 있습니다)

(변수 i 의 시작을 0 으로 고정하면 시간 초과가 되는 것은 확인했습니다..)

c++코딩-테스트 C++코테 준비 같이 해요!

답변 2

서장규

#include <bits/stdc++.h>
using namespace std;
int n = 5, k = 3, a[5] = {1, 2, 3, 4, 5};

void print(vector<int> b){
	for(int i : b)cout << i << " ";
	cout << '\n';
}

void combi(int start, vector<int> b){
	if(b.size() == k){
		print(b);
		return;
	}
	
	for(int i = start + 1; i < n; i++){
		b.push_back(i);
		combi(i, b);
		b.pop_back();
	}
	
	return;
}

int main() {
	vector<int> b;
	combi(-1, b);
	return 0;
}

저도 이해하기 힘들었는데 알고리즘교안에 있는 재귀를 이용한 조합

이 부분과 가장 유사해 보입니다.

큰돌

지식공유자

안녕하세요 ㅎㅎ

    for(int i = here; i <= h; i++){
        for(int j = 1; j <= n; j++){
            if(visited[i][j] || visited[i][j - 1] || visited[i][j + 1]) continue;
            visited[i][j] = 1;
            go(i, cnt + 1);
            visited[i][j] = 0;
        }
    }

앞의 코드를 보면 here부터 들어가고 있죠? 그러면서 here ~ h까지 들어가면서 here부분의 j = 1부터 n까지 모든 가로 라인을 다 확인하고 있는 것을 볼 수 있습니다.

즉 이부분은 세로라인 here의 가로라인을 중복해서 확인하는 것입니다. 따라서 here의 가로에 해당하는 모든 경우의수를 다 확인합니다.

그렇기 때문에 과거의 here - 1을 탐색할 필요가 없습니다. 이미 모든 경우의수를 다 확인하는 코드니까요.

예를 들어

here가 1일 때 {1, 1}, {1, 2} ... {1, n} 확인하고 {2, 1} .. 이런식으로 호출되겠죠. 이 때 {2, 1}에서 다시 {1, 1}을 확인할 필요가 있을까요? 이미 모두 확인했는데요?

그렇기 때문에 cnt = 0 에서 놓았던 가로선 보다 같거나 아래 위치에 가로선을 놓아야한다는 조건이 도출되는 것입니다.

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

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

감사합니다.

강사 큰돌 올림.

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

3-O go 함수 질문 드립니다.