급하게임개발

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/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/2631

이 문제는 LIS 문제이다  그 이유는 이 문제의 경우 학생들을 원하는 위치이 넣을 수 있으므로 정렬되어 있지 않은 학생들을 정렬된 학생의 알맞은 위치에 넣으면 되는것이다 즉 전체 수에서 LIS만큼  뺴주면 되는 문제였다

#include <iostream>
#include <algorithm>
using namespace std;
int arr[200];
int dp[200] = { 0, };
int lis = 0;
int main() {
	int n,x,y;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		dp[i] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <i; j++) {
			if (arr[i] > arr[j]) {
				dp[i]=max(dp[i], dp[j] + 1);
				lis = max(lis, dp[i]);
			}
		}
	}
	cout << n-lis;
}