david의 CS Blog

Spanning Tree  Spanning Tree는 그래프의 모든 정점이 연결되어 있는 트리로, $V$개의 정점이 $V-1$개의 간선으로 연결되어 있다. 트리의 성질에 의해 모든 정점이 연결되어 있으므로 사이클이 존재하지 않는다. 스패닝 트리를 활용한 개념으로 최소 스패닝 트리(Minimum Spanning Tree)가 존재한다. 이는 간선에 가중치가 존재하는 그래프에서 가중치의 합을 최소로 하면서 스패닝 트리를 구성하기 위해 선택해야 하는 간선들을 정하는 것으로, 간선들의 가중치를 정렬하여 가중치가 작은 간선부터 우선적으로 선택하는 Greedy한 알고리즘을 채택할 수 있다.  DFS를 이용해 일반적인 그래프를 트리의 형태로 표현하는 경우가 존재한다. 특정 시작 정점에서 시작하여 중복 방문을 허용하지 ..

트리란? 노드로 이루어진 계층적인 자료구조로 사이클이 없는 그래프의 일종 트리에는 하나의 루트 노드가 있으며, 루트 노드는 자식 노드를 가지게 되고 그 자식 노드들은 그들의 자식 노드를 가지는 구조의 자료구조이다. 트리에 관한 용어들 루트 노드(root node): 부모 노드가 없는 중심이 되는 노드로 트리에 단 한 개만 존재한다. ex) 위 트리에서 루트 노드는 1번 노드이다. 서브 트리(subtree): 루트 노드를 제외한 나머지 노드 ex) 2, 3, ..., 9, 10번 노드들이 서브 트리이다. 리프 노드(leaf node): 자식 노드를 가지고 있지 않은 트리의 말단에 있는 노드 ex) 위 트리에서 리프 노드는 7, 8, 9, 10번 노드이다. 부모 노드(parent node): 어떤 노드와 간..

1. 계산 로봇 https://www.acmicpc.net/problem/22342 22342번: 계산 로봇 M개의 행(가로줄)과 N개의 열(세로줄)이 있는 격자의 각 칸에는 로봇이 있다. 각 행에는 위에서부터 아래로 1부터 M까지의 번호가 붙어 있고, 각 열에는 왼쪽에서부터 오른쪽으로 1 부터 N까지의 www.acmicpc.net 각 칸에 있는 로봇이 입력값, 저장값, 출력값을 가지므로 이해를 위해 입력값, 저장값, 출력값을 저장하는 2차원 배열 3개를 만들어보자. 각 로봇들의 입력값은 로봇의 위치(x, y)를 기준으로 왼쪽에 있고, |i-a|≤j-b를 만족하는 (a, b)에 있는 로봇들의 출력값이다. 로봇의 저장값은 입력값들의 최댓값이고, 저장값에 자신들의 가중치를 더한 값이 출력값이다. 이제 배열들..

비트마스크(BitMask)란? 정수의 이진수 표현을 이용하여 집합의 요소들의 구성을 나타내는 테크닉이다. 비트는 0 또는 1의 값을 가질 수 있고, 1은 참(True), 거짓(False)을 나타낸다. 예를 들어 십진수 12를 이진수로 나타내보면 다음과 같이 나타나는데 12 = $2^{3}$ + $2^{2}$ 로 표현되기 때문에 1100이라고 나타낼 수 있다. 이 때 각 비트가 가지는 상태를 통해 집합으로 이용할 수 있다. 비트는 1(True)와 0(False)만을 나타내기 때문에 구성 요소의 존재 여부를 나타낼 수 있는 것이다. 아래의 예시를 보면 집합을 정수형 변수 하나로 나타낸 것이다. 값 $i$가 집합에 포함되어 있으면 $i$번 비트가 1이고, 없으면 0인 것이다. {0, 1, 2, 3, 4, 5}..

https://www.acmicpc.net/problem/18251 18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 www.acmicpc.net 노드의 개수와 각각의 노드의 가중치를 입력받고 포화이진트리 모양을 만들었을 때 직사각형 영역을 그려서 영역 내에 있는 가중치들의 합을 최대로 만드는 문제이다. 만약 노드들의 좌표가 주어져 있다면 문제처럼 해결할 수 있을 것이다. 따라서 우리는 노드들의 좌표를 정해줄 것이다. 노드들의 $x$좌표는 트리를 전위 순회하는 순서로 ..

최단 경로 알고리즘 가중치 그래프에서 정점 간의 최단 경로를 구해야 하는 문제들은 많이 있다. 최단 경로란, 정점 $u$에서 $v$까지 가는데 거치는 간선의 가중치들의 총합을 말한다. 일상생활에서 최단 경로 알고리즘이 사용되는 예시로는 내비게이션(길찾기) 알고리즘이 있다. 최단 경로를 구하는 문제는 어떤 정점 $v$에서 다른 정점 $u$까지 가는 최단 경로를 구하거나, 어떤 정점 $u$에서 다른 모든 정점들까지 가는 최단 경로를 구하는 등 다양하게 사용된다. 다익스트라나 플로이드 알고리즘을 이용해 최단 경로를 구할 때에는 간선의 가중치가 모두 양수여야한다. 그 이유는 음수 간선에 의해 최단 경로가 계속 갱신되어 무한 루프에 빠질 수 있기 때문이다. 이에 대해서는 벨만포드 알고리즘의 글에서 자세하게 다룰 ..

Convex Hull  Convex Hull은 2차원 좌표 평면 위에 존재하는 여러 점들 중 일부를 이용하여 모든 점을 포함하는 볼록 다각형이다. 아래와 같이 점들이 2차원 좌표 평면에 존재할 때, 볼록 껍질을 나타내어보면 다음과 같다.  컨벡스 헐 알고리즘은 2차원 좌표 평면에서 점들의 좌표가 주어졌을 때 볼록 껍질을 구성하는 점들을 $O(N)$에 구하는 알고리즘으로, 다양한 알고리즘이 존재하는데 이 중 Graham Scan이라는 알고리즘을 통해 볼록 껍질을 구할 것이다.    Graham Scan의 동작 과정은 다음과 같다.  주어진 점들을 반시계방향으로 정렬하고, 정렬된 순서대로 점들을 탐색한다.stack에 첫 번째 점과 두 번째 점을 push한다. 그 다음 세 번째 점부터 N번째 점까지 아래의 과..

단절선이란? 하나의 컴포넌트로 구성되어 있는 그래프에서 특정 간선을 제거하면 컴포넌트 수가 증가하는 그 간선을 단절선이라 한다. 즉, 제거했을 때 그래프가 둘 이상으로 나누어지는 간선을 단절선이라고 한다. 위 그래프에선 정점 $1$, $2$, $3$, $4$번 정점은 사이클을 이루므로 이들 중 어느 두 정점 간의 간선도 단절선이 아닐 것이다. 하지만 정점 $5$, $6$을 잇는 간선을 제거하면 정점 $6$이 그래프와 분리되어 다른 컴포넌트가 되기 때문에 단절선이라고 볼 수 있다. 구현 그래프를 dfs로 탐색해서 트리 형태로 만들어준다. 위의 그래프를 트리 형태로 만들면 다음과 같다. 현재 노드 $A$, 자식 노드 $B$를 잇는 간선 ($A$, $B$)에서 A의 자식 노드들 중 A를 거치지 않고 A보다 이..

Sqrt Decomposition  구간 쿼리를 Segment Tree를 이용해서 처리하면 시간복잡도가 $O(logN)$이다. 이는 트리의 깊이에 비례하는데, 각 노드의 자식 노드의 수를 밑으로 가지는 로그의 시간복잡도를 가지는 것이다. 예를 들어 세그먼트 트리는 자식 노드가 2개이므로 엄밀한 시간복잡도 식은 $f(x) = log_{2}(x)$이다. 그렇다면 다음과 같이 생각할 수 있다.   "만약 세그먼트 트리의 자식 노드의 개수가 3개라면 시간복잡도는 어떻게 될까?    그러면 트리의 높이가 log_3(N)이므로 시간복잡도 식도 이와 같을 것이다. 그러면 공간복잡도를 배제하고 생각해보자. 시간복잡도를 최적화하려면 트리에서 자식 노드의 개수가 많을수록 유리할 것이다.하지만 우리는 마냥 공간복잡도를 배제..

Euler Tour Technique  Segment Tree를 이용한 쿼리 처리는 일반적으로 Array에서 이루어졌다. Array에서 구간 쿼리를 효율적으로 처리할 수 있었던 이유는, 처리하고자 하는 구간의 원소들이 인접하게, 연속하게 존재했기 때문이다. 이러한 연속성을 이용하여 특정 구간에 대한 쿼리를 Segment Tree로 $O(logN)$에 처리할 수 있었던 것이다. 그렇다면 Graph에서의 쿼리 처리에 대해 고민해보자. Update Query는 아마도 간선 가중치 업데이트가 될 것이고, 구간합 쿼리는 경로의 길이를 구하는 쿼리가 될 것이라고 예상할 수 있다. 하지만 Array와 달리 Graph는 연속성이 정해져 있지 않다. 즉, 그래프의 형태에 따라 업데이트 하고자 하는 구간이 연속적일수도 있..