본문 바로가기

알고리즘 관련/알고리즘&이론

advanced disjoint set 오늘은 disjoint set에 대해서 글을 적어보겠습니다. 직역하면 상호배타적 집합이며, union-find 라는 자료구조로 표현됩니다. [disjoint set, DSU(disjoint union),union find] 는 전부 union find 자료구조를 칭하는 말입니다. union find 는 union연산과 find연산을 매우 빠르게 해주는 자료구조로서, 상호배타 집합에서는 어떠한 집합에서도 공통 된 원소가 존재하지 않으며, 동시에 모든 집합의 합집합은 전체집합이 됩니다. 이해를 돕기 위하여 특수한 상황을 가정해보겠습니다. a라는 나라와 b라는 나라가 동맹이고, b라는 나라와 c라는 나라가 동맹을 맺게된다면 a와 c나라도 자동으로 동맹이 되는 경우를 생각해봅시다. 해당 경우로 각각의 나라의 동.. 더보기
CCW와 CCW를 이용한 선분 교차 판별 PS에서 종종 이용되는 선분 교차 여부 판별을 CCW를 이용하여 비교적 간단(?)하게 할 수 있는 방법을 소개하려고 합니다. 그 전에 우선 CCW에 대하여 이야기 해보겠습니다. CCW는 Counterclockwise의 약자로 풀어 해석하면 그냥 반시계 방향입니다. PS에서의 CCW는 세 점에 대한 방향성을 나타냅니다. CCW의 return 값은 보통 세가지 경우입니다. 1. 반시계 방향인 경우 2. 시계 방향인 경우 3.세 점이 평행한 경우 이렇게 세가지 경우로 분류되며 CCW는 삼각형의 면적을 구하는 공식+벡터를 이용하여 구해지게 됩니다. 해당 식에서 S가 0보다 크면 반시계 방향 S가 0보다 작으면 시계 방향 S가 0이면 세 점이 평행합니다. 이를 소스코드로 작성하면 아래와 같습니다. 1234567i.. 더보기
좌표압축 기법 좌표압축 기법은 Problem Solving을 하다보면 정말 정말 정말 자주 쓰이는 테크닉이다. 세그트리(or BIT) 등등.. 구간 쿼리와 함께 같이 쓰이는 경우도 많고, 오프라인 쿼리등을 처리할 때 등등 많은 경우에서 유용하게 이용된다. 개념에 대한 설명을 하기 위하여 한 문제를 예시로 들어보겠다. N( 더보기
deque를 이용한 다이나믹프로그래밍 BOJ)5977 Mowing the Lawn 라는 문제를 풀 때 이용한 테크닉이다. 문제: icpc.me/5977 시퀀스가 주어질 때 주어진 시퀀스에서 수를 선택하여 최댓값을 만들어야 하는데 수를 연속으로 k이하로 선택가능할 때 답을 출력하는 문제이다. 예를 들어서 n이 5고 k가2라면 (1,2) (4,5) 이런식으로 연속된 수열은 최대 k까지 선택하여야 한다. 문제만 보면 당연히 다이나믹 프로그래밍을 떠올릴 수 있다. 하지만 점화식을 세우다보면 n이 너무 크기때문에 곤란할 수 있다. 하지만 일단 점화식을 세워보자 dp[i]는 i번째 인덱스까지 수열을 처리하였을 때 최댓값이라고 정의를 한다면 dp[i] =max(psum[i]- psum[j]+ dp[j-1]) j:(i-k+1 ~ i) 라는 수식이 세워진다.. 더보기
L-R flow http://blog.myungwoo.kr/111 와 http://koosaga.com/134 에서 많은 부분 참고하였습니다. -간선에 lower_bound가 존재할 때 플로우를 흘릴 수 있는지 여부 확인 1. MCMF로 모델링 a->b로의 간선이 하한이 l 상한이 r일 때 a->b로 (l , -1) , (r-l ,0)으로 두가지 간선을 만들어 준 뒤 MCMF 를 돌린다면 항상 -1이 있는 쪽으로 플로우가 강제된다. 이 때 cost를 확인하여 플로우를 흘릴 수 있는 지 여부를 확인해준다. 이 때의 maxflow는 flow를 확인하여 구할 수 있다. 2. 디닉을 사용하는 방법 새로운 소스와 새로운 싱크를 만든다. 기존 싱크-> 기존 소스로 capacity가 INF인 간선을 생성한다. a->b로의 간선이 하.. 더보기
트리에서 A와 B의 경로 사이에 C존재 여부 트리에서 임의의 노드 A,B가 있을 때 A와 B의 경로에 C가 존재하는지 여부는 어떻게 알 수 있을까? A와 B의 LCA를 LCA(A,B)라고 칭해보자. 만약 A와 B의 경로사이에 C가 존재한다면 C는 A와 LCA(A,B) 사이의 경로에 존재하거나 B와 LCA(A,B) 사이의 경로에 존재할 것이다. 일단 A와 LCA(A,B) 사이의 경로에 C가 존재한다고 가정해보자 그렇다면 LCA(A,C)==C && LCA(A,B)==LCA(C,B) 가 성립할 것 이다. 그러면 이번에는 B와 LCA(A,B)사이의 경로에 C가 존재한다고 가정해보자. 그렇다면 LCA(B,C)==C && LCA(A,B)==LCA(C,A) 가 성립할 것이다. 따라서 { LCA(A,C)==C && LCA(A,B)==LCA(C,B) }|| { L.. 더보기
다익스트라 알고리즘(Dijkstra's Algorithm) 다익스트라 알고리즘은 간선에 가중치가 있는 그래프에서 1:N 최단거리를 구하는 알고리즘 입니다. 여기서 말하는 1:N이란 한 정점 V를 기준으로 V와 같은 컴포넌트에 속해있는 모든 정점들과의 최단거리를 계산한다는 의미입니다. 보통 가중치가 없는 그래프에서의 1:N 최단거리는 BFS (O(V+E))를 통하여 계산해주고, 가중치가 있는 그래프에서의 N:N 최단거리는 플로이드 워셜(O(N^3))으로 계산해주는게 일반적입니다. 단 다익스트라를 포함한 위에서 제시한 알고리즘들은 가중치가 음수 일때는 사용하지 못합니다. 가중치가 음수일 경우 벨만포드 알고리즘(O(VE))이나 SPFA(O(VE))를 통하여 최단거리를 구해주어야 합니다. 그렇다면 다익스트라는 어떤 방식으로 1:N 최단거리를 구해낼까요? 일단 다익스트라.. 더보기
트리의 이심률,지름,반지름 트리에서 존재하는 한 정점 v에서의 이심률(eccentricity)이란 v가 속한 트리내의 모든 정점 u에 대해 max(dist(v,u))를 의미한다. 트리에서의 반지름은 트리내의 모든 정점 v에 대해서 이심률이 최소가 되는 v의 이심률이고 트리에서의 지름은 트리내의 모든 정점 v에 대해서 이심률이 최대가 되는 v의 이심률이다. 간단하게 정리하면 v의 이심률은 v에서 가장 먼 정점까지의 거리로 정의되며 트리의 지름은 트리 내부에서 가장 먼 두점 사이의 거리이며 트리의 반지름은 각 정점들에서의 가장 먼거리들 중 최소가 되는 거리이다. 트리의 지름을 구하는 방법은 익히 잘알려져있는 방법으로 임의의 정점에서 v에서 dfs를 통하여 이심률을 구하고 해당 이심률의 단말에 해당되는 정점 u에서 다시 dfs를 통하여.. 더보기
(pow(A,B))mod C 를 logB 시간안에 구하는 함수 http://jason9319.tistory.com/169 예전에 이항 계수를 구할 때 설명한 적이 있지만 빈번하게 사용되는 유용한 테크닉이라 생각되어 다시 설명드립니다. 우선 소스코드를 먼저 보시죠 12345678910111213141516#include #include using namespace std;typedef long long ll;ll a, b, c;ll mypow(ll x, ll y) { if (!y)return 1; if (y % 2) return (x*mypow(x, y - 1)) % c; return mypow((x * x) % c, y / 2) % c;}int main() { scanf("%lld%lld%lld", &a, &b, &c); printf("%lld", mypow(a, .. 더보기
Parallel binary search 크루스칼의 공이라는 문제가 있다. 이 문제는 http://jason9319.tistory.com/280처럼 LCA를 이용하여 온라인 쿼리로 해결할 수 있으나 LCA를 쓰지않고 오프라인 쿼리로 해결 가능한 방법도 있다. Parallel binary search는 이 문제를 오프라인 쿼리로 해결해 줄 방법이다. 어떤 문제가 요구하는 정답이 단조 증가의 모양을 가질 때 binary search를 이용한 parametric search로 답을 구해줄 수 있다. 크루스칼의 공같이 답이 될 수 있는 수가 연속적이라면 우리는 쿼리 전체에 대하여 binary search를 수행하여 답을 구해낼 수 있다. 하지만 쿼리 하나씩 이분 탐색을 거칠경우 너무 많은 시간이 소요되기 때문에 쿼리를 모아놓고 한번 값을 구할 때 해당.. 더보기

티스토리툴바