Kcode

소수를 구하는 여러 알고리즘들이 있지만 그중에서 자주 사용되는 것은

에라토스테네스의 체이다.

한번 틀을 짜놓고 외우면 이후에 쉽게 사용 가능하다.

그 외에도 비트마스크를 이용해서 소수를 구하면 메모리를 무려 1/8이나 절감시킬 수 있다.

이런 식으로 전처리해주고 사용하면 된다.

플로이드 와샬 알고리즘은 다익스트라, 벨만 포드 알고리즘과 달리 '모든 정점에서 다른 정점까지의 최단거리'를 구한다.

다익스트라처럼 큐에 넣어서 거쳐가는 지점을 뽑아 쓰는 것과 달리 플로이드 와샬은

거쳐가는 지점을 중심으로 해서 다시 모든 노드를 탐색한다. 따라서 시간 복잡도는 \(O(N^3)\) 이 걸린다.

www.acmicpc.net/problem/11404

문제 풀이를 통해 알아보면 시간 복잡도가 높은 만큼 입력 범위는 작게 100으로 주어진다.

	for (int k = 0; k < n; k++) { //k = 거처가는 노드
		for (int i = 0; i < n; i++) { // i = 시작 노드
			for (int j = 0; j < n; j++) { // j = 도착 노드
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
				//i -> j = min(시작 -> 도착, 시작 -> 거처가는 노드 + 거처가는 노드 -> 도착 노드)
			}
		}
	}

놀랍지만 저 코드가 플로이드 와샬 알고리즘을 나타낸다. 

중간에 거쳐가는 모든 노드에 대해 각 정점들을 전부 탐색하다 보니 다익스트라는 1차원 배열을 사용하지만

플로이드 와샬은 2차원 배열을 사용하여 i -> j로 가는 최단거리를 모두 나타낸다.

다익스트라나 벨만 포드와 달리 모든 정점을 INF로 초기화하지 않고 i == j 인 부분에 대해 0으로 처리해준다.

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			d[i][j] = i == j ? 0 : INF;
		}
	}

자기 자신으로 가는 최단거리는 0이므로 d [i][i]인 모든 부분을 0으로 초기화해줘야 한다.

#include <iostream>
using namespace std;

const int INF = 1e9;
int d[101][101];
int n, m, a, b, c;

int min(int a, int b) { return a > b ? b : a; }

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

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			d[i][j] = i == j ? 0 : INF;
		}
	}

	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		d[a - 1][b - 1] = min(d[a - 1][b - 1], c);
	}

	for (int k = 0; k < n; k++) { //k = 거처가는 노드
		for (int i = 0; i < n; i++) { // i = 시작 노드
			for (int j = 0; j < n; j++) { // j = 도착 노드
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
				//i -> j = min(시작 -> 도착, 시작 -> 거처가는 노드 + 거처가는 노드 -> 도착 노드)
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (d[i][j] >= INF) cout << 0 << ' ';
			else cout << d[i][j] << ' ';
		}
		cout << '\n';
	}

	return 0;
}

Bellman - Ford 알고리즘은 다익스트라 알고리즘과 달리 

모든 노드를 주기적으로 갱신시켜주기 때문에 \(O(V*E)\)가 걸리지만

음의 가중치를 포함한 노드들에 대해서도 성공적으로 탐색할 수 있다.

www.acmicpc.net/problem/11657

대표적인 벨만 - 포드를 사용한 문제이다.

우선 각 간선의 수만큼 입력을 받는데 편하게 계산하기 위해 좌표들에 -1씩 해서 받아줬다.

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		ar[a - 1].push_back({ b - 1,c });
	}

문제 조건 중 

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다.

라는 조건이 있다.

이 문제를 풀 때에는 조심해야 할 점이 있는데 그래프에 음의 사이클이 포함되어 있는가?이다.

음의 사이클이 포함되어 있다면 그 사이클이 나오기 전까지의 노드들만 정상으로 갱신될 것이고 그 이후의

값들은 모두 음의 무한대 값이 나올 것이다.

void bellmanford() {
	cost[0] = 0;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n; j++) {
			for (auto& i : ar[j]) {
				int nxt = i.first, d = i.second;
				if (cost[j] != INF && cost[nxt] > cost[j] + d) {
					cost[nxt] = cost[j] + d;
				}
			}
		}
	}
}

위와 같은 코드가 기본적인 벨만 - 포드의 틀이라 할 수 있는데 이 코드는 음의 가중치가 포함되어있는 그래프를

찾지 못한다.

• 각 vertax - 1 만큼 돌려주는 중첩 문에 대해서 (vertax - 1) + 1 만큼 돌려준다
• 현재 vertax -1까지 돌렸으면 모든 갱신이 완료된 것이다. 하지만,
• 맨 마지막(vertax ( -1 + 1))에 갱신이 된다면 사이클에 빠져 무한히 갱신하게 된다는 뜻이다

위와 같은 접근법으로 해결한다.

bool bellmanford(int start) {
	dst[start] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (auto& v : ar[j]) {
				int nxt = v.first;
				int d = v.second;
				if (dst[j] != INF && dst[nxt] > dst[j] + d) {
					dst[nxt] = dst[j] + d;
					if (i == n - 1) return true;
				}
			}
		}
	}
	return false;
}

n -1 이 아닌 n 번 돌리며 마지막에 갱신이 된다면 음의 가중치를 포함하고 있다는 뜻이다.

전체적인 소스 코드

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const ll INF = 1e18;
int n, m, a, b, c;
vector<ll> dst(501, INF);
vector<pair<int, int>> ar[501];

bool bellmanford(int start) {
	dst[start] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (auto& v : ar[j]) {
				int nxt = v.first;
				int d = v.second;
				if (dst[j] != INF && dst[nxt] > dst[j] + d) {
					dst[nxt] = dst[j] + d;
					if (i == n - 1) return true;
				}
			}
		}
	}
	return false;
}

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		ar[a - 1].push_back({ b - 1,c });
	}
	
	if (bellmanford(0)) {
		cout << -1 << endl;
	}
	else {
		for (int i = 1; i < n; i++) {
			int ans = dst[i] != INF ? dst[i] : -1;
			cout << ans << '\n';
		}
	}

	return 0;
}

Disjoint-Set (서로수 집합) 이라고도 불리는 유니온 파인드는 여러 집합이 주어지면 각 집합의 루트 노드가 무엇인지,

또는 Union(합집합) 연산을 손쉽게 하기 위한 일종의 자료구조이다.

큰 틀로는 집합의 부모 노드를 찾는 find 함수, 각 집합을 병합하는 union 함수를 만들어주면 된다.

int find(int x) {
	if (parent[x] < 0) return x;
	parent[x] = find(parent[x]);
	return parent[x];
}

find 함수부터 살펴보면 parent배열의 초기값은 -1로 설정해둔다(이후에 집합의 크기를 알기 쉽게 하기 위해)

만약 parent [x]가 0보다 작다는 소리는 그 노드가 루트 노드임을 알 수 있다.

그대로 x를 반환하면 된다.

만약 루트 노드가 아닐경우 재귀적으로 그 노드의 부모 노드를 호출하여 parent [x]에 담는다. 이후 모든 호출이 끝나면 

parent [x]를 리턴해주면 된다.

void merge(int x, int y) {
	x = find(x);
	y = find(y);

	if (x != y) parent[y] = x;
}

merge는 union연산이다. C언어에서는 union이 이미 사용되고 있기 때문에 union함수명을 사용할 수 없다.

두 집합이 주어지면 그 두 집합의 부모 노드를 찾아서 그 노드가 서로 같지 않다면(같은 집합이 아니라면)

한 노드에 다른 노드를 붙여주기만 하면 된다.

백준에서 연습해볼 만한 문제로는

www.acmicpc.net/problem/1717

집합의 표현이 있다. 문제를 읽어보면 0 ~ n까지 집합을 병합하고

그 집합이 같으면 YES 아니면 NO를 출력해주면 된다.

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

vector<int> parent;
int n, m, a, b, input;

int find(int x) {
	if (parent[x] < 0) return x;
	parent[x] = find(parent[x]);
	return parent[x];
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);

	if (x != y) parent[y] = x;
}

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

	cin >> n >> m;
	parent.resize(n + 1, -1);

	while (m--) {
		cin >> input >> a >> b;

		if (input == 0) merge(a, b);
		else if (input == 1) {
			if (find(a) == find(b)) cout << "YES" << '\n';
			else cout << "NO" << '\n';
		}
	}

	return 0;
}

유니온 파인드는 이후 다른 알고리즘에 융합되어 사용된다고 한다.

여러 문제들을 풀면서 경우의 수를 따질 때 모든 경우의 수를 따지기 좋은 것이

바로 순열과 조합인 걸 느끼고 정리를 해보려 한다.

• 중복을 포함하지 않는 순열
• 중복을 포함한 순열
• 중복을 포함하지 않는 조합
• 중복을 포함한 조합

이렇게 4가지로 나눌 수 있을 것 같다.

각각의 방법에 대해서 DFS와 c++의 algorithm 헤더 파일의 next_permutation을 사용해서 만들 수 있다.

모든 순열과 조합에 대해서 n개 중에서 m개를 뽑는 경우의 수를 보자.

• 중복을 포함하지 않는 순열(DFS)

#include <iostream>
using namespace std;
	
int ar[10], n, m;
bool vis[10];

void DFS(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) {
			cout << ar[i] << ' ';
		}
		cout << '\n';
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			vis[i] = true;
			ar[cnt] = i;
			DFS(cnt + 1);
			vis[i] = false;
		}
	}
}

int main() {
	cin >> n >> m;
	DFS(0);

	return 0;
}

순열과 조합은 기본적인 틀이 있는 것 같다.

cnt == m 이 되는 경우 ar 배열에 들어있는 수들을 출력해주고 아니라면

vis 배열을 통해서 중복을 체크해준다. 중복되지 않은 수라면 DFS를 한번 더 사용해서 가지치기하는 식으로 사용해주는 틀을 벗어나지 않는다.

따라서 중복을 포함하게 해주려면

• 중복을 포함한 순열

#include <iostream>
using namespace std;

int ar[10], n, m;

void DFS(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) {
			cout << ar[i] << ' ';
		}
		cout << '\n'; return;
	}
	for (int i = 1; i <= n; i++) {
		ar[cnt] = i;
		DFS(cnt + 1);
	}
}

int main() {
	cin >> n >> m;
	DFS(0);

	return 0;
}

그냥 vis 배열을 지워주면 방문을 처리하지 않으니 중복해서 뽑는다. 조심해야 할 점은 cnt == m 일 때 출력을 전부 하고 return;을 통해 종료를 해줘야 한다는 것이다. 종료하지 않으면 roof에 빠져서 탈출하지 못한다.

조합도 비슷하다.

• 중복을 포함하지 않는 조합

#include <iostream>
using namespace std;

int ar[10], n, m;
bool vis[10];

void DFS(int cnt, int idx) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) {
			cout << ar[i] << ' ';
		}
		cout << '\n'; 
	}
	for (int i = idx; i <= n; i++) {
		if (!vis[i]) {
			vis[i] = true;
			ar[cnt] = i;
			DFS(cnt + 1, i);
			vis[i] = false;
		}
	}
}

int main() {
	cin >> n >> m;
	DFS(0, 1);

	return 0;
}

순열과의 차이점은 idx인자를 넘겨주는 것이다 idx변수를 통해서 이전에 방문한 순열은 다시 보지 않게 처리할 수 있다.

예를 들어 1, 4와 4, 1은 수열에서 표시되지만 조합에서는 표시되지 않는다.

• 중복을 포함한 조합

#include <iostream>
using namespace std;

int ar[10], n, m;

void DFS(int cnt, int idx) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) {
			cout << ar[i] << ' ';
		}
		cout << '\n'; return;
	}
	for (int i = idx; i <= n; i++) {
		ar[cnt] = i;
		DFS(cnt + 1, i);
	}
}

int main() {
	cin >> n >> m;
	DFS(0, 1);

	return 0;
}

중복을 포함시키려면 마찬가지로 vis 배열만 지워주면 된다.

이번에는 다익스트라 알고리즘을 공부해 봤다.

사실 다익스트라는 너무 잘 알려진 알고리즘이라 다른 여러 블로그들을 참고해서 

www.acmicpc.net/problem/1753

이 문제를 푸는 식으로 알아봤다.

const int INF = 1e9;
vector<pair<int, int>> ar[20001]; // ar[from].push_back({to, cost}) from -> to , 가중치
vector<int> d; // 거리값을 갱신해주는 배열

일단 기본적으로 가중치가 포함된 간선을 연결해줄 배열을 선언하고, 최단거리를 갱신해줄 배열도 필요하다.

void dijkstra(int s) {
	d[s] = 0;
	priority_queue<pair<int, int>> PQ; 
	PQ.push({ 0,s });
	while (!PQ.empty()) {
		int cur = PQ.top().second;
		int dist = -PQ.top().first;
		PQ.pop();
		if (d[cur] < dist) continue;
		for (auto i : ar[cur]) { 
			int nxt = i.first;		
			int nxtdist = dist + i.second; 
			if (nxtdist < d[nxt]) { 
				d[nxt] = nxtdist;
				PQ.push({ -nxtdist,nxt });
			}
		}
	}
}

기본적인 틀은 이렇다.

	d[s] = 0; //시작값은 0으로 초기화 후 시작
	priority_queue<pair<int, int>> PQ; //가중치, 현재 위치
	PQ.push({ 0,s });

처음 들어온 시작점은 0으로 초기화해주고 큐에 가중치, 현재 위치 순으로 넣어주는데

순서가 바뀌면 이상한 값을 건드려서 시간 초과가 난다.

		int cur = PQ.top().second;
		int dist = -PQ.top().first;
		//cout << "cur = " << cur << " dist = " << dist << '\n';

PQ의 두번째 값인 위치를 cur에 저장해주고 첫 번째 값인 가중치를 dist에 넣어준다.

이때 거리에 -를 붙혀서 최소 힙으로 바꿔줘야 한다.

여러 가중치들 값 중에서 가장 작은 값만을 사용해야 하니까.

		if (d[cur] < dist) continue;
		for (auto i : ar[cur]) { //i.first = 위치, i.seoncd = 가중치
			int nxt = i.first;		//여기서 여러 간선들의 가중치들을 구하지만..
			int nxtdist = dist + i.second; 
			if (nxtdist < d[nxt]) { //이 조건문에서 가장 최단거리만 갱신시켜줌
				d[nxt] = nxtdist;
				//printf("d[%d] = %d\n", nxt, d[nxt]);
				PQ.push({ -nxtdist,nxt });
			}
		}

주석 처리한 것과 같이 각 원소들의 연결점을 돌면서 다음 구간의 가중치와 위치를 저장해준다.

이후 if문에서 가장 작은 값만 갱신해주면 된다.

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

const int INF = 1e9;
vector<pair<int, int>> ar[20001]; // ar[from].push_back({to, cost}) from -> to , 가중치
vector<int> d; // 거리값을 갱신해주는 배열

void dijkstra(int s) {
	d[s] = 0; //시작값은 0으로 초기화 후 시작
	priority_queue<pair<int, int>> PQ; //가중치, 현재 위치
	PQ.push({ 0,s });
	while (!PQ.empty()) {
		int cur = PQ.top().second;
		int dist = -PQ.top().first;
		//cout << "cur = " << cur << " dist = " << dist << '\n';
		PQ.pop();
		if (d[cur] < dist) continue;
		for (auto i : ar[cur]) { //i.first = 위치, i.seoncd = 가중치
			int nxt = i.first;		//여기서 여러 간선들의 가중치들을 구하지만..
			int nxtdist = dist + i.second; 
			if (nxtdist < d[nxt]) { //이 조건문에서 가장 최단거리만 갱신시켜줌
				d[nxt] = nxtdist;
				//printf("d[%d] = %d\n", nxt, d[nxt]);
				PQ.push({ -nxtdist,nxt });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int v, e, k;

	cin >> v >> e >> k;
	d.resize(v + 1, INF);

	for (int i = 0; i < e; i++) {
		int x, y, z; cin >> x >> y >> z;
		ar[x].push_back({ y,z });
	}

	dijkstra(k);

	for (int i = 1; i <= v; i++) {
		if (d[i] == INF) cout << "INF" << ' ';
		else cout << d[i] << ' ';
	}
	cout << endl;

	return 0;
}

전체적인 소스코드는 이렇다.

백준 문제를 풀던 중 약수에 대해 공부할 기회가 생겨 찾아보던 중에 에라토스테네스의 채와 같이 제곱근의 형태를 띄는 최적화를 알게 되었다.

	for (int i = 1; i <= n; i++) {
		if (n % i == 0) cout << i << ' ';
	}

기본적인 약수 구하는 방법은 O(N)으로 구하려는 수가 i를 돌면서 나누어 떨어진다면 약수이다. 그러나 이 식으로는 21억같은 큰 수들은 꽤 오랜 시간이 걸린다.

이를 위해서 약수의 특성을 이용하여

	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) cout << i << ' ' << n / i << ' ';
	}

이런 식으로 하여금 구할 수 있다.

int 형 범위의 대푯값인 21억을 넣어서 확인해봤다.

간단한 코드 차이지만 눈에 띄게 시간이 줄어든다. 

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

int main() {
	int n;
	vector<int> ar;
	cin >> n;
	clock_t start = clock();
	//for (int i = 1; i <= n; i++) {
	//	if (n % i == 0) ar.push_back(i);
	//}
	//cout << endl;
	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) cout << i << ' ' << n / i << ' ';
	}
	cout << endl;

	sort(ar.begin(), ar.end());
	ar.erase(unique(ar.begin(), ar.end()), ar.end());
	for (int i = 0; i < ar.size(); i++) cout << ar[i] << ' ';
	cout << endl;

	clock_t end = clock();
	cout << "TIME: " << (end - start) / CLOCKS_PER_SEC << endl;

	return 0;
}

약수일 때마다 벡터에 푸쉬해주고 정렬한 뒤 중복되는 수를 제거해서 출력해줬다.