5-S 질문있습니다!

jin

작성한 질문수 2

0

안녕하세요 jin님 ㅎㅎ

이 코드는 백트래킹이라고 볼 수가 없습니다.

왜냐하면 휴리스틱으로 어떤 부분의 경우의 수를 제외한다는게 없는것 같아서 그렇습니다.

사실 이 문제는 백트래킹으로 풀 수 없는문제고 제 코드 또한 백트래킹으로 풀지 않았습니다.

    if(plus) go(index + 1, cur  + a[index + 1], plus - 1, minus, mul, div);
    if(minus) go(index + 1, cur - a[index + 1], plus, minus - 1, mul, div);
    if(mul) go(index + 1, cur * a[index + 1], plus, minus, mul - 1, div);
    if(div) go(index + 1, cur / a[index + 1], plus, minus, mul, div - 1);

앞의 코드처럼 모든 경우의 수를 탐색하죠? 완탐입니다. :)

 

자 그러면 jin님의 코드를 볼까요?

	for (int i = 0; i < N-1; i++) { // operate
		if (visited[i])continue;
		visited[i] = 1;
		_index.push_back(i);
		dfs();

제 생각에는 앞의 코드는 0, 1, 2 / 0, 1, 3 모든 경우의 수를 탐색해 나가기 위해 구축하신 거 같은데 저부분의 비효율성이 큽니다. 계속해서 0부터 n - 1까지 탐색을 하고 있습니다. continue를 하고 있지만 저 부분은 O(N - 1)의 코드입니다.

 

제 생각에는 jin님이 담아놓은 v를 기반으로

구축을 한다고 했을 때 v안에 + - *가 있다고 가정하면 총 6가지 순열의 수가 나오죠?

그렇다면 이런식으로 할게 아니라 차라리

```

do

while next_permutation

을 기반으로 하는게 나아보입니다.


또한

	if (_index.size() == N - 1) {
		int result = arr[0];

이런식으로 기저사례에서만 체크할 수 있게 한 부분은 잘하셨습니다.

 

감사합니다.