코딩무식자 전공생

문제 출처: https://www.acmicpc.net/problem/1182

풀이

s를 위한 부분수열(부분집합)을 만들 때, 해당 인덱스값을 더하거나, 더하지않는 경우가 있습니다.

즉 저 두 경우에대해서 s를 만들 수 있는 모든 후보군들이 구해집니다.

주의할 것은 공집합(0)처리입니다. 

s가 0일때, 아래코드를 돌리면 정답+1갯수가 출력되는데, 시작하는 sum이 0부터 시작되므로, 최초의 연산 시, 부분수열을 구하지않았음에도 

재귀함수를 통해(더하지 않았을 때의 함수)언젠가는 최초의 sum=0인값이 s와 동일하다고 인식되어 경우의 수가 하나 추가됩니다. 

그러므로, s=0일 때는 모든 경우를 구하고 한가지경우를 빼준 경우가 답이됩니다.

코드

문제 출처: https://www.acmicpc.net/problem/6603

풀이

대놓고 백트래킹(방문,방문해제)을 쓰지않았음으로 dfs문제로도 볼 수 있다.

1. 입력받을 배열과 로또6자리를 저장할 수 있는 배열 선언

2. 시작점 0(index 0부터)과, 숫자 6개를 저장했다면 출력할 수 있게 dfs(start,cnt)함수를 만들어 호출한다.

3.  재귀함수 종료조건을 dfs내부에서, cnt=6이면 로또6자리가 쌓인것이므로 출력후 종료할 수 있게 작성한다.

4. 아래와 같이 작성하여 숫자6개의 모든 조합들을 탐색한다.

for (int i = start; i < k; i++)
	{
		lotto[cnt] = arr[i];
		dfs(i + 1, cnt + 1);
	}

i=5, cnt=5일 때 dfs를 수행하면 cnt=6이되므로 1 2 3 4 5 6을 출력후 함수를 빠져나오고 다시 돌아가 i=6으로 시작되어서 

lotto[5]= arr[6]으로 되어 1 2 3 4 5 6 7 즉, 맨 뒷자리부터 수정됨을 확인 할 수 있다.

코드

#include<iostream>
#include<vector>
using namespace std;
int k, arr[13];
void dfs(int start,int cnt);
int lotto[6];
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	while (1)
	{
		cin >> k;
		int cnt = 1;
		if (k == 0)return 0;
		for (int i = 0; i < k; i++)
			cin >> arr[i];
		
		dfs(0,0);
		cout << '\n';
	}

}
void dfs(int start,int cnt)
{
	if (cnt == 6)
	{
		for (int i = 0; i < 6; i++)
		{
			cout << lotto[i] << " ";
		}
		cout << '\n';
		return;
	}
	for (int i = start; i < k; i++)
	{
		lotto[cnt] = arr[i];
		dfs(i + 1, cnt + 1);
	}
	
}

결과

문제출처: https://www.acmicpc.net/problem/9663

구글에 백트래킹 검색해보시면 가장먼저 나오는게 n-queen 문제입니다.

기본적인 이해와 재귀호출을 정확히 이해해야하므로 학습하시고 올 것을 추천드립니다.

백트래킹의 대표적인 문제라서, 학습하시면 많은 소스코드들이있으니 풀이는 따로 적지않겠습니다.

코드

#include<iostream>
using namespace std;
int col[15];
int n, cnt;
void N_queen(int pos);
bool promising(int pos);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n;
	N_queen(0);
	cout << cnt << '\n';
}
void N_queen(int pos)
{
	if (pos == n)
		cnt += 1;
	else
	{
		for (int i = 0; i < n; i++)
		{
			col[pos] = i;
			if (promising(pos))
				N_queen(pos + 1);
		}
	}
}
bool promising(int pos)
{
	for (int i = 0; i < pos; i++)
	{
		if (col[pos] == col[i] || abs(col[i] - col[pos]) == pos - i)
			return false;
	}
	return true;
}

결과

문제출처: https://www.acmicpc.net/problem/14888

삼성전자 A형 기출문제입니다.

풀이

백트래킹을 이용하여 풀 수 있습니다.

cnt를 선언하여 숫자가 모두 사용되었는지 체크합니다.

최초에 일단 계산을 하려면 첫번째값이 필요하므로, 첫번째 값과 첫번째값이 사용되었음을 나타낼수 있게 cnt+1 두 변수를 매개변수로하는 함수를 선언하여 백트래킹으로 연산을 하면됩니다.

헷갈리시는 분들은 아래 경우처럼 식을 작게해서 이해하시고 식으로 표현해보시면좋을 것같습니다.

3

1 2 3

1 0 1 0

코드

#include<iostream>
#include<algorithm>
using namespace std;
int min_val = 1000000001;
int max_val = -1000000001;
int arr[12];
int op[4];
int n;
void func(int num, int cnt);
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	for (int i = 0; i < 4; i++)
		cin >> op[i];
	//첫 숫자와
	int num = arr[0];
	//첫숫자를 배치하고 연산할준비하므로
	//ex)"1+" 상태여서 숫자한개썼으므로 cnt=1로시작
	func(num, 1);
	cout << max_val << endl << min_val << endl;

}
void func(int num, int cnt)
{
	//숫자를 다 썼으면
	if (cnt == n)
	{
		max_val = max(max_val, num);
		min_val = min(min_val, num);
		return;
	}
	//모든 연산자돌면서확인
	for (int i = 0; i < 4; i++)
	{
		//연산자가 있을 때만 연산합시다.
		if (op[i]) {
			if (i == 0)
			{
				//연산 할거기때문에 연산자 횟수-1
				op[i]--;
				//현재값과 현재 더해야하는 피연산자의 index더함
				func(num + arr[cnt], cnt + 1);
				//백트래킹
				op[i]++;
			}
			if (i == 1)
			{
				op[i]--;
				func(num - arr[cnt], cnt + 1);
				op[i]++;
			}
			if (i == 2)
			{
				op[i]--;
				func(num * arr[cnt], cnt + 1);
				op[i]++;
			}
			if (i == 3)
			{
				op[i]--;
				func(num / arr[cnt], cnt + 1);
				op[i]++;
			}
		}
	}
}

결과