본문 바로가기

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

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.. 더보기
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)의 공간복잡도로 유지하는 .. 더보기
제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 더보기
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.. 더보기
이항계수를 구하는 알고리즘 이항계수 는 으로 정의되며 흔히 조합으로 알려져 있습니다. n개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수를 이항계수라고 합니다. 우리는 이항계수가 가지는 이라는 성질을 이용하여 메모제이션 해주어 O(N^2)의 시간과 메모리 복잡도를 가지는 전처리 한번으로 매 쿼리를 O(1)에 처리해줄 수 있습니다. 하지만 BOJ)11401 이항 계수 3 처럼 N이 큰 쿼리가 들어올 경우 O(N^2)의 방법으로는 해결할 수 없습니다. 그래서 개선된 방법을 필요로 합니다. 이는 맨 위에 정의 된 를 이용하는 방법입니다. 문제 조건에서 모듈러를 위한 소수가 주어질텐데 을 소수에 대한 의 역원을 구해주는 문제로 수정하여 해결하는 문제입니다. 우리는 동적 프로그래밍을 이용하여 n!을 계산하는데 O(N).. 더보기
디닉 알고리즘(Dinic's Algorithm) 디닉 알고리즘은 Maximum flow를 구하는 알고리즘 중에서 이분 그래프같은 특수한 환경에서 사용되는 알고리즘을 제외하고는 현재 PS분야에서 가장 빠르게 동작하는 알고리즘 입니다. 대부분의 유량 문제가 에드몬드 카프를 이용하여 해결 가능하지만 최근 몇몇 문제들은 디닉을 사용하지 않으면 시간초과를 보게 되는 경우도 많기 때문에 마음 편하게 디닉을 쓰시는걸 추천드립니다. 디닉 알고리즘의 시간 복잡도는 O(V^2*E)입니다. 그러면 디닉 알고리즘은 어떤 원리로 동작할까요? 우선 BFS를 이용하여 잔여용량이 0 이상인 간선에 대하여 레벨 그래프(level graph)라는 것을 만들어줍니다 잔여용량(residual capacity)이란 플로우에서 해당 간선의 기존 용량(c)에서 소스에서 흘려보낸 용량(f)를 .. 더보기
이분 매칭(Bipartite Matching) 네트워크 플로우의 개념중에서 이분 그래프(bipartite grape)에서의 최대 유량을 구하는 경우를 이분 매칭이라고 부릅니다. 이분 그래프는 다음과 같은 모양을 띄고 있습니다. 위의 그림에서 파란색 정점과 노란색 정점들 끼리는 어떠한 간선도 존재하지 않습니다. 이렇게 정점을 두 그룹으로 나누었을 때 모든 간선에 연결 된 두 정점이 서로 다른 그룹에 존재하는 그래프를 이분 그래프라고 합니다. 간선의 용량이 전부 1인 이분 그래프에서의 최대 유량을 구하는 문제는 이분 그래프에서의 최대 매칭과 동치입니다. 이분 그래프에서 매칭이라는 말은 서로 다른 그룹에 놓인 두 정점을 짝지어주는 의미이고 우리는 이분 그래프에서 최대 매칭을 최대 유량 알고리즘인 디닉이나 에드몬드 카프 알고리즘을 이용하여 구해줄 수 있겠지.. 더보기
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의 정의에 대해 알았으니 구현을 해 볼 차례입니다. 단순하게 접미사 배열을 구한다면 접미사를 구한다음 정렬을 하는 방법이 있겠군요 하지만 이.. 더보기
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에서 문자열.. 더보기
[자료구조]트라이(Trie) 트라이(Trie)는 문자열에서의 검색을 빠르게 해주는 자료구조입니다. 우리는 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간만에 원하는 데이터를 검색할 수 있습니다. 하지만 문자열에서 이진검색트리를 사용한다면 문자열의 최대 길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것입니다. 우리는 문자열에서의 검색을 개선하기 위하여 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있습니다. 트라이라는 명칭은 Retrieval에서 유래했다고 합니다. 트라이가 retrieve(탐색)하는데 유용한 걸 생각하면 납득이됩니다. 자 그러면 트라이는 어떻게 문자열의 검색을 O(M)만에 처리해 줄 수 있을까요? 아래 그림은 문자열 집합 = {"AE" , "ATV", "ATES", .. 더보기