햇갈리는 알고리즘 복습

1. 소수 판별 알고리즘

에라토스테네스 + bitmask (비트마스크) 방법

#include <iostream>
#include <bitset>
#define MAX 10000001

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;	// range [m, n]
  
    bitset<MAX> sieve;
    sieve.set();
    sieve.reset(0), sieve.reset(1);	// 0 and 1 is not prime.
    // find prime numbers in [0, MAX]
    for (int i = 2; i * i < MAX; ++i) {
        if (!sieve.test(i)) continue;	// i is not prime.
        for (int j = i + i; j < MAX; j += i) sieve.set(i);
    }
    int input, answer = 0;
    for (int i = 0; i < n; ++i) {
        cin >> input;
        if (mask.test(input)) answer++;
    }
    cout << answer << '\n';
}

2. 다익스트라 알고리즘

시간복잡도: $O(ElogV)$
모든 간선의 가중치가 양수일 때만 사용.

// 다익스트라 복습
#include <iostream>
#include <queue>
#include <vector>
#define INF 2e9
using namespace std;

static int n, k, s, dist[100001];
static vector<pair<int, int>> graph[100001];

void dijkstra() {
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > pq;
	pq.push({0, s});
	dist[s] = 0;
	
	while (!pq.empty()) {
		int cd = pq.top().first, cv = pq.top().second;
		pq.pop();
		for (const auto& next : graph[cv]) {
			int nd = cd + next.first, nv = next.second;
			if (dist[nv] > nd) {
				dist[nv] = nd;
				pq.push({nd, nv});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> k >> s;
	int s, e, w;
	for (int i = 0; i < k; ++i) {
		cin >> s >> e >> w;
		graph[s].push_back({w, e});
	}
	fill_n(dist, n + 1, INF);
	dijkstra();
	
	for (int i = 1; i <= n; ++i) {
		if (dist[i] == INF) cout << "INF\n";
		else cout << dist[i] << '\n';
	}
}

3. 벨만포드 알고리즘

음수 간선 가중치가 있을 때 사용 가능.
시간 복잡도: $O(VE)$ 로 다익스트라보다 느리다.
음수 간선 합 사이클의 존재 여부 판단 가능. 존재할 때 해당 그래프는 잘못된 것.

// 벨만포드 복습
#include <iostream>
#include <vector>
#define INF 1e9
using namespace std;

static int n, m;
static long long d[501]; 
static vector<pair<int, pair<int, int> > > edges;

bool bellmanFord(int start) {
    d[start] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int cv = edges[j].first, nv = edges[j].second.first, w = edges[j].second.second;
            if (d[cv] != INF and d[nv] > d[cv] + w) {
                d[nv] = d[cv] + w;
                if (i == n - 1) return true;
            }
        }
    }
    return false;
}

int main(void) {
	ios::sync_nvith_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        edges.emplace_back({v1, {v2, w}});
    }
    fill_n(d, 501, INF);
    if (bellmanFord(1)) { cout << "-1" << '\n'; return 0; }
    for (int i = 2; i <= n; i++) {
        if (d[i] == INF) cout << "-1" << '\n';
        else cout << d[i] << '\n';
    }
}

4. 크루스칼 알고리즘

Union-find에 경로압축쓰면 아주 효과적이다.
시간복잡도는 $O(ElogE)$로 알려져있음.
간선을 반드시 오름차순으로 정렬해야하기 때문에 E < 3V 일 때 쓰기 적절한 알고리즘.

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

typedef struct Edge {
	int s, e, w;
	Edge(int s = 0, int e = 0, int w = 0) : s(s), e(e), w(w){}
}Edge;

static int root[10001];
static Edge edges[100000];

int findOp(int v) {
	if (root[v] == v) return v;
	return root[v] = findOp(root[v]);
}

void unionOp(int a, int b) {
	a = findOp(a), b = findOp(b);
	root[b] = a;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int v, e;
	cin >> v >> e;
	for (int i = 1; i <= v; ++i) root[i] = i;	// Important!
	
	int start, end, weight;
	for (int i = 0; i < e; ++i) {
		cin >> start >> end >> weight;
		edges[i] = Edge(start, end, weight);
	}
	sort(edges, edges + e, [](const Edge& lhs, const Edge& rhs) { return lhs.w < rhs.w; });
	int v1, v2, cost, comp = 0, answer = 0;
	for (int i = 0; i < e; ++i) {
		v1 = edges[i].s, v2 = edges[i].e, cost = edges[i].w;
		if (findOp(v1) != findOp(v2)) {
			unionOp(v1, v2);
			answer += cost;
			if (++comp == v - 1) break;
		}
	}
	cout << answer << '\n';
}

5. 프림 알고리즘

다익스트라와 굉장히 유사하게 동작하는 알고리즘.
E > 3V 일 때 사용하기 좋은 알고리즘이지만 잘 쓰이지는 않음.
시간복잡도는 $O(V^2)$으로 알려져있음.
중요한 점이 있다면 무향 그래프에서만 동작한다는 점임. 따라서 방향 그래프는 모두 무향그래프로 바꿔서 적용해줘야 함.

#include <iostream>
#include <vector>
#include <queue>
#define INF 2147483647
using namespace std;
// Prim 알고리즘은 인접리스트가 답이다.
	// 이유 1. pq에 시작정점과 연결된 간선 정보를 넣어서 초기화 해야하기 때문
	// 이유 2. 무방향 그래프이기 때문에 인접행렬은 메모리 오버플로우 발생 때문

static int n, k, dist[10001];
static bool visited[10001];
static vector<pair<int, int> > edges[100000];

int prim(int sv) {
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > pq;
	pq.push({0, sv});
	for (const auto& edge : edges[sv]) pq.push({edge.first, edge.second});
	visited[sv] = true;
	dist[sv] = 0;
	
	int answer = 0;
	while (!pq.empty()) {
		int cd = pq.top().first, cv = pq.top().second;
		pq.pop();
		if (!visited[cv]) {
			visited[cv] = true;
			answer += cd;
			for (const auto& edge : edges[cv]) {
				int nd = edge.first, nv = edge.second;
				if (!visited[nv] && dist[nv] > nd) {
					dist[nv] = nd;
					pq.push(edge);
				}
			}
		}
	}
	return answer;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> k;
	for (int i = 0; i < k; ++i) {
		int v1, v2, w;
		cin >> v1 >> v2 >> w;
		edges[v1].push_back({w, v2});
		edges[v2].push_back({w, v1});	// Prim used for non-direction graph.
	}
	fill_n(dist, n + 1, INF);
	cout << prim(1) << '\n';
}