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

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..

위상정렬 (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..