[알고리즘] 백트래킹

 

 

[예제1] BOJ 1182 부분수열의 합

https://www.acmicpc.net/problem/1182

 

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

브루트포스로 풀었을 때.

백트래킹보다 느리고 메모리 사용량이 많다. 

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, S;
	cin >> N >> S;

	vector<int> v(N);
	vector<vector<int>> sums(N);

	for (int i = 0; i < N; i++)
		cin >> v[i];
	sums[0].push_back(v[0]);
	

	int answer = 0;
	if (v[0] == S)answer++;

	for (int i = 1; i < N; i++)
	{
		sums[i].push_back(v[i]);
		if (v[i] == S)
			answer++;
		for (int j = 0; j < i; j++)
		{
			for (int prev : sums[j])
			{
				if (prev + v[i] == S)
					answer++;
				sums[i].push_back(prev + v[i]);
			}
		}
	}
	cout << answer;
}

 

 

백트래킹으로 풀었을 때. 

코드가 더 직관적으로 효율적이다. 

각 원소마다 선택/미선택 2분기이므로, 시간복잡도는 O(2^N) 이다. 

 

int N, S;
int answer = 0;

void BackTracking(vector<int>& nums, int sum, int i)
{
	if (i >= N)
		return;
	if (sum + nums[i] == S)
		answer++;

	BackTracking(nums, sum, i + 1);
	BackTracking(nums, sum + nums[i], i + 1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> N >> S;

	vector<int> v(N);

	for (int i = 0; i < N; i++)
		cin >> v[i];

	BackTracking(v, 0, 0);

	cout << answer;
}

 

 

 

[예제2] BOJ 14888 연산자 끼워넣기

여기까지 풀고 백트래킹 쉽고 재밌다고 생각했다... 

int N;
vector<int> nums;
int addC, subC, mulC, divC;
int minResult = 1000000000;
int maxResult = -1000000000;

void BackTracking(int i, int result, int leftAddC, int leftSubC, int leftMulC, int leftDivC)
{
	if (i == N)
	{
		minResult = min(minResult, result);
		maxResult = max(maxResult, result);
		return;
	}

	if (leftAddC > 0)
		BackTracking(i + 1, result + nums[i], leftAddC - 1, leftSubC, leftMulC, leftDivC);
	if (leftSubC > 0)
		BackTracking(i + 1, result - nums[i], leftAddC, leftSubC - 1, leftMulC, leftDivC);
	if (leftMulC > 0)
		BackTracking(i + 1, result * nums[i], leftAddC, leftSubC, leftMulC - 1, leftDivC);
	if (leftDivC > 0)
		BackTracking(i + 1, result / nums[i], leftAddC, leftSubC, leftMulC, leftDivC - 1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> N;
	nums = vector<int>(N);
	for (int i = 0; i < N; i++)
		cin >> nums[i];
	cin >> addC >> subC >> mulC >> divC;

	BackTracking(1, nums[0], addC, subC, mulC, divC);

	cout << maxResult << '\n' << minResult;
}

 

 

 

[예제3] BOJ 9663 N-Queen

https://www.acmicpc.net/problem/9663

 

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

체스에서 퀸은 상하좌우, 대각선으로 이동 가능하다. 

간단하게 풀 수 있는 아이디어는, 한 행에 1개씩만 놓을 수 있다는 것을 이용하는 것. 

그리고 같은 열이나 대각선에 퀸이 있는지 조건을 검사하면 된다. 

 

void BackTracking(vector<vector<bool>> v, int y, int x, int count)
{
		...
        
        if (possible && y + 1 < N)
        {
            v[y][x] = true;
            BackTracking(v, y + 1, 0, count + 1);
        }
        if(x + 1 < N)
        {
            v[y][x] = false;
            BackTracking(v, y, x + 1, count);
        }
}

 

처음에 이런 구조로 했다가 chatGPT한데 호되게 혼났다. 아직도 이해를 못했다. 내일 다시 풀어볼 것임 ㅠㅠ