병아리 개발자의 실력 양성기

최소신장트리(MST) 각 간선(edge)의 weight가 1이나 0이 아닌 경우에 모든 노드를 한 트리로 묶은 것(spanning tree)의 weight의 합이 최소가 되는 것을 MST (minimum spanning tree) 라 한다. 이를 구하는 방법은 union find를 쓰는 Kruskal과, Dijkstra의 변형인 Prim이 있는데, 통상 CP에서는 전자를 많이 쓴다고 한다. UnionFind Kruskal을 쓰려면 union find 자료구조를 정의해서 사용해야 한다. 다음 코드는 path compression과 union-by-rank가 모두 적용된 클래스이다. class UnionFind: def __init__(self, N: int) -> None: # N: number of ve..

SCC - Kosaraju Strongly Connected Components (Directed Graph) 는 노드간에 모두 연결된 경우를 말한다. CC와 다른 점은, 방향 그래프에서 dfs를 수행해서 일방향으로 닿을 수 있는 경우로는 요건이 충족되지 못하며, 서로간에 모두 닿을 수 있는 그래프의 부분집합이어야 한다. 그림을 보자 [1]. Kosaraju는 dfs를 두 번 돌려서 SCC를 찾는 알고리즘이다. 아래 그림에서 먼저 dfs 이용해서 Topological Sort를 수행한 결과 S = {0, 1, 3, 4, 5, 7, 6, 2} 가 된다. 이 결과의 의미는, 각 vertex를 방문시 종결 순서의 역순으로 이를 나열한 것이다. 두 번째 dfs에서는 그 결과 S의 원소를 앞에서부터 차례로 짚어가..

한 점(node 1)에서 시작하여 연결된 노드를 방문할 때 방문이 되지 않는 점을 찾는 것을 하고자 한다. 문제는 다음에서 가져왔다. https://open.kattis.com/problems/wheresmyinternet Where's My Internet?? – Kattis, Kattis Photo by Jerry John from Flickr A new town is being built far out in the country, and currently there are $N$ houses. People have already started moving in. However, some of the houses aren’t connected to the internet yet, and natural..

그래프 이론은 방대하다. 기본적으로 방문, 최단거리, DAG, 사이클, MST가 있고, 고급 알고리즘으로는 SCC, 경로, flow 등이 있다. 트리도 그래프의 일종이나 그 특성상 더 적합한 알고리즘이 있기도 하므로 별도로 다루게 된다. 이번 시간에 다룰 문제는 다음과 같다. Connected Components Topological Sort Bipartite or Cycle Check Shortest Path (BFS) Graph traversal 문제 중에서 더 어려운 Strongly Connected Components, Articulation Points/Bridges, Flood Fill은 몇 차례에 나누어 다루기로 하겠으며, MST, SSSP, APSP, Special Graph (최단/장 거..

Linked List (singly) 도, Tree도 모두 DAG인 그래프의 일종이라 할 수 있다. 그래프의 사이클을 찾는 방법은 크게 방문된 노드를 기록해 두었다가 (O(n) space), 방문하려는 노드가 이미 방문한 적이 있다면 cycle 이 있다고 보고하는 방법과, Floyd가 제시한 two pointer를 사용하는 방법이 있다 (O(1) space). 이전에 전자에 대해 다루었으므로 오늘은 후자를 다뤄본다. 아무래도 공간을 사용한 전자가 더 속도가 빠르기는 하다. 사이클 여부 토끼는 2걸음씩, 거북이는 1걸음씩 걷는다. 사이클이 존재한다면 둘이 만날 것이고 그렇지 않다면 토끼가 먼저 종점에 도달할 것이다. # Definition for singly-linked list. # class ListN..

위상정렬 (topological sorting)은 DAG에서 DFS 탐색 순서대로 노드의 값을 나열하는 것을 말한다. DFS는 어느 source 노드를 먼저 탐색할지를 임의로 정할 수 있기 때문에 다양한 위상정렬이 있을 수 있지만 '탐색 순서대로' 라는 규칙은 맞아야 한다. 일반적인 해법은 각 노드에 대해 탐색 상태를 저장하는 배열을 하나 만들고, DFS를 하면서, 배열에 다음과 같이 값을 기록한다. state 0 (white) : 노드가 아직 처리되지 않음 state 1 (light gray) : 노드가 처리되는 중임(visiting) state 2 (dark gray) : 노드가 처리 완료 됨(visited) 처리 완료라는 말은 모든 후속 노드가 처리가 되었다는 뜻이다. 그럼 모든 후속 노드가 처리되..

벽으로 둘러싸인 공간, 즉 방의 갯수를 구하는 Counting Rooms 라는 문제가 있다. https://cses.fi/problemset/task/1192/ CSES - Counting Rooms cses.fi 이는 DFS의 응용 형태로 푸는 것이다. DFS는 한 점에서 출발해 닿을 수 있는 미 방문점을 모두 방문하는 것이다. 방문할 때 마다 방문된 점을 표시하되 끝까지 방문이 되면 돌아온다. 이와 유사한 과정인 backtracking은 방문시마다 어떤 조건에 대해 확인하는 절차를 거쳐, 그 조건이 만족되지 않으면 방문을 종료하는 것이다. DFS에서 기본적으로 검증하는 조건은 바로 '방문여부'가 된다. 이미 방문된 것은 다시 방문하지 않는다. 이를 위해 방문된 노드에 대한 기호를 모아놓는 일을 set..

BST BST는 node.left.data > t = bintrees.RBTree([(3, 'Ryan'), (2, 'Muzi'), (5, 'Jay-Z'), (1, 'Chunshik')]) >>> t[2] 'Muzi' >>> t.min_item() (1, 'Chunshik') >>> t.max_item() (5, 'Jay-Z') >>> t.insert(8, 'Pengsoo') >>> t RBTree({1: 'Chunshik', 2: 'Muzi', 3: 'Ryan', 5: 'Jay-Z', 8: 'Pengsoo'}) >>> t.discard(5) >>> a = t.pop_min() >>> a (1, 'Chunshik') >>> b = t.pop_max() >>> b (8, 'Pengsoo') >>> t RBT..

공부를 하면 할 수록, 기본 개념은 간단하며 소위 '기초'로 분류되는 주제이나 실제로 문제를 풀기에는 여간 까다롭지 않은 것이 연결 리스트라는 생각이 든다. 주변 엔지니어에게 경험을 물어봐도 이 주제를 어렵다고 평가하는 것을 들을 수 있었다. 대표적 문제를 풀면서 심층적으로 탐구해 보고자 한다. 정의 연결 리스트는 아래와 같이 정의된 노드들의 연결로 이루어진다 (Goodrich et al. [1]) class _Node: def __init__(self, element=0, next=None, prev=None): # initialize node's fields self._element = element # user's element self._prev = prev # previous node refer..