브루트 포스[4]:두포인터, 중간에서 만나기 (Brute Force[4]:Two Pointers, Meet in the Middle(MITM))

브루트 포스(brute force)

이러한 브루트 포스방법 중에서 투포인터, 중간에서 만나기에 관해서 소개를 하려고 한다.

 

---

두 포인터(Two Pointers)

배열에서 전체의 경우의 수를 반복문을 통해서 찾는 것이 아니라 두개의 포인터를 조작하여 원하는 결과를 얻는 방법이다.

여기서 두개의 포인터를 이용하여 기존보다 시간복잡도가 줄어드는 구조를 만들 수 있다.

 

두 포인터 예제

2003 - 수들의 합2 https://www.acmicpc.net/problem/2003

A[i]+...+A[j] = M이 되는 i,j 쌍의 개수를 찾는 문제와 같다.

가장 기본적으로 생각 할 수 있는 방법은 반복문을 만드는 것이다.

반복문으로 i와 j를 선택하고 i부터 j까지의 합을 구한다.

(i선택 x j선택 x 합더하기 = O(N^3))

이 문제의 N의 범위는 10^4이다. 고로 N^3 은 10^12으로 1조로, 시간제한인 0.5초를 통화하지 못한다.

//5% 시간초과
#include <iostream>
#include <vector>
using namespace std;

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

	long long n, m;
	int ans = 0;
	cin >> n >> m;
	vector<int> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	for (int i = 0; i < n; ++i) {
		for (int j = n - 1; j >= i; --j) {
			long long sum = 0;
			for (int k = i; k <= j; ++k) {
				sum += v[k];
			}
			if (sum == m) ans++;
		}
	}
	cout << ans;
}

이때 생각 할 수 있는 방법은 투포인터 이다.

위의 문제에서 합은 변하지 않는데 여러 번 구하는 것은 투포인터와 중복된 연산으로 없앨 수 있다.

start, end포인터로 연속한 부분수열의 첫과 끝을 잡는다. 

이때 합이 목표보다 작을 경우 end+1

합이 목표보다 클 경우 start +1

합이 목표와 같을 경우 start +1, end+1

 

여기서 중요한 부분은 각 포인터가 한방향으로만 이동하기 때문에 연속한 부분 수열을 선택하는 경우의 수가 O(N^2)가 아닌 O(N)이라는 점이다.

합이 목표보다 작아서 end +1

 

합이 목표보다 작아서 end +1

 

합이 목표보다 작아서 end +1

 

합이 목표보다 커서 start+1

 

목표이므로 start+1, end +1

 

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<int> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}

	int start = 0, end = 0, sum = 0, ans = 0;
	while (true) {
		if (sum < m) {
			if (end >= n) break;
			sum += v[end++];
		}
		else if (sum > m) {
			sum -= v[start++];
		}else{
			ans++;
			if (end >= n) break;
			sum -= v[start++];
			sum += v[end++];
		}
	}
	cout << ans;
}

---

중간에서 만나기(Meet in the Middle, MITM)

문제를 절반으로 나눠서 양쪽 절반에서 모든 경우를 다 해보는 방법이다.

시간복잡도 즉, 탐색의 크기를 많이 줄일 수 있다.

 

중간에서 만나기 예제

1208 - 부분수열의 합2 https://www.acmicpc.net/problem/1208

가장 먼저 생각해 볼 수 있는 방법은 모든 부분수열을 만들어서 확인해 보는 것이다.

부분수열의 갯수는 2^N이므로 (각 수에 대해서 뽑거나 안뽑거나 2가지 경우, dfs 등으로 구현가능)

하지만 n이 40이므로 2^40 약 10^12으로 1000초 이상 걸리므로 시간제한에 걸린다.

 

그럼 중간에서 만나기를 활용해보자.

수열을 두개로 쪼개서 부분수열의 합을 구하고 정렬하자.

이때 n을 반으로 줄인다면 2^20 약 10^6이므로 시간제한에 걸리지 않는다.

(정렬은 M개의 원소에 대해서 O(MlogM))

 

그 후에 두 포인터를 이용해서 갯수를 세보자.

N개의 수를 이용해서 전체 부분수열을 만들었을때는 포인터가 하나였지만

두개로 쪼개니 포인터가 두개다. (물론 시간 복잡도도 많이 작아졌다.)

양쪽을 선택해서 합을 확인 하며 된다. 

//한쪽 배열에서 만든 부분수열의 합이 같은것이 여러개 있을 경우에는 곱해서 더해야 한다.

// 목표 합이 0일 경우에 0 과 0을 선택 하는 경우는 빼야 한다. 공집합은 미포함.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, s;
vector<int> v;
vector<int> v1, v2;
int temp;

void dfs(int index, int sum, int end, vector<int> &a) {
	if (index == end) {
		a.push_back(sum);
		return;
	}
	dfs(index + 1, sum, end, a);
	dfs(index + 1, sum + v[index], end, a);
}
long long moveRight(vector<int> &a, int index) {	//같은 수가 몇개인지 리턴
	long long ans = 1;
	if (index == a.size() - 1) return ans;
	while (a[index] == a[index + 1]) {
		ans++;
		index++;
		if (index == a.size() - 1) return ans;
	}
	return ans;
}

int main(void) {
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin >> n >> s;

	for (int i = 0; i < n; ++i) {
		int num;
		cin >> num;
		v.push_back(num);
	}
	//부분수열의 합을 둘로 나눠서 각각 구한후 정렬.
	dfs(0, 0, n / 2, v1);
	dfs(n / 2, 0, n, v2);

	long long ans = 0;
	int start1 = 0;
	int start2 = 0;
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	reverse(v2.begin(), v2.end());
	while (start1 < v1.size() && start2 < v2.size()) {
		int sum = v1[start1] + v2[start2];
		if (sum == s) {
			long long s1 = moveRight(v1, start1);
			long long s2 = moveRight(v2, start2);
			start1 += s1;
			start2 += s2;
			ans += s1 * s2;			//같은 수가 여러개 일경우 곱
		}
		else if (sum > s) {
			long long s2 = moveRight(v2, start2);
			start2 += s2;
		}
		else {
			long long s1 = moveRight(v1, start1);
			start1 += s1;
		}
	}
	if (s == 0) ans--;
	cout << ans;
}