이것 저것 &

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

최장 공통 수열 (LCS)를 도출하는 문제.

문제에 대한 설명은.... https://yhwan.tistory.com/18

이분보다 잘할 자신이 없어서 이분꺼 참고

같은 논리로 작성하였는데, 정작 나는 이분탐색을 사용하지 않은 일반구현으로 제작했다.

아직까지 굳이 이분탐색으로 작성해야하는 이유를 못느끼고 있다.. (문제 검색에 올려놓음)

접근방식

1.  LCS 만큼의 전깃줄이 남아있을 수 있겠구나

2.  수의 범위가 커서 dp를 사용한 방식O(n^2)으로는 불가능 하겠구나 

문제풀이 

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

정답코드입니다.

아래 방식이 이분탐색을 사용하지 않아서 문제가 될 수 있을 것 같은데, 아직까지는 잘 모르겠습니다.

혹시 아시는 분은 댓글 부탁드립니다. 

--- ++ 추가 ---

아래방식은 해당 문제에서는 시간초과가 난다. 

최악의 경우에는 취약한 방법이기 때문이다. 따라서 이분탐색 방식을 권장한다.

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

단순 구현

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

int n = 0, temp;
vector <int> vec;
int lcs[100000];
int lcs_cnt = -1;


void low_bound(int num) {

	int val = vec[num];

	for (int i = 0; i <= lcs_cnt; i++) {
		if (val < lcs[i]) {
			lcs[i] = val;
			break;
		}

	}
}


int main() {

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		vec.push_back(temp);
	}

	for (int i = 0; i < vec.size(); i++) {

		if (lcs_cnt == -1)
			lcs[++lcs_cnt] = vec[i];
		else if (lcs[lcs_cnt] <= vec[i]) 
			lcs[++lcs_cnt] = vec[i];
		else if (lcs[lcs_cnt] > vec[i]) 
			low_bound(i);
		

	}
	
	
	
	cout << n - (lcs_cnt + 1) << endl;

	return 0;
}

이분탐색 적용

#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 << n - v.size() << endl;
	return 0;
}

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

접근방식

1. 시간 제한이 0.1초인 것을 보고 일반적인 정렬 방식을 사용하면 안되는 것을 인지

2. 시간 제한상 nlogn번만에 도출해야 하는 것을 인지하였고 max 힙, min 힙 2개를 사용해서 구현하는 방법을 고안

문제풀이 

1. 음.. 설명하기 어려워서 잘 설명된 링크를 가져왔습니다! ㅋㅋㅋㅋㅋ

https://o-tantk.github.io/posts/finding-median/

너무 잘 정리하셨더라구요! 

2. 위에서 설명하는 방식처럼 max힙에는 기준점보다 작은 값, min힙에는 기준값보다 큰 값들로 구성

정답코드입니다.

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

int n = 0, temp = 0;

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

	priority_queue <int> mx; //기준보다 작은 값들을 넣을거 (기준포함)
	priority_queue <int> mn; //기준보다 큰 값들을 넣을거 -1곱하면서

	//초기작업
	cin >> n;

	cin >> temp;
	mx.push(temp);
	cout << temp << "\n";

	for (int i = 1; i < n; i++) {
		cin >> temp;
		int sta = mx.top();
		if (sta > temp) {
			if (mx.size() > mn.size()) {
				mx.pop();
				mn.push(sta*-1);
				mx.push(temp);
			}
			else {
				mx.push(temp);
			}

		}
		else if (sta < temp) {
			if (mx.size() == mn.size()) {
				mn.push(temp*-1);
				int mnn = mn.top()*-1;
				mn.pop();
				mx.push(mnn);
			}
			else {
				mn.push(temp*-1);
			}
		}
		else { //sta == temp
			if (mx.size() == mn.size()) {
				mx.push(temp);
			}
			else { //mx가 하나 더 많을 때
				mn.push(temp*-1);
			}
		}

		cout << mx.top() << "\n";

	}


	return 0;
}

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

우선순위 큐를 사용하는 문제입니다. 

접근방식

1. n이 200,000까지 이기 때문에 일반적인 브루트 포스는 불가

2. 우선순위큐에 데이터를 담고 합치며 진행하는 구조를 생각

3. 우선순위큐 2개를 사용해서 구현 

문제풀이 

1. 입력값을을 min-heap(우선순위 큐)에 삽입

이때, 시작시간이 작은 순으로 배치

2. 시작시간이 작은 순으로 하나씩 heap에서 꺼냄

3. 두번째 min-heap2에 넣을건데,  min-heap2 top에 값의 e와 현재 데이터의 s값을 확인하고,

합칠 수 있으면 합친후 min-heap2에 삽입하는 것을 반복

4. 결과값은 min-heap2의 사이즈

아래는 정답코드입니다. 

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

int n;
priority_queue <pair<int, int>> ique;
priority_queue <pair<int, int>> oque;

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

	cin >> n;
	int a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		ique.push(make_pair(-a, -b));
	}

	for (int i = 0; i < n; i++) {
		int s = ique.top().first * -1;
		int e = ique.top().second * -1;
		ique.pop();
	
		if (oque.empty()) { //처음에 비어 있다면,
			oque.push(make_pair(-e, -s));
			continue;
		}

		int ne = oque.top().first*-1;
		int ns = oque.top().second*-1;

		if (ne <= s) {
			oque.pop();
			oque.push(make_pair(-e, -ns));
		}
		else {
			oque.push(make_pair(-e, -s));
		}



	}

	cout << oque.size() << endl;

	return 0;
}

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

리프노드의 갯수를 구하는 문제입니다.

dfs 탐색을 통해서 제거된 노드의 자식노드들도 함께 제거를 하면 진행해주었습니다.

만약, 자식 노드를 가지고 있지 않다면 leaf 노드로 간주했습니다.

이때, 주의할 점은 제거된 노드의 부모노드가 leaf 노드가 될 수 있다는 점입니다.

아래는 정답 코드입니다.

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

vector <int> vec[50];
int n = 0, root;

void dfs(int n) {

	if (vec[n].size() == 0) {
		vec[n].push_back(-2);
		return;
	}
	for (int i = 0; i < vec[n].size(); i++) {
		dfs(vec[n][i]);
	}

}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		if (temp == -1) 
			root = i;
		else
			vec[temp].push_back(i);
	}
	int m;
	cin >> m;

	dfs(m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < vec[i].size(); j++) {
			if (vec[i][j] == m)
				vec[i].erase(vec[i].begin() + j);
		}
	}
	int result = 0;
	for (int i = 0; i < n; i++)
		if (vec[i].size() == 0)
			result++;
	cout << result << endl;

	return 0;
}

문제풀이:https://www.acmicpc.net/problem/1436

666을 포함하는 값의 위치를 탐색하는 탐색문제였습니다.

별 다른 알고리즘기법이 포함되지 않기 때문에 구현문제라고도 생각할 수 있습니다.

666부터 수를 탐색하면서 666을 포함하는지 확인해주고 카운트값을 1씩 올려주면 탐색하면 되는 문제였습니다.

시간초과를 조심해야 하는데,  해당 문제는 10000까지 밖에 되지 않기 때문에 풀이가 가능했습니다. 

정답코드입니다.

#include <iostream>
using namespace std;
int n = 0;
int arr_index = 0;
int val[15]; //자리수들을 저장할 배열 

int main() {
	cin >> n;

	for (int i = 666; arr_index != n; i++) {
		int num = i;
		int num_size = 0;
		bool jud = false;

		while (num) { // 10이면 2자리수 이런식 
			val[num_size] = num % 10;
			num /= 10;
			num_size++;	
		}
		num = i; // 다시 num은 i 
		for (int j = 0; j <= num_size - 3; j++) {
			if (val[j] == 6 && val[j + 1] == 6 && val[j + 2] == 6) {
				jud = true;
				break;
			}
		}
		if (jud == true)
			arr_index++;
		if (arr_index == n) {
			cout << i << '\n';
			return 0;
		}
	}
}

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

정렬문제입니다.

우선 일반적으로 생각할 수 있는 nXh 번 반복하여 값을 구하는 결과는 오답입니다. (시간초과)

O(n*h) = 200000 X 500000 번 반복하게 됩니다. 대략 1억번 반복에 1초라고 가정할때 당연한 결과 입니다.

완전탐색이 안된다면 고려해야할 것은 dp 혹은 그리디적 관점입니다. dp를 사용하기에는 결과값들 사이에 연관이 전혀 없습니다. 

정렬을 하고 결과값을 구할때 O(n)의 과정을 O(lgn)으로 줄일 수 있습니다. 

그방법은 이분탐색의 개념을 이용하는 것입니다. 정렬되어있는 상태라면 해당 높이를 기준으로 더큰 값들이 몇개 있는지 작은 값들이 몇개있는지 판단하는데 있어 평균적으로 lgn번의 탐색으로 값을 알 수 있습니다. 

직접구현해도 좋지만 C++의 lowerbound, upperbound를 사용해보겠습니다. 

사용 예시입니다. 선행조건은 꼭 정렬되어있는 배열을 넣어야합니다.

int val = lower_bound(arr, arr + n, num ) - arr ;
int val = upper_bound(arr, arr + n, num ) - arr ;

위처럼 사용하고 lower_bound는 arr배열의 0~n까지중  num값인덱스 중 제일 작은 값을 반환 합니다. 

upper_bound는 arr배열의 0~n까지중 num보다 큰 가장작은 값의 인덱스 값을 반환합니다.

즉 1 2 3 3 3 3 4 배열에서 num=2인 lowerbound는 1을 반환, upperbound는 2를 반환하는 형태입니다.

정답코드입니다. 

#include <iostream>
#include <algorithm>
using namespace std;
int arr[100001] = { 0 };
int arr2[100001] = { 0 };
int n, h;
int result = 200001, result_cnt = 0;


int main() {
	cin >> n >> h;

	for (int i = 0; i < n/2; i++) 
		cin >> arr[i ] >> arr2[i];
		
	sort(arr, arr + (n / 2));
	sort(arr2, arr2 + (n / 2));


	for (int i = 1; i <= h; i++) {

		int val = lower_bound(arr, arr + (n / 2), i ) - arr ;
		val += upper_bound(arr2, arr2 + (n / 2), h-i ) - arr2 ;
		val = n - val;

		if (result == val)
			result_cnt++;
		else if (result > val) { 
			result = val;
			result_cnt = 1;
		}
	}

	cout << result << ' ' << result_cnt << endl;

}

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

간만에 털렸습니다...

우선 시뮬레이션 문제로 인식했습니다. 문제에서 요구하는 조건 그대로 이동하면서 결과값을 도출하게 끔 구현을 했습니다.

문제조건인 

1. 현재 구슬이 놓인 노드의 자식이 없다면 그 자리에서 멈춘다.
2. 1을 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 한 개라면 해당 자식 노드로 떨어진다.
3. 1, 2를 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 두 개라면,
   1. 현재 노드의 왼쪽 서브트리에 담긴 모든 구슬의 수 <= 오른쪽 서브트리에 담긴 모든 구슬의 수일 경우, 왼쪽 자식 노드로 떨어진다.
   2. 그 외의 경우에는 오른쪽 자식 노드로 떨어진다.
4. 1~3번의 조건을 다시 체크하고 되풀이한다.

를 생각하면서 구현한 답입니다.

#include <iostream>
using namespace std;

int n, u, v;
long long k;
int result = 0;
struct node {
	int left = 0;
	int right = 0;
};
node arr[200001];
int cnt[200001] = { 0 };
int left_cnt, right_cnt;

void add_cnt(int current,int direction) {
	
	if (arr[current].left == 0 && arr[current].left == 0) {
		if (direction == 0)
			left_cnt += cnt[current];
		else
			right_cnt += cnt[current];

		return;
	}
	if (arr[current].left != 0)  add_cnt(arr[current].left,direction);
	if (arr[current].right != 0)   add_cnt(arr[current].right, direction);

}

void action(int current,int i) {

	//1
	if (arr[current].left == 0 && arr[current].left == 0) {
		cnt[current]++;

		result = current;
		return;
	}
	//2
	else if ((arr[current].left != 0 && arr[current].right == 0)) action(arr[current].left,i);
	else if ((arr[current].left == 0 && arr[current].right != 0)) action(arr[current].right,i);
	//3
	else if (arr[current].left != 0 && arr[current].left != 0) {
		/*
		left_cnt = 0, right_cnt = 0;
		add_cnt(arr[current].left,0);
		add_cnt(arr[current].right,1);
		if(left_cnt <= right_cnt) action(arr[current].left);
		else action(arr[current].right);	
		*/

		if(i%2) action(arr[current].left,i/2 +1);
		else action(arr[current].right, i/2);
	}
}

int main() {

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> u >> v;
		if (u != -1 || v != -1) {
			arr[i].left = u;
			arr[i].right = v;
		}
	}

	cin >> k;

	for (int i = 1; i <= k; i++)
		action(1,i); //루트는 항상 1번 노드이다.

	cout << result << endl;
	
}

이러한 방식입니다. 문제가 많은 코드입니다. 

왜냐하면 1 ≤ K ≤ 10^18, 1 ≤ N ≤ 200000  이기 때문에 저렇게 무식한 시뮬레이션으로는 문제를 시간초과가 납니다.

규칙을 찾아야합니다. 

위와 같은 문제 규칙에서 2번, 4번, 2번, 5번, 2번 노드에 차례대로 떨어지게 됩니다. 

루트노드입장에서 생각해봅시다. k번째를 반복하며 인덱스가 홀수에서는 왼쪽 짝수에서는 오른쪽으로 이동합니다.

3의 입장에서도 보면 인덱스가 홀수에서는 왼쪽 짝수에서는 오른쪽으로 이동합니다. 

이러한 규칙이 있기 때문에 굳이 시뮬레이션할 필요가 없습니다.

즉 k번을 반복하는게 아니라, k번째만 확인해 답을 구할 수 있습니다.

정답코드입니다.

#include <iostream>
using namespace std;
struct node {
	int left, right;
};

node arr[200001];

int main() {
	int n; long long k;

	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i].left >> arr[i].right;

	cin >> k;

	int pos = 1; //루트 노드에서 시작
	while (1) {
		//1
		if (arr[pos].left == -1 && arr[pos].right == -1) break;
		//2
		else if (arr[pos].left == -1) pos = arr[pos].right; //왼쪽노드가 없음 -> 오른쪽으로 이동
		else if (arr[pos].right == -1) pos = arr[pos].left; //오른쪽노드가 없음 -> 왼쪽으로 이동
															//3
		else if (k % 2) {//1)조건 -> 홀수면 왼쪽으로 간다.
			pos = arr[pos].left, k = k / 2 + 1;
		}
		else { //2)조건 -> 짝수면 오른쪽으로 간다.
			pos = arr[pos].right, k /= 2;
		}
	}
	cout << pos << endl;

	return 0;
}

이중에서  아래 코드를 봅시다.

while (1) {
		//1
		if (arr[pos].left == -1 && arr[pos].right == -1) break;
		//2
		else if (arr[pos].left == -1) pos = arr[pos].right; //왼쪽노드가 없음 -> 오른쪽으로 이동
		else if (arr[pos].right == -1) pos = arr[pos].left; //오른쪽노드가 없음 -> 왼쪽으로 이동
															//3
		else if (k % 2) {//1)조건 -> 홀수면 왼쪽으로 간다.
			pos = arr[pos].left, k = k / 2 + 1;
		}
		else { //2)조건 -> 짝수면 오른쪽으로 간다.
			pos = arr[pos].right, k /= 2;
		}
	}

1,2번 조건은 쉽게 이해하실겁니다. 아래 코드에서 k%2와 k/2를 통해서 위치를 판별합니다. 

루트기준으로 k번째에서의 떨어지는 방향은 홀수면 왼쪽으로 짝수면 오른쪽으로 이동합니다. 

그아래 노드들도 위에서 설명한 규칙대로 이동하기 때문에 k값의 짝,홀수 를 변경해주는 것 입니다. 

카카오 코드 페스티벌  의 카카오 코드 페스티벌 2018 예선 A번 문제입니다. 

간단한 프로그래밍 문제입니다. 

#include <iostream>
using namespace std;
int t = 0, a = 0, b = 0, result = 0;
void festival1(int num) {
	if (num == 1)
		result += 5000000;
	else if (num <= 3)
		result += 3000000;
	else if (num <= 6)
		result += 2000000;
	else if (num <= 10)
		result += 500000;
	else if (num <= 15)
		result += 300000;
	else if (num <= 21)
		result += 100000;
}
void festival2(int num) {

	if (num == 1)
		result += 5120000;
	else if (num <= 3)
		result += 2560000;
	else if (num <= 7)
		result += 1280000;
	else if (num <= 15)
		result += 640000;
	else if (num <= 31)
		result += 320000;
}
int main() {
	cin >> t;

	while (t--) {
		result = 0;
		cin >> a >> b;
		if (a != 0)
			festival1(a);
		if (b != 0)
			festival2(b);
		cout << result << endl;
	}
	
}