본문 바로가기
Problem Solving/template

ㅇㅅㅇ ㅡㅅㅡ

by kadokok 2022. 10. 6.

myCPP

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1 << 18;
const int MOD = 1e9 + 7;

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	
	return 0;
}

CCW, 선분 교차 판별

ll ccw(pll a, pll b, pll c) {
	ll ret =  (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);
	if (ret > 0) return 1;
	else if (ret == 0) return 0;
	else return -1;
}

bool isIntersect(pll a, pll b, pll c, pll d) {
	ll ab = ccw(a, b, c) * ccw(a, b, d);
	ll cd = ccw(c, d, a) * ccw(c, d, b);
	if (ab == 0 && cd == 0) { // 서로 평행하거나, 평행하진 않지만 끝점만 만남
		if (a > b) swap(a, b);
		if (c > d) swap(c, d);
		if (c <= b && a <= d) return true; // 서로 겹치거나, 끝점만 만남
		else return false;
	}
	else { // 평행하지 않으면서 교차
		if (ab <= 0 && cd <= 0) return true; // 서로 교차하거나, 선분 위에 한 점만 만나거나 
		else return false;
	}
}

구간 합 Lazy propagation

const int SIZE = 1 << 21; // SIZE == 1 << (ceil(log2(N)) + 1)

ll arr[1000001];
ll seg[SIZE];
ll lazy[SIZE];

// start, end는 표적 대상의 범위
// nodeLeft, nodeRight는 0, N - 1으로 시작하여 범위를 줄여나감 (0 based)

ll init(int node, int start, int end) {
	if (start == end) return seg[node] = arr[start];
	int mid = (start + end) >> 1;
	return seg[node] = init(node * 2, start, mid) + init(node * 2 + 1, mid + 1, end);
}

void update_lazy(int node, int nodeLeft, int nodeRight) {
	if (lazy[node] != 0) {
        // 만약 해당 세그먼트 트리 노드에 lazy 값이 있다면
		if (nodeLeft != nodeRight) {
			// 만약 리프노드가 아니라면 lazy 값을 자식노드에게 전파
			lazy[node * 2] += lazy[node];
			lazy[node * 2 + 1] += lazy[node];
		}
		seg[node] += lazy[node] * (nodeRight - nodeLeft + 1);
		lazy[node] = 0; // 자식에게 전파 후, 자신 lazy 값은 삭제
	}
    else return;
}

void update_range(int node, int start, int end, int nodeLeft, int nodeRight, ll k) {
	update_lazy(node, nodeLeft, nodeRight); // 항상 먼저 lazy 갱신 
	if (nodeLeft > end || nodeRight < start) return;
	if (start <= nodeLeft && nodeRight <= end) {
		lazy[node] += k;
		update_lazy(node, nodeLeft, nodeRight);
		return;
	}
	int mid = (nodeLeft + nodeRight) >> 1;
	update_range(node * 2, start, end, nodeLeft, mid, k);
	update_range(node * 2 + 1, start, end, mid + 1, nodeRight, k);
	seg[node] = seg[node * 2] + seg[node * 2 + 1];
}

ll sum_range(int node, int start, int end, int nodeLeft, int nodeRight) {
	update_lazy(node, nodeLeft, nodeRight); // 항상 먼저 lazy 갱신 
	if (nodeLeft > end || nodeRight < start) return 0;
	if (start <= nodeLeft && nodeRight <= end) return seg[node];
	int mid = (nodeLeft + nodeRight) >> 1;
	return sum_range(node * 2, start, end, nodeLeft, mid) + sum_range(node * 2 + 1, start, end, mid + 1, nodeRight);
}

 유니온 파인드

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

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	p[a] += p[b];
	p[b] = a;
}

큰 수 나머지

int getMod(string s, int d) {
	int ret = 0;
	for (int i = 0; i < s.size(); i++) {
		ret *= 10;
		ret += s[i] - '0';
		ret %= d;
	}
	return ret;
}

다익스트라 // O(E log V)

vector<pii> adj[1001];
int dist[1001];

int dijkstra(int start, int end) {
	for (int i = 0; i < 1001; i++) dist[i] = INF;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	dist[start] = 0;
	pq.push({0, start});
	while (!pq.empty()) {
		int cur_dist = pq.top().X;
		int cur_node = pq.top().Y;
		pq.pop();
		if (dist[cur_node] < cur_dist) continue;
		for (pii next : adj[cur_node]) {
			int next_node = next.X;
			int next_dist = dist[cur_node] + next.Y;
			if (next_dist >= dist[next_node]) continue;
			dist[next_node] = next_dist;
			pq.push({next_dist, next_node});
		}
	}
	return dist[end];
}

벨만 포드 // O(VE)

vector<pii> adj[51];
ll dist[51];
bool minusCycle;

void bellmanFord(int start, int n) {
	for (int i = 0; i < 51; i++) dist[i] = INF;
	minusCycle = false;
	dist[start] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (auto next : adj[j]) {
				int nextNode = next.X;
				ll nextDist = dist[j] + next.Y;
				if (dist[j] == INF || dist[nextNode] <= nextDist) continue;
				dist[nextNode] = nextDist;
				if (i == n - 1) minusCycle = true;
			}
		}
	}
}

compare 구조체 정의

struct A {
	int node;
	int cost;
};

struct compare {
	bool operator()(A& a, A& b) {
		return a.cost > b.cost; // cost 값을 기준으로 최소 힙
	}
};

struct compare {
	bool operator()(A& a, A& b) {
		return a.cost < b.cost; // cost 값을 기준으로 최대 힙
	}
};

최대 유량 (에드몬드-카프)

int c[305][305];
int f[305][305];
int prevv[305];
vector<int> adj[305];

int maximumFlow(int S, int E) {
	int total = 0;
	int source = S;
	int sink = E;
	while (1) {
		for (int i = 0; i < 305; i++) prevv[i] = -1;
		queue<int> que;
		que.push(source);
		while (!que.empty() && prevv[sink] == -1) {
			int node = que.front();
			que.pop();
			if (node == sink) break;
			for (int next : adj[node]) {
				if (c[node][next] == f[node][next] || prevv[next] != -1) continue;
				que.push(next);
				prevv[next] = node; 
			}
		}
		if (prevv[sink] == -1) break; // 싱크로 향하는 증가 경로가 더 이상 없다면 while문 탈출
		int flow = inf;
		for (int i = sink; i != source; i = prevv[i]) flow = min(flow, c[prevv[i]][i] - f[prevv[i]][i]);
		for (int i = sink; i != source; i = prevv[i]) {
			f[prevv[i]][i] += flow;
			f[i][prevv[i]] -= flow;
		}
		total += flow;
	}
	return total;
}

댓글