급하게임개발

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;
}

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

이 문제의 경우 아마도 프로그래머스 고득점 알고리즘 키트해도 비슷한 문제가 수록 되있을 것이다 단 백준에서는 매우 큰수까지의 비교를 하기 때문에 자료형에 unsinged long long을 해줌으로 범위를 널널 하게 잡아줘야 한다

이 문제의 경우는 각 테이블 마다 특정 시간을 주고 해당 시간 동안 몇명의 인원수를 상대할 수 있는 지를 더해서 친구들의 수와 같으면 정답이게 출력을 해주면 되지만 해당 조건을 만족하는 더 작은 수가 있을  수  있다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	unsigned long long n, m;
	vector <unsigned long long > times;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		unsigned long long tmp1;
		cin >> tmp1;
		times.push_back(tmp1);
	}

	sort(times.begin(), times.end());
	unsigned long long answer = 0;
	unsigned long min = 1;
	unsigned long long max = m * times.back();

	while (min <= max) {
		unsigned long long tmp = 0;
		unsigned long long avg = (min + max) / 2;
		for (unsigned long long i = 0; i < n; i++) {
			tmp += avg / times[i];
		}

		if (tmp < m) {
			min = avg + 1;
		}
		else {
			max = avg - 1;
			answer = avg;
		}
	}
	cout << answer;
}