티스토리

ACM-ICPC 상 탈 사람

검색하기

블로그 홈

ACM-ICPC 상 탈 사람

jason9319.tistory.com/m

BOJ Handle : jason9319

구독자: 12

방명록 방문하기

주요 글 목록

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나라도 자동으로 동맹이 되는 경우를 생각해봅시다. 해당 경우로 각각의 나라의 동.. 공감수 2 댓글수 2 2018. 6. 24.
CCW와 CCW를 이용한 선분 교차 판별 PS에서 종종 이용되는 선분 교차 여부 판별을 CCW를 이용하여 비교적 간단(?)하게 할 수 있는 방법을 소개하려고 합니다. 그 전에 우선 CCW에 대하여 이야기 해보겠습니다. CCW는 Counterclockwise의 약자로 풀어 해석하면 그냥 반시계 방향입니다. PS에서의 CCW는 세 점에 대한 방향성을 나타냅니다. CCW의 return 값은 보통 세가지 경우입니다. 1. 반시계 방향인 경우 2. 시계 방향인 경우 3.세 점이 평행한 경우 이렇게 세가지 경우로 분류되며 CCW는 삼각형의 면적을 구하는 공식+벡터를 이용하여 구해지게 됩니다. 해당 식에서 S가 0보다 크면 반시계 방향 S가 0보다 작으면 시계 방향 S가 0이면 세 점이 평행합니다. 이를 소스코드로 작성하면 아래와 같습니다. 1234567i.. 공감수 17 댓글수 8 2017. 10. 9.
좌표압축 기법 좌표압축 기법은 Problem Solving을 하다보면 정말 정말 정말 자주 쓰이는 테크닉이다. 세그트리(or BIT) 등등.. 구간 쿼리와 함께 같이 쓰이는 경우도 많고, 오프라인 쿼리등을 처리할 때 등등 많은 경우에서 유용하게 이용된다. 개념에 대한 설명을 하기 위하여 한 문제를 예시로 들어보겠다. N( 공감수 8 댓글수 1 2017. 9. 19.
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) 라는 수식이 세워진다.. 공감수 4 댓글수 0 2017. 9. 5.
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로의 간선이 하.. 공감수 0 댓글수 0 2017. 8. 15.
트리에서 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.. 공감수 0 댓글수 0 2017. 7. 11.
다익스트라 알고리즘(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 최단거리를 구해낼까요? 일단 다익스트라.. 공감수 4 댓글수 7 2017. 7. 9.
트리의 이심률,지름,반지름 트리에서 존재하는 한 정점 v에서의 이심률(eccentricity)이란 v가 속한 트리내의 모든 정점 u에 대해 max(dist(v,u))를 의미한다. 트리에서의 반지름은 트리내의 모든 정점 v에 대해서 이심률이 최소가 되는 v의 이심률이고 트리에서의 지름은 트리내의 모든 정점 v에 대해서 이심률이 최대가 되는 v의 이심률이다. 간단하게 정리하면 v의 이심률은 v에서 가장 먼 정점까지의 거리로 정의되며 트리의 지름은 트리 내부에서 가장 먼 두점 사이의 거리이며 트리의 반지름은 각 정점들에서의 가장 먼거리들 중 최소가 되는 거리이다. 트리의 지름을 구하는 방법은 익히 잘알려져있는 방법으로 임의의 정점에서 v에서 dfs를 통하여 이심률을 구하고 해당 이심률의 단말에 해당되는 정점 u에서 다시 dfs를 통하여.. 공감수 2 댓글수 0 2017. 7. 8.
(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, .. 공감수 0 댓글수 0 2017. 6. 18.
Parallel binary search 크루스칼의 공이라는 문제가 있다. 이 문제는 http://jason9319.tistory.com/280처럼 LCA를 이용하여 온라인 쿼리로 해결할 수 있으나 LCA를 쓰지않고 오프라인 쿼리로 해결 가능한 방법도 있다. Parallel binary search는 이 문제를 오프라인 쿼리로 해결해 줄 방법이다. 어떤 문제가 요구하는 정답이 단조 증가의 모양을 가질 때 binary search를 이용한 parametric search로 답을 구해줄 수 있다. 크루스칼의 공같이 답이 될 수 있는 수가 연속적이라면 우리는 쿼리 전체에 대하여 binary search를 수행하여 답을 구해낼 수 있다. 하지만 쿼리 하나씩 이분 탐색을 거칠경우 너무 많은 시간이 소요되기 때문에 쿼리를 모아놓고 한번 값을 구할 때 해당.. 공감수 0 댓글수 0 2017. 6. 14.
Fenwick Tree(Binary Indexed Tree) http://jason9319.tistory.com/282 문제를 lazy progatition을 이용한 segment tree를 이용하다가 멘탈이 나가서 fenwick tree를 공부하였다. (https://www.acmicpc.net/board/view/15993) 펜윅트리는 BIT(Binary Indexed Tree)로도 불리며 갱신이 이루어지는 range의 구간 합 연산을 빠르게 해결해주는 자료구조로 알려져있다. 자료구조의 정당성과 시간복잡도등은 https://www.acmicpc.net/blog/view/21에 잘 설명이 되어있고 여기서는 간단하게 사용법만 알아보겠다. 123456789101112131415ll tree[MAX_N+1];void update(ll x, ll val) { while.. 공감수 0 댓글수 3 2017. 6. 14.
Persistent Segment Tree 먼저 시작하기 전에 .. -오늘 공부한 내용을 제 멍청한 머리가 기억하지 못할까봐 기록하는 개인용 글입니다. -해당 자료구조에 대하여 완벽하게 알고 적는 글이 아니기 때문에 Persistent segment tree를 공부하는 용도로는 좋지 못한 글이 될 확률이 높습니다.-BOJ 11932 문제를 풀기 위해 https://hongjun7.tistory.com/m/64와 http://blog.myungwoo.kr/100 를 많은 부분에서 참고하였습니다. persistent segment tree가 뭔지는 알고있었지만 귀찮아서 공부를 미루다가 오늘 BOJ 11932번을 접하고 도전하게 되었다. persistent segment tree는 가상의 N개의 세그먼트 트리를 O(NlogN)의 공간복잡도로 유지하는 .. 공감수 0 댓글수 14 2017. 6. 5.
제1종 스털링 수 원소의 개수가 N인 집합을 구분되지 않는 K개의 원순열로 분할하는 방법의 수이다. 이를 D[N][K]로 정의하면 D[N][K]=D[N-1][K-1]+(N-1)*D[N-1][K] 라는 점화식을 얻을 수 있다. 관련 문제: https://www.acmicpc.net/problem/1413 공감수 0 댓글수 0 2017. 5. 29.
Minimum Path cover in DAG DAG(Directed Acyclic Graph)에서 모든 정점을 커버하는 겹치지 않는 최소의 경로의 수를 구하는 문제 전체 정점의 수가 V 커버한 경로상의 간선이 X라면 V-X개의 경로로 커버할 수 있다. 따라서 X를 최대화 시켜야한다. 간선을 고를 때 제약 조건은 한 정점이 선택 될 때 오직 하나의 indegree와 오직 하나의 outdegree가 선택되어야 한다는 점이다. 즉, indegree와 outdegree가 최대한으로 매칭되어야 한다. 이를 이용하여 indegree를 상징하는 정점과 outdegree의 정점을 상징하는 정점으로 그래프를 구성하여 해당 그래프의 이분 매칭을 구함으로서 Minimum Path cover in DAG를 구할 수 있다. 참조: http://koosaga.com/ent.. 공감수 0 댓글수 0 2017. 5. 29.
이항계수를 구하는 알고리즘 이항계수 는 으로 정의되며 흔히 조합으로 알려져 있습니다. n개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수를 이항계수라고 합니다. 우리는 이항계수가 가지는 이라는 성질을 이용하여 메모제이션 해주어 O(N^2)의 시간과 메모리 복잡도를 가지는 전처리 한번으로 매 쿼리를 O(1)에 처리해줄 수 있습니다. 하지만 BOJ)11401 이항 계수 3 처럼 N이 큰 쿼리가 들어올 경우 O(N^2)의 방법으로는 해결할 수 없습니다. 그래서 개선된 방법을 필요로 합니다. 이는 맨 위에 정의 된 를 이용하는 방법입니다. 문제 조건에서 모듈러를 위한 소수가 주어질텐데 을 소수에 대한 의 역원을 구해주는 문제로 수정하여 해결하는 문제입니다. 우리는 동적 프로그래밍을 이용하여 n!을 계산하는데 O(N).. 공감수 1 댓글수 9 2017. 2. 21.
디닉 알고리즘(Dinic's Algorithm) 디닉 알고리즘은 Maximum flow를 구하는 알고리즘 중에서 이분 그래프같은 특수한 환경에서 사용되는 알고리즘을 제외하고는 현재 PS분야에서 가장 빠르게 동작하는 알고리즘 입니다. 대부분의 유량 문제가 에드몬드 카프를 이용하여 해결 가능하지만 최근 몇몇 문제들은 디닉을 사용하지 않으면 시간초과를 보게 되는 경우도 많기 때문에 마음 편하게 디닉을 쓰시는걸 추천드립니다. 디닉 알고리즘의 시간 복잡도는 O(V^2*E)입니다. 그러면 디닉 알고리즘은 어떤 원리로 동작할까요? 우선 BFS를 이용하여 잔여용량이 0 이상인 간선에 대하여 레벨 그래프(level graph)라는 것을 만들어줍니다 잔여용량(residual capacity)이란 플로우에서 해당 간선의 기존 용량(c)에서 소스에서 흘려보낸 용량(f)를 .. 공감수 1 댓글수 7 2017. 2. 13.
이분 매칭(Bipartite Matching) 네트워크 플로우의 개념중에서 이분 그래프(bipartite grape)에서의 최대 유량을 구하는 경우를 이분 매칭이라고 부릅니다. 이분 그래프는 다음과 같은 모양을 띄고 있습니다. 위의 그림에서 파란색 정점과 노란색 정점들 끼리는 어떠한 간선도 존재하지 않습니다. 이렇게 정점을 두 그룹으로 나누었을 때 모든 간선에 연결 된 두 정점이 서로 다른 그룹에 존재하는 그래프를 이분 그래프라고 합니다. 간선의 용량이 전부 1인 이분 그래프에서의 최대 유량을 구하는 문제는 이분 그래프에서의 최대 매칭과 동치입니다. 이분 그래프에서 매칭이라는 말은 서로 다른 그룹에 놓인 두 정점을 짝지어주는 의미이고 우리는 이분 그래프에서 최대 매칭을 최대 유량 알고리즘인 디닉이나 에드몬드 카프 알고리즘을 이용하여 구해줄 수 있겠지.. 공감수 2 댓글수 7 2017. 2. 12.
Suffix Array & LCP Array(Longest Common Prefix Array) Suffix Array는 번역하면 접미사 배열으로 다양한 문자열 문제들을 해결할 수 있는 매우 강력한 자료구조 입니다. Suffix Array는 문자열의 Suffix를 사전순으로 정렬한 배열입니다. 예를 들어 banana라는 문자가 있다면 Suffix Array는 다음과 같이 됩니다. 하지만 Suffix Array를 이렇게 문자열로 가지고 있을 경우 O(N^2)의 공간 복잡도를 가지게 될 것입니다. 그렇기 때문에 Suffix Array는 몇번째 접미사인지 나타내는 정수 i만 가지는 정수형 자료 구조형태를 가집니다. 다음과 같이 말이죠. 자 이제 Suffix Array의 정의에 대해 알았으니 구현을 해 볼 차례입니다. 단순하게 접미사 배열을 구한다면 접미사를 구한다음 정렬을 하는 방법이 있겠군요 하지만 이.. 공감수 2 댓글수 4 2017. 2. 8.
KMP(Knuth–Morris–Pratt) 알고리즘 KMP 알고리즘은 문자열 A와 문자열 B가 있을 때, 문자열 A에서 문자열 B를 찾아주는 알고리즘 입니다. KMP는 KMP를 만든 사람의 이름인 Knuth, Morris, Prett 세 사람의 앞 글자를 따서 KMP 알고리즘이라고 불립니다. 자 그러면 우리는 문자열 A에서 문자열 B를 찾는 방법을 생각해봅시다. 가장 먼저 생각해 볼 수 있는 방법은 Brute force가 있겠군요. 하지만 모든 경우를 다 탐색할 경우 문자열 A의 길이가 N,문자열 B의 길이가 M이라면 O(N*M)의 시간 복잡도를 가지게 됩니다. 만약 N,M이 10만인 문제가 주어진다면 시간 초과를 보게 될 것입니다. 자 그러면 KMP를 사용하였을 때의 시간복잡도는 어떻게 될까요? 놀랍게도 O(N+M)의 시간복잡도만에 문자열 A에서 문자열.. 공감수 8 댓글수 1 2017. 2. 4.
[자료구조]트라이(Trie) 트라이(Trie)는 문자열에서의 검색을 빠르게 해주는 자료구조입니다. 우리는 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간만에 원하는 데이터를 검색할 수 있습니다. 하지만 문자열에서 이진검색트리를 사용한다면 문자열의 최대 길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것입니다. 우리는 문자열에서의 검색을 개선하기 위하여 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있습니다. 트라이라는 명칭은 Retrieval에서 유래했다고 합니다. 트라이가 retrieve(탐색)하는데 유용한 걸 생각하면 납득이됩니다. 자 그러면 트라이는 어떻게 문자열의 검색을 O(M)만에 처리해 줄 수 있을까요? 아래 그림은 문자열 집합 = {"AE" , "ATV", "ATES", .. 공감수 18 댓글수 4 2017. 2. 4.
단절점(Articulation Point)와 단절선(Bridge) 하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상의 컴포넌트로 나누어지는 정점을 단절점이라고 합니다.다음과 같은 무방향 그래프가 있다고 해봅시다. 여기서 빨간색 테두리로 이루어진 정점들중 하나를 지울 경우 컴포넌트가 2개로 나누어지게 됩니다. 이러한 성질을 가지는 정점들을 단절점이라고 부릅니다. 그러면 우리는 단절점을 어떤 방법으로 찾을 수 있을까요? 우선은 단절점을 찾기 위해서 우선 단절점이 가지는 특징을 알아야 됩니다. 아까의 그래프에서 단절점인 빨간정점에 연결된 정점들을 초록정점으로 색칠해봤습니다. 우리는 어떤 정점 A에 연결된 모든 정점들 중 두 정점들 간에 정점 A를 거치지않고 갈 수 있는 우회경로가 존재하지 않는 경우가 존재한다면 정점 A는 단절점으로 판단.. 공감수 9 댓글수 1 2017. 1. 31.
[최장 증가 수열] LIS(Longest Increasing Subsequence) 이번 글에서는 DP중에서 특별한 케이스인 LIS에 대해 얘기해보자 합니다. LIS(Longest increasing Subsequence)는 가장 긴 증가하는 부분 수열 정도로 해석 가능합니다. 쉬운 이해를 위해서 예를 들어보겠습니다. 다음과 같은 수열이 존재한다고 해봅시다. 여기서 LIS를 찾는다면 다음과 같이 빨간 부분으로 색칠된 부분이 LIS가 됩니다. 눈치 빠르신 분들은 벌써 알아채셨을겁니다. LIS는 앞에서부터 뒤로 숫자를 선택하며 부분 수열을 구성해 나갈 때 증가하는 순서대로 숫자를 고르면서 고른 부분 수열의 길이가 최대 길이가 되도록 숫자를 선택하는 경우입니다. 보통 LIS를 구하는 문제의 답은 한 수열에서 주어지는 LIS의 길이가 답이됩니다. 즉, 그 수열에서 존재하는 모든 부분 증가 수열.. 공감수 43 댓글수 33 2017. 1. 25.
SCC(Strongly Connected Component) 방향 그래프에서 어떤 그룹 X에 있는 임의의 두 정점 A,B에 대해서 항상 A->B로 가는 경로가 존재한다면 그 그룹을 SCC(Strongly Connected Component)라 칭합니다. 더 정확하게 정의하자면 SCC가 되는 그룹은 항상 최대로 정의되기 때문에 다음과 같은 조건을 만족해야 합니다. 1. 같은 SCC 내의 임의의 두 정점 A,B사이의 경로가 항상 존재한다.2. 서로 다른 SCC에서 뽑은 임의의 두 점 A,B 사이의 경로 A->B로 가는 경로와 B->A로 가는 경로는 동시에 존재할 수 없다. (SCC 끼리는 사이클이 존재하지 않는다.) SCC를 직역하면 "강한 연결 요소" 라는 뜻이됩니다. 즉 SCC는 집합 내에서 정점들이 서로 왕복 가능한 최대 크기의 집합입니다. 다음과 같은 그래프에.. 공감수 9 댓글수 12 2017. 1. 21.
Topological Sort(위상 정렬) DAG에서 방향성을 거스르지 않게 정점들을 나열하는 알고리즘을 Topological sort(위상 정렬)이라 합니다. DAG란 Directed Acyclic Graph의 줄임말로 직역하자면 사이클이없는 방향(유향) 그래프 정도가 될 것입니다. DAG는 유향 그래프에서 정의되며 DAG가 되려면 Cycle이 없어야 합니다. 우리는 유향 그래프에서 한 정점에서 DFS를 실행 할 경우 DFS의 방문순서에 따라서 스패닝 트리를 얻을 수 있습니다. 우리는 이러한 트리를 DFS 스패닝 트리(DFS Spanning Tree)라고 부르며 DFS 스패닝 트리에서 간선의 특징에 따라 간선 분류를 할 수 있습니다. 1. 트리 간선-> 스패닝 트리에 포함된 간선 2. 순방향 간선-> 스패닝 트리에는 포함되지 않았지만 선조에서 .. 공감수 22 댓글수 30 2017. 1. 20.
LCA(Lowest Common Ancestor) 1개 이상의 노드로 구성 된 사이클이 없는 그래프를 트리라고 합니다. 우리는 트리에서 정의되는 LCA(Lowest Common Ancestor)에 대해서 얘기해 보려 합니다. LCA를 직역하면 최소 공통 조상(?) 정도의 뜻으로 해석되며 두 정점에서 (자신을 포함한)조상들을 거슬러 올라갈 때 처음으로 공통되게 만나는 정점을 지칭합니다. 예를 들기 위해 다음과 같은 트리가 존재한다고 합시다. 이 트리에서 6번 정점과 10번 정점의 LCA를 구하면 다음과 같이 2번 정점이 6번 정점과 10번 정점의 LCA가 됩니다. 이번에는 7번 정점과 10번 정점의 LCA를 구해보겠습니다. 다음과 같이 1번 정점이 7번 정점과 10번 정점의 LCA가 됩니다. 자, 이제 어느정도 LCA의 정의에 대한 감이 오시나요? 마지막.. 공감수 9 댓글수 4 2017. 1. 19.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.