Junnnho

BOJ : https://www.acmicpc.net/problem/2470

이분탐색으로 해결가능하다.

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

typedef long long ll;
typedef pair<int, int> pii;
#define MAX 2000000001

ll arr[100005];
ll maxx = MAX;
pii ans;

void bound(int s, int e, ll key) {
	int m;

	while (s <= e) {
		m = (s + e) / 2;

		ll ret = abs(0 - (key + arr[m]));
		if (ret <= maxx) {
			maxx = ret;
			ans = { arr[m], key };
		}

		ll left = abs(0 - (key + arr[m-1]));
		ll right = abs(0 - (key + arr[m+1]));
		if (left <= right) e = m - 1;
		else s = m + 1;
	}
}

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

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

	sort(arr, arr + N);

	for (int i = 0; i < N; i++) {
		bound(0, i - 1, arr[i]);
		bound(i + 1, N-1, arr[i]);
	}

	if (ans.first > ans.second) swap(ans.first, ans.second);
	cout << ans.first << ' ' << ans.second;
}

에라토스테네스의 체 : 소수를 빠르게 구해낼 수 있는 알고리즘

2가지의 알고리즘이 있다.

1000 이하의 소수를 찾아내보자

1. 반복문을 통해 약수를 걸러내는 방법을 이용한 알고리즘

2. 소수는 소수로 나누어 떨어지지 않는다는 방법을 이용한 알고리즘

소수의 범위가 클수록 2번의 방법은 각 숫자마다 벡터에 담긴 소수를 통해 약수를 확인해야하므로 비효율적이다.

==> 범위가 클수록 1번의 약수를 거르는 방법을 이용한다.

어떤 방법이든 소수에 관한 문제를 풀 때 가장 중요한 요점은

임의의 소수는 제곱근보다 큰 수로는 나누어 떨어지지 않는다는 것이다.

이것만 기억해둬도 시간해결에 큰 영향을 미치게 될 것이다.

관련 풀어본 백준 문제들 :

셀프 넘버 - https://www.acmicpc.net/problem/4673

소수 찾기 - https://www.acmicpc.net/problem/1978

소수 구하기 - https://www.acmicpc.net/problem/1929

베르트랑 공준 - https://www.acmicpc.net/problem/4948

골드바흐의 추측 - https://www.acmicpc.net/problem/9020

소수의 연속합 - https://www.acmicpc.net/problem/1644

제곱 ㄴㄴ 수 - https://www.acmicpc.net/problem/1016

BOJ : https://www.acmicpc.net/problem/11729

문제에서 하노이탑을 이동한 과정을 보면 

원판이 3개 일때

1 3

1 2

3 2

1 3

2 1

2 3

1 3

의 순서대로 옮긴 것을 확인할 수 있다. 정답을 기준으로 따라가보면

이는 원판이 3개라고 가정했을 때 최종적으로 장대1의 원판3개를 장대3으로 옮기기 위한 과정은

1을 장대3 => 2을 장대2 => 1을 장대2 로 옮겨서 장대1:3 // 장대2:12 // 장대3:x 로 옮겼다는 것을 볼 수 있다.

이는 장대1의 원판의 남은 갯수가 1이 되도록 다른 원판을 장대2로 옮긴 것이다. (알고리즘1)

그리고 나서 장대1의 3을 장대3으로 옮겼다. (알고리즘2)

그리고 나서 장대2의 1,2를 장대3으로 옮겼다. (알고리즘3)

이 3가지의 분할 알고리즘으로 하노이 원판을 이동시킬 수 있다.

BOJ : https://www.acmicpc.net/problem/1780

3^ 형태로 분할되는 형태의 문제입니다.

현재 분할된 지점을 체크해서 -1,0,1 에 대한 값을 확인해주시고 재분할시 조건에 맞게 분할해주시면 됩니다.