모든 Mother Vertex를 O(V+E)에 구하는 알고리즘

발행일 : 2020-07-08 UPD1 : 2020-09-25 Find All Mother Vertices in a directed graph. Mother Vertex. 어떤 방향 그래프에서 한 정점이 다른 모든 정점에 도달할 수 있다면 이를 Mother Vertex라 부른다. 이 글에서는 방향 그래프에서 존재하는 모든 Mother Vertex를 구하는 방법에 대해 알아본다. Existence of a Mother Vertex Mother Vertex의 존재성을 판정하는 방법은 두가지가 있다. 첫번째 방법은 각 정점에서 방문이 가능한 정점을 저장하는 bitset을 생성한다. 모든 비트가 체크된 노드가 있다면 그것은 Mother Vertex이다. DFS를 통해 bitset을 갱신한다. 주의할 것은 한번의..

2020.09.25

특정 조건에서 LCS를 O((n+m) log (nm))에 구하는 알고리즘

*LCS Longest Common Subsequence. Subsequence는 부분수열들이 꼭 연속하지 않아도 된다. 예를 들어 두 수열 A,B가 있다 하자. A = 1 5 3 4 2 6 5 B = 1 6 3 2 3 5 A와 B의 부분 수열은 {1}, {3}, {1,2} 등 여러가지가 있다. A와 B의 LCS는 {1,3,4,5}이고 그 길이는 4이다. A의 길이를 n, B의 길이를 m이라 할 때 다이나믹 프로그래밍을 이용해 O(nm)의 시간에 LCS(A,B)를 구할 수 있다. 이는 잘 알려져 있는 알고리즘이므로 쉽게 설명된 글이 많다. 이 글에서는 특정 상황에서 빠르게 LCS를 구하는 방법에 집중한다. 또한 앞으로 LCS를 구하는 것을 LCS의 길이를 구하는 것과 동일하게 취급한다. *특정 조건에서 ..

2020.09.25

과반수 원소 알고리즘

Majority Element / Majority Vote Algorithm 주어진 리스트에서 과반수를 차지하는 원소의 존재성 판정과, 존재 시 과반수 원소를 구하는 알고리즘. A[] = { 1, 3, 1, 1, 2} 리스트 A에서 과반수 원소는 1이다. 정렬하면 슥삭 풀리는 문제이지만 O(N) 시간복잡도에 가능한 알고리즘이 존재한다. O(N) Solution 내가 소개할 것 : Pair 매칭 알고리즘. *기존 길이 $n$ 리스트 A로부터 길이 $[n/2]$ 리스트 B를 만든다. N이 짝수일 때 : 앞에서부터 차례대로 2개씩 묶는다. 각각의 pair (x,y)에 대해 x==y면 하나만 남기고, x!=y면 둘 다 제거한다. A[]={1,3,1,1,2,1} 을 예시로 들자면 (1,3) => (), (1,1)..

2020.08.20

Convex Hull과 Sorting의 관계

정렬 문제를 Convex Hull 문제로 환원하는 방법을 소개합니다. Convex Hull 문제를 정렬 문제로 환원할 수 있다는 것은 널리 알려져 있는 사실이다. Graham Scan알고리즘은 점들을 각도 순으로 정렬한 뒤 한 번의 스캔을 통해 Convex Hull을 구하는 알고리즘이기 때문이다. 곧, 다항 시간 내에 Convex Hull 문제를 점들을 정렬하는 문제로 환원할 수 있다. 여기서는 정렬 후에 이루어지는 스캔 (O(N))이 변환 시간이 된다. 다음과 같이 나타낸다. 여기까지는 Convex Hull과 다항식 시간 변환의 개념을 안다면 누구나 알 수 있는 사실이다. 한 발 더 나아가보자. 정렬 문제를 Convex Hull을 구하는 문제로 변환할 수 있을까? 즉, Convex Hull을 구하는 알..

2020.08.15

첫 Codeforces

Codeforces Div.3에 처음으로 참여했다. https://codeforces.com/contest/1367 Dashboard - Codeforces Round #650 (Div. 3) - Codeforces codeforces.com A,B,C는 문제를 빠르게 읽는 것에 경각심을 느끼게 해주었다. D,E는 문자열 다루기에 익숙해지라는 것을 가르쳐주었다. F1,F2는, 내가 아이디어에 강하지만 애매한 구현을 더 연습해야 좋은 결과를 낼 수 있다는 조언을 주었다. 새벽에 재밌었다.

2020.06.17

강 건너기 문제

※이 글은 사람이 10명 이하일 때의 알고리즘입니다. Large 문제의 해법은 0000 원하는 상태 ==> 1111 이 된다. 탐색 알고리즘 n이 7 이하이기 때문에 사람들이 분포될 수 있는 경우의 수는 2^7 * 2(배의 위치) = 256 으로 매우 작다. 그렇기 때문에 브루트 포스 (DFS)로 충분히 해결될 수 있을 것이라 보았지만 웬걸, 83퍼에서 시간 초과가 걸리고 말았다. 다시 생각해보니 256개의 정점이 있는 것이더라.. 일반적인 DFS로 풀 경우 지수함수에 비례하는 시간이 걸리므로 시간 초과가 날 수 밖에 없다. 그럼 지금 구해야 하는 것은 가중치 그래프에서의 최단 거리이다. 그렇다면 역시 다익스트라 알고리즘을 사용하자. 아래 풀이를 이해하기 위해서는 다익스트라 알고리즘에 대한 기본적인 이해..

2020.02.02