이것 저것 &

#include <iostream>
using namespace std;

int n, q;
int arr[500001] = { 0, };
int qarr[500001] = { 0, };


int binarysearch(int v, int s, int e) { // recursion 

	//1.base condition
	if (s > e)
		return -1;

	//2.divide
	int m = (s + e) / 2;

	if (v == arr[m]) return m;
	else if (v > arr[m]) return binarysearch(v, m + 1, e);
	else return binarysearch(v, s, m - 1);

}



int binarysearch2(int v, int s, int e) { // while 

	int start_val = s;
	int end_val = e;

	while (start_val <= end_val) {
		int m = (start_val + end_val) / 2;
		if (v == arr[m]) return m;
		else if (v > arr[m]) start_val = m + 1;
		else end_val = m - 1;
	}

	return -1;
}

int main() {

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	cin >> q;
	for (int i = 0; i < q; i++)
		cin >> qarr[i];


	for (int i = 0; i < q; i++) {
		int val = binarysearch(qarr[i],0,n-1);
		cout << val;
		if (i != (q - 1))
			cout << ' ';
	}
	cout << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/12738

대표적인 이분탐색 LCS문제입니다.

아래 문제와 동일하여 설명은 대체합니다.

https://gusdnr69.tistory.com/279

문제풀이 

1.  일반적인 구현방식으로 해결

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

int n;
int arr[1000000];
vector <int> v;


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

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

	for (int i = 0; i < n; i++) {
		if (v.size() == 0 || v[v.size() - 1] < arr[i]) v.push_back(arr[i]);
		else {
			int left = 0;
			int right = v.size();

			while (left <= right) {
				int mid = (left + right) / 2;
				if (v[mid] >= arr[i]) right = mid - 1;
				else left = mid + 1;
			}
			v[left] = arr[i];

		}


	}
	cout << v.size() << endl;
	return 0;
}

문제링크: https://www.acmicpc.net/problem/1477

이분탐색임을 인지했는데, 어떻게 풀어나가야 할지 고민했던 문제

처음에는 간격이 제일 넓은 구획을 찾고, 그 두 간격을 반토막씩 자르면 어떨까 생각함

하지만 아래 처럼 휴게소가 배치되어있고, m = 2인 경우라면 

이렇게 추가가 되어짐...

당연히 오답.. 

거리가 비례하게끔, 아래 그림처럼 구성이 되어져야함 

고민하다가 "거리"로 이분 탐색해야 한다는 것을 깨닫게 됨.

접근방식

1. 위 설명처럼 거리를 통한 이분탐색을 생각하게 됨

2. 이분탐색에서의 조건은 휴게소 간격들 사이 해당 거리(mid) 만큼 지정했을 때, 배치 가능한 갯수 

문제풀이 

주석을 자세하게 적어 놓아기 때문에 생략

정답 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, l;
vector <int> vec;

bool cmp(int& a, int& b) { // 없어도 되지만 간만에 짜보고 싶었어요ㅋㅋ
	if (a < b)
		return true;
	return false;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> l;
	int temp;
	vec.push_back(0), vec.push_back(l); //시작점과 끝점 추가 + 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 라는 조건 때문에
	for (int i = 0; i < n; i++) {
		cin >> temp;
		vec.push_back(temp);
	}
	sort(vec.begin(), vec.end(), cmp);



	int low = 0, high = l;
	int mid, result = 0;

	while (low <= high) {
		mid = (low + high) / 2; 

		int val = 0; // 휴게소 사이에 배치 될 수있는 휴게소의 갯수
		for (int i = 1; i < vec.size(); i++) {
			int dist = vec[i] - vec[i - 1]; // 휴게소 a와 b 사이에 간격

			val += (dist / mid); // 휴게소 간격 / 현재 길이
			if (dist%mid == 0) //휴게소가 이미 있는 위치라면 
				val--; // 갯수를 하나 감소 시켜주어야지. 
		}
		if (val > m)  // 배치할 수 있는 휴게소가 m개 보다 많으면
			low = mid + 1; // 길이를 늘려주어 m개가 배치 되게끔 만들어주고 
		else {// 배치될 휴게소가 m개보다 작거나 같을 때 
			high = mid - 1;// 길이(mid)가 더 작아질 수 있을지 확인해야지  
			result = mid;  //결과값을 갱신해주기 
		}
	}

	cout << result << endl;

	return 0;
}

문제링크:https://www.acmicpc.net/problem/1072

일반 반복탐색은 1000000000번 탐색을 반복해야하기 때문에 무조건 시간초과(대략 10초)

킹반적인 이분탐색문제입니다.

이분탐색 개념이 모호하시다면, 아래 링크를 참고하세요! 

https://cjh5414.github.io/binary-search/

접근방식

1. 일반적인 반복은 시초니까 이분탐색을 사용해보자

문제풀이 

1. result 를 -1로 저장한다. 만약 불가능하다면 result 값을 갱신하지 않아서 -1이 그대로 남게 된다.

2. 일반적인 이분탐색 방식으로 구현 코드를 보면 이해가 더 빠를듯

정답 코드입니다.

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

double x, y;
double z;
int result = -1;


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> x >> y;
	z = (y * 100) / x;
	z = floor(z);

	int low = 1;
	int high = 1000000000;

	while (low <= high) {
		int mid = (low + high) / 2; // 범위 ㄱㅊ
		double val = (double)((y + mid) * 100) / (x + mid);
		val = floor(val);
		if (val > z) {
			result = mid;
			high = mid - 1;
		}
		if (val <= z) {
			low = mid + 1;
		}
	}


	cout << result << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/1939

접근방식

1. 모든 경우를 판단해주어야 하는 것을 인지

2. 근데 n이 10000으로 크기 때문에 일반적인 bfs, dfs가 불가능함을 인지

3. 그러면 방문했던 값을 저장하는 dp(메모이제이션) 방식이 가능한가 확인

4. 10,000*10,000 = 100,000,000 X 4Byte = 대략 400Mb... 즉, dp방식도 불가능

5. 이분탐색을 통해서 방문하는 범위를 줄여볼까? 생각하게 됨

문제풀이 

1. 결과값은 다리의 비용중에 하나이다.2. 최소 비용(0), 최대비용(다리 비용중 최대값)을 low, high값으로 지정하고 mid값일때, 이동가능한지 확인3. 간단한 bfs를 통해서 이동이 가능한지 확인 4. 이동이 불가하면 high값을 낮춰주고, 이동이 가능하면 low값을 올려주며 진행

이분탐색 + bfs로 해결하는 문제입니다. 아래는 정답코드입니다.

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

int n, m;
int a, b, c;
vector <pair<int, int>> vec[10001];
bool visited[10001];
int s, e;
int bfs(int cost) {
	queue <int> que;
	que.push(s);
	visited[s] = 1;

	while (!que.empty()) {

		int cur = que.front();
		que.pop();
		if (cur == e)
			return true;
		for (int i = 0; i < vec[cur].size(); i++) {
			int ncur = vec[cur][i].first;
			int ncos = vec[cur][i].second;

			if (!visited[ncur] && ncos >= cost) {
				visited[ncur] = 1;
				que.push(ncur);

			}

		}



	}

	return false;

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	int from, to, cost;
	int maxcost = 0;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
		vec[to].push_back(make_pair(from, cost));
		if (cost > maxcost)
			maxcost = cost;
	}
	
	cin >> s >> e;
	
	int low = 0, high = maxcost;
	while (low <= high) {
		
		memset(visited, 0, sizeof(visited));
		int mid = (low + high)/2;

		if (bfs(mid)) {
			low = mid  + 1;
		}
		else {
			high = mid  - 1;
		}
		
	}
	cout << high << endl;

	return 0;
}