급하게임개발

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

이 문제는 이분탐색으로 LIS를 찾는 문제이다 이를 해결하는 과정은 해당 카테고리의 이전 게시물들을 참고하면 된다

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> lis;
int binary_search(int target) {
	int start = 0; 
	int end = lis.size() - 1;
	int mid = 0;
	while (start < end) {
		mid = (start + end) / 2;
		if (lis[mid] < target) {
			start= mid+1;
		}
		else {
			end = mid ;
		}
	}
	return start;
}

int main() {

	cin >> n;
	int idx = 0;
	int tmp;
	cin >> tmp;
	lis.push_back(tmp);
	for (int i = 1; i < n; i++) {
		cin >> tmp;
		if (tmp > lis[idx]) {
			lis.push_back(tmp);
			idx++;
		}
		else {
			lis[binary_search(tmp)] = tmp;
		}
	}

	cout << n-lis.size();

}

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

반도체 회로가 얽이지 않기 위해서는
우리는 해당 회로의 LIS를 구하면 된다

이 문제는 내가 이전에 풀었던 LIS 문제를 dp가 아닌 이분탐색으로 푸는 문제이다

해당 이미지를 보고 우리는 LIS즉 이전 인덱스가 현재 인덱스보다 커지지 않게 해주면 된다

이문제의 풀이는 
첫번째로 LIS 배열을 만들어주고 LIS는 무조건 1이상 일것이다 이에 LIS[0]에 arr[0]를 넣어준다

그후 우리는 2

가지 규칙으로 해당 문제를 풀어주면 된다
현재 내가 보는 숫자가 LIS의 가장 나중 인덱스의값보다 크면  그 나중인덱스 + 1 위치에 해당 수를 넣어주고

작을 시에는 해당 LIS 배열에서 해당 수가 들어갈 적절한 위치를 이분탐색으로 찾아서 해당 위치에 해당수를넣어주면된다

#include <iostream>

using namespace std;

int arr[40000];
int lis[40000];

int binarySearch(int left, int right, int target) {
	int mid = 0;
	while (left < right) {
		mid = (left + right) / 2;
		if (lis[mid] < target) {
			left = mid + 1;
		}
		else {
			right = mid;
		}
	}
	return right;
}
int n;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int j = 0;
	int i = 1;

	lis[0] = arr[0];

	while (i < n) {
		if (lis[j] < arr[i]) {
			lis[j + 1] = arr[i];
			j += 1;
		}
		else {
			int pos = binarySearch(0, j, arr[i]);
			lis[pos] = arr[i];
		}

		i += 1;
	}

	cout << j + 1;
}

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

이 문제는 일단 부분수열의 합의 모든 경우의 수를 구하는 방법을 알아야한다

부분수열을 굳이 연속되지 않아도 부분수열이기때문에

각 원소가 참여했는지 안했는지를 파악해야해서 n개의 원소를 파악할때 2^n개의 경우의 수를  검사해야 한다.
해당 문제를 푸는 방법

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

해당 문제를 참고 하면된다

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

int N, S;
int arr[41];
map<int, int> subsum;
long long cnt;

void rightSeq(int mid, int sum) {
    if (mid == N) {
        subsum[sum]++;
        return;
    }

    rightSeq(mid + 1, sum + arr[mid]);
    rightSeq(mid + 1, sum);
}

void leftSeq(int st, int sum) {
    if (st == N / 2) {
        cnt += subsum[S - sum];
        return;
    }

    leftSeq(st + 1, sum + arr[st]);
    leftSeq(st + 1, sum);
}

int main() {
    cin >> N >> S;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    rightSeq(N / 2, 0);
    leftSeq(0, 0);

    if (!S) cout << cnt - 1;
    else cout << cnt;

    return 0;
}

전체 코드는 이렇게 된다 부분적으로 한번 보자
일단 2의 20승은 1048576이기 때문에 1초연산을 약 100000000번이라고 가정하면 오바되지 않지만
현재 우리의 문제는 최대 2의40승이기에 1,099,511,627,776번 연산은 1초를 넘어간다

이에 우리는 2의40승에 대하여 2의 20승 2개로 나눠서 연산을 해준다
이에 우리는 우리가 받은 수열을 20개 짜리로 2개로 나눠서한다고 가정한다
그래서 나눈 왼쪽의 모든 부분수열의 합을  map에다가 저장해주고

오른쪽을 연산할때 오른쪽의 부분수열의 합을 연산할때 s-sum이 존재하면 그만큼의 갯수만큼 카운트를 중가시켜주면된다

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

이 문제는 bfs에 이분탐색을 통한 적절한 값 찾기 이다 
처음에는 갈수있는 경로별 최댓값을 구하려 했으나 시간초과가 났다 당연한 얘기다

자 일단 이코드는 bfs를 통해 특정 노드에서 노드로 가는 경우의 수를 모두 탐색하는데 이때 우리는 무게를 계속 정해주고 해당 무게가 특정 다리의 cost를 넘어가면 이후 탐색의 값을 좀더 줄여 나가는 방식으로 진행한다 도착점에 도착하면 그이후로 탐색하지않는다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector < pair < int , int >> v[100001];
bool isVisited[100001];
int maxNum = 1000000000;
int bfs(int from, int to) {
	int lo = 1;
	int hi = maxNum;
	int mid;
	int ans;
	while (lo <= hi) {
		mid = (lo + hi) / 2;

		for (int i = 0; i < n+1; i++) {
			isVisited[i] = false;
		}

		queue<int> q;

		q.push(from);
		isVisited[from] = true;
		bool canMore = false;

		while (!q.empty()) {
			int node = q.front();
			q.pop();

			if (node == to) {
				canMore = true;
				break;
			}

			for (int i = 0; i < v[node].size(); i++) {
				int next = v[node][i].first;
				int cost = v[node][i].second;
				if (isVisited[next])
					continue;
				if (mid > cost)
					continue;
				isVisited[next] = true;
				q.push(next);
			}
		}

		if (canMore) {
			lo = mid + 1;
			ans = mid;
		}
		else {
			hi = mid - 1;
		}
	}
	return ans;

}
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	int a, b, c;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;

		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}

	int from, to;
	cin >> from >> to;
	int ans = bfs(from, to);
	cout << ans;

}

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

이 문제는 일단 누적합을 이용해서 구간들의 합을 구해야 하는데 구간합간의 단순 비교를 하면 시간 초과가 뜨기 때문에 이문제의 경우 일단 한 배열의  구간 합들을 따로 저장 해놓고  이를 정렬한 후 이분탐색으로 그값의 하위 인덱스와 상위인덱스의 차를 더해주면 된다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> valOfA;
vector<int> valOfB;
vector<int> cmpB;
int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	iostream::sync_with_stdio(false);
	int t;
	int n, m;
	cin >> t;
	cin >> n;
	valOfA.resize(n + 1,0);
	int tmp;
	for (int i = 1; i <= n; i++) {
		cin >> tmp;
		valOfA[i] = tmp + valOfA[i - 1];
	}
	cin >> m;
	valOfB.resize(m + 1, 0);
	for (int i = 1; i <= m; i++) {
		cin >> tmp;
		valOfB[i] = tmp+ valOfB[i - 1];
	}

	for (int i = 0; i <= m; i++) {
		for (int j = i+1 ; j <= m; j++) {
			cmpB.push_back(valOfB[j] - valOfB[i]);
		}
	}
	sort(cmpB.begin(), cmpB.end());
	int start = 1;
	int subAarr = 0;
	long long ans = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			subAarr =valOfA[j] - valOfA[i];
			subAarr = -(subAarr)+t;
			int lowIdx = lower_bound(cmpB.begin(), cmpB.end(),subAarr) - cmpB.begin();
			int upIdx = upper_bound(cmpB.begin(), cmpB.end(), subAarr) - cmpB.begin();
			ans += upIdx - lowIdx;
		}
	}
	cout << ans;

}

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

이 문제의 경우 처음에 투포인터로 분류가 되어있어 풀려고 했는데 투포인터가 불가능 하게 리스트가 4개 있어서 안될거 같다는 생각을 했다 그래서 투포인터를 사용하기 위해서는 어떻게 해야할까라고 생각해봤을 때 a와 b의 합을 c와 d의 합의 모든 경우의 수로 리스트를 만들려고 하였다

즉 c와 d의 합을

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cmp.push_back(v[2][i] + v[3][j]);
		}
	}

이런 식으로 만들어 주고

a와 b의 합의 -  를 붙인거가 c와 d를 합친 cmp에 있는 갯수를 더해서 경우의 수를 구하면 된다 근데 갯수를 어떻게 구할지를 생각해보면 -(a+b) 에 대한 거를 algorithm 헤더에 있는 lower_bound와 upper_bound를  이분 탐색으로 해당 수를 찾아 낮은 인덱스 와 높은 인덱스를 찾아 차이가 해당 수의 갯수이니 이를 더해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v[4];
vector<int> cmp;
long long ans = 0;
int n;
int main() {
	cin >> n;
	for (int i = 0; i < 4; i++) {
		v[i].resize(n + 1);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> v[j][i];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cmp.push_back(v[2][i] + v[3][j]);
		}
	}

	sort(cmp.begin(), cmp.end());

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int tmp = v[0][i] + v[1][j];
			int lowIdx = lower_bound(cmp.begin(), cmp.end(), -tmp)- cmp.begin();
			int upIdx = upper_bound(cmp.begin(), cmp.end(), -tmp) - cmp.begin();
			ans += (upIdx - lowIdx);
		}
	}
	cout << ans;
}

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

이 문제는 이분탐색 문제이다 처음 그냥 대충  쉽게 접근하다가 틀렸는데 같은수가 여러번 들어갈수 있음을 망각했다

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long long  n;
vector<long long > inputData;
int main() {
	cin >> n;
	long long  tmp;
	long long  cnt = 0;

	for (long long i = 0; i < n; i++) {
		cin >> tmp;
		inputData.push_back(tmp);
	}
	sort(inputData.begin(), inputData.end());

	for (long long i = 0; i < n; i++) {
		long long left = n-1;
		long long right = 0;
		
		while (right <n && left>=0  && right<left) {
			if (right == i) {
				if (right < n-1) {
					right += 1;
				}
			}
			if (left == i) {
				if (left > 0) {
					left -= 1;
				}
			}
			if (left == right) {
				break;
			}
			if ((inputData[right] + inputData[left]) == inputData[i]) {
				cnt += 1;
				break;
			}
			else if ((inputData[right] + inputData[left]) > inputData[i]) {
				left -= 1;
			}
			else if ((inputData[right] + inputData[left]) < inputData[i]) {
				right += 1;
			}
		}
	}
	cout << cnt;
}

전체 코드는 이렇게 된다 처음에는 2/n 기준으로 양옆으로 펼쳐지면서 값을 찾으려 했으나 이렇게 하면 못찾을 때 가 발생해서 양옆에서 조이는 방식으로 진행 했다

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

이 문제는 내가 투포인터에 넣어놓은 LIS 문제에 이분탐색 버전이다 이전에 어떠한 코테 시험에서 봤을 때 LIS를 투포인터로 풀어서 시간 초과가 히든 테케에서 발생했었는데 이 방식으로 풀었어야 한거 같다

백준 에서 제공 하는 해당 테스트케이스를 예로 들어보자

일단 LIS를 저장하는 LIS 배열이 있다고 생각하자.

LIS 배열이 비었을 때 10을 넣을 수 가 있다

이렇게 되어있는 상황에서 20을 넣는다고 가정할 때 현재 10만 들어가 있는 LIS에서 가장 큰원소이자 마지막 원소인 10보다 20이 크기 떄문에 LIS 배열의 다음 인덱스에 20을 넣어준다

자 그후 10을 넣으려고 보면 10이 들어갈 자리는 10 과 20중에 자기 와 같은 크기의 원소인 10밖에 없다
그럼 으로 해당 10을 최근에 10으로 바꾼다
그후 30을 넣게 되면

자 이과정을 반복하면 우리는 LIS의 크기를 구할 수 있다
이문제를 풀때의 핵심은
1. LIS 배열이 비었을 때 그냥 원소 넣기
2. LIS 에 있는 원소보다 현재 집어넣을 원소가 클때 끝에 넣기
3. LIS 에 마지막원소(가장큰 원소) 보다 작을 떄 이분탐색으로 들어가야 할 위치 찾아서 넣기

이렇게 하면 결국에 LIS 배열의 크기는 LIS의 크기만큼만  된다

#include <iostream>
using namespace std;
int n;
int arr[1000000];
int lis[1000000];
int binarySearch(int left, int right, int target) {
	int mid = 0;
	while (left < right) {
		mid = (left + right) / 2;
		if (lis[mid] < target) {
			left = mid + 1;
		}
		else {
			right = mid;
		}
	}
	return right;

}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int j = 0;
	int i = 1;
	lis[0] = arr[0];
	while (i < n) {
		if (lis[j] < arr[i]) {
			lis[j + 1] = arr[i];
			j += 1;
		}
		else {
			int pos = binarySearch(0, j, arr[i]);
			lis[pos] = arr[i];
		}
		i += 1;
	}
	cout << j + 1;
}