슥지니의 코딩노트

사용 전 배열, vector 오름차순 정렬 필요

1. 직접 구현하기

lower_bound

#include<iostream>
using namespace std;

#define MAX_N 500000

int n;
int arr[MAX_N];

//lower_bound(x) : x보다 같거나 큰 수 중에 가장 왼쪽에 있는 수의 인덱스
int lower_bound(int x) {
	int left = 0;
	int right = n - 1;
	int ret = n; // 같거나 큰 최초의 위치를 찾아야 하므로 최악을 고려해서 n이 초깃값이 되어야 함
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] >= x) { // mid 값이 관심있는 영역이라면
			ret = mid;
			right = mid - 1; //가장 왼쪽에 있는 수의 인덱스를 찾아야 하니깐, 왼쪽 부분을 살펴봄

		}
		else { //mid 값이 관심있는 영역이 아니라면
			left = mid + 1;
		}
	}
	return ret;
}

upper_bound

// upper_bound(x) : x보다 큰 수 중에 가장 왼쪽에 있는 수의 인덱스
int upper_bound(int x) {
	int left = 0;
	int right = n - 1;
	int ret = n; // x보다 큰 최초의 위치를 찾아야 하므로 최악을 고려해서 n이 초깃값이 되어야 함
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] > x) { // mid 값이 관심있는 영역이라면
			ret = mid;
			right = mid - 1;  //가장 왼쪽에 있는 수의 인덱스를 찾아야 하니깐, 왼쪽 부분을 살펴봄
		}
		else { //mid 값이 관심있는 영역이 아니라면
			left = mid + 1;
		}
	}
	return ret;
}

2. STL 사용하기

STL은 배열이라면 포인터를 리턴하고 vector라면 iterator를 리턴합니다.

lower_bound

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

int main(void) {
	vector<int> v({ 1, 2, 3, 3, 3, 6, 7, 8, 9, 10 });
	cout << lower_bound(v.begin(), v.end(), 3) - v.begin() << '\n'; // idx : 2
	return 0;
}

upper_bound

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

int main(void) {
	vector<int> v({ 1, 2, 3, 3, 3, 6, 7, 8, 9, 10 });
	cout << upper_bound(v.begin(), v.end(), 3) - v.begin() << '\n'; // idx : 5
	return 0;
}

단절선이란 무방향 그래프에서 해당 간선을 제거했을 때 그래프가 두 개 이상으로 나누어질 때 그 간선을 단절선이라고 합니다.

단절선은 단절점을 구하는 것과 유사합니다.

https://seokjin2.tistory.com/87

정점 A에서 부모 노드를 제외한 자식 노드들이 역방향 간선(backward edge)을 통해서 정점 A에 갈 수 없고 정점 A보다 위에 있는 선조로 갈 수 없으면 정점 A는 단절점이 됩니다.

단절점과 다른 점은 다음 두 가지입니다.

1. 루트가 빠졌다.

2. low > visited[A] (등호가 빠졌다) 

<C++ 소스 코드>

<백준 문제>

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

단절점이란 무방향 그래프에서 해당 정점을 제거했을 때 그래프가 두 개 이상으로 나누어질 때 그 정점을 단절점이라고 합니다.

먼저 간단하게 생각할 수 있는 방법은 모든 정점에 대해서 정점 하나를 삭제해보고 DFS를 돌려서 그래프의 개수를 세보면 됩니다. 이때 시간 복잡도는 정점의 개수를 V, 간선의 개수를 E라고 할 때 O(V * (V + E) )가 됩니다.

그러나 위 방식은 비효율적이고 O(V + E) 시간복잡도로 단절점을 구할 수 있는 방법이 있습니다.

바로 DFS spanning tree를 이용하는 방법입니다.

위와 같은 그래프가 있을 때 DFS spanning tree로 번호를 매겨보겠습니다.

DFS spanning tree에서 단절점을 찾는 방법은

정점 A에서 부모 노드를 제외한 자식 노드들이 역방향 간선(backward edge)을 통해서 정점 A보다 위에 있는 선조로 갈 수 없으면 정점 A는 단절점이 됩니다.

6번 정점을 예로 들면

정점 6에서 부모 노드 1을 제외한 자식 노드인 7이 역방향 간선을 통해서 정점 6보다 위에 있는 선조 1로 갈 수 없으니깐 정점 6은 단절점이 됩니다.

2번 정점을 예로 들면

정점 2에서 부모 노드 7을 제외한 자식노드인 3이 역방향 간선을 통해서 정점 2보다 위에 있는 선조 7로 갈 수 있으니 정점 2는 단절점이 아닙니다.

그런데 루트 노드의 경우엔 선조가 없기 때문에 예외가 발생합니다.

루트 노드일 땐 루트의 자식 노드의 개수를 계산해서 자식 노드 수가 2 이상일 때 단절점이라고 판단하면 됩니다.

<C++ 소스 코드>

<백준 문제>

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

1차원 배열에서 연속되는 값들을 이용해서 문제를 해결해야할 때 두 개의 포인터를 이용해 원하는 결과를 얻는 알고리즘

대표 문제: https://www.acmicpc.net/problem/2003

위 문제는 배열에서 i ~ j 부분합이 M을 만족하는 모든 경우의 수를 구하는 문제이다.

부분 배열의 시작과 끝을 가리키는 변수 s, e을 준비하고 부분합을 저장할 변수 sum을 준비한다.

다음을 반복한다. while(true)

    1. 현재 부분합이 M과 같다면 경우의 수 카운트++

    2. 현재 부분합이 M 이상이면 sum에서 s가 가리키는 원소의 값을 빼고 s++

    3. e == n 즉 e가 배열에 끝에 도달하면 break

    4. 현재 부분합이 M 미만이면 sum에 e가 가리키는 원소의 값을 더하고 e++

<C++ 소스코드>

참조
https://blog.naver.com/kks227/220795165570

에라토스테네스의 체 (시간 복잡도O(N log log N) )

고대의 그리스 수학자 에라토스테네스에 의하여 개발된 정해진 범위 안의 소수를 찾는 알고리즘

2부터 N까지의 수를 적고 다음을 반복한다.

2부터 시작해 1씩 증가하면서 시작 수가 지워지지 않았다면 시작한 수를 제외하고 그 수의 배수를 모두 지운다. (배수들은 소수가 아니므로 지움)

시작 수를 정할때는 sqrt(N)까지만 보면 됩니다. (N이 소수임을 판별할 때 sqrt(N)까지만 보는 이유와 같음)

( sqrt(N) 소수 판정 알고리즘: https://seokjin2.tistory.com/17) )

배수를 지울때 시작 수의 제곱인 i*i 시작합니다.

왜냐하면 (2*i), (3*i), .... (i-1)(i)는 각각 2의 배수, 3의 배수, (i-1)의 배수에서 이미 지워졌기 때문에 그다음인 i*i부터 시작하면 됩니다,

<C++ 소스코드>

소수는 1보다 크고 1과 자기 자신으로만 나눠지는 자연수입니다.

자연수 N이 소수임을 판별하는 방법은 2부터 n-1까지의 자연수로 자연수 N을 나눴을 때 나누어 떨어지는지 보면 됩니다.

만약 2부터 n-1까지의 자연수 중에 하나라도 나누어 떨어지면 자연수 N은 소수가 아닙니다.

그런데 이렇데 n-1까지 나누어 보는 방식은 O(N)의 시간 복잡도가 걸립니다.

n-1까지 나누어 떨어지는지 다 확인할 필요가 없고 sqrt(N)까지만 나누어 봐도 소수임을 판별할 수 있고 이때 시간 복잡도는 O(sqrt(N))입니다.

<C++ 소스 코드>

<증명>

자연수에서 두 개 이상의 소수의 곱으로 이루어져 있는 수, 1과 소수를 제외한 수를 합성수라고 합니다.

어떤 수가 합성수가 아님을 판별하면 그 수는 소수입니다.

​

자연수 N을 N = P X Q (P <= Q, P 와 Q 는 1과 N이 아닌 자연수)을 만족하는 합성수라고 가정했을 때

​

N = P X Q >= Q x Q = Q ^ 2

-> Q <= sqrt(N)

따라서 N은 sqrt(N)보다 작은 적어도 하나의 인수를 가지므로 sqrt(N)까지만 나누어보면 됩니다.