mojo's Blog

문제 링크 => 11779번: 최소비용 구하기 2 (acmicpc.net) 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 전형적인 다익스트라 문제이다. 다익스트라 알고리즘을 활용하여 최소거리를 구할 수 있어야 하며 동시에 경로까지 출력해야 하는 문제이다. 경로를 추적하기 위한 배열 trace 를 이용하였다. 시작 지점으로부터 다음 지점(next)까지의 최소 거리를 Distance[next] 라고 할 때 해당 값이 update 될 때마다 현재 위치(cur)에 대해서 trace[n..

Directed Acyclic Graph (DAG) 자료 흐름 분석이 완료된 후 기본 블록에 대한 코드를 생성할 때, 각 블록에 대해 DAG(directed acyclic graph) 생성하여 활용한다. ● DAG는 값이 어떻게 계산되는지를 그림으로 나타내준다. ● DAG는 주로 블록 내부에서 사용되지만, 블록 외부에서 어떤 문장이 그 문장에서 계산한 값을 사용하는지 알아볼 수 있으므로 매우 중요하다. DAG는 모든 산술식에 대한 노드를 가진다. ● 내부 노드(interior node)는 연산자를 나타내고 그 자식 노드는 피연산자를 나타낸다. ● 터미널 노드는 id나 constant이고 중간 노드는 연산자이다. ● 노드 옆에 여러 개의 id를 놓을 수 있으며, 이는 노드의 계산 결과를 이 id들이 공유함..

What on-disk structures to represent files and directories?  - Contiguous, Extents, Linked, FAT, Indexed, Multi-level indexed  - Which are good for different metrics?  What disk operations are needed for:  - make directory, open file, write/read file, close file on-disk structures : disk 상에 있는 구조체로 file, directory를 나타내기 위한 용도다. contiguous, extents, linked, fat, indexed, multi-level indexed 등..

We have shown previously that independent set, vertex cover, and clique are all equivalent. We now show they are all NP-complete by showing independent set is. independent set이 NP-complete 임을 보임으로써 나머지 vertex cover, clique 또한 동일하게 NP-complete 임을 확인해보도록 하자. Up to now, all reductions transformed one form of constraint into another. However, independent set is not a constraint satisfaction problem ..

문제 링크 => 23743번: 방탈출 (acmicpc.net) 23743번: 방탈출 첫 번째 줄에는 방의 개수 $N$과 설치할 수 있는 워프의 개수 $M$이 주어진다. ($2 \le N \le 200\,000$, $1 \le M \le 100\,000$) 다음 $M$개의 줄에는 워프의 정보를 나타내는 세 정수 $a_i$, $b_i$, $c_i$가 공백으 www.acmicpc.net 방탈출 카페에는 1번부터 N번까지 총 N개의 방이 있고, 각 방에는 친구들이 한 명씩 들어가 있다. 모든 방은 외부로부터 완전히 독립되어 있다. 방에서 탈출하지 못하는 친구들이 답답했던 원빈이는 모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하려고 한다. 워프는 최대 M개까지 설치할 수 있는데, i번째 워프는 ..

Data Structures for Disjoint Sets • Partition – A partition of a set X is a set of non-empty subsets of X such that every element x in X is in exactly one of these subsets. – Example: X = {1, 2, 3, 4, 5, 6} → { {1, 3, 5}, {2}, {4, 6} } • Disjoint-set data structure (union-find data structure) – Used to effectively manage a collection of subsets that partition a given set of elements. • Basic ope..