david의 CS Blog

BitMasking 수학에서의 집합은 원소들의 포함 여부를 가진다. 이를 프로그래밍을 통해 표현하기 위해서는 Array 등의 메모리 공간을 이용해서 표현할 수 있다. 이 때, 각 원소의 존재 여부를 0 혹은 1로 표시하는 방법이나, 원소들을 일일이 Array, Vector에 저장하는 방법으로 집합을 포현할 수 있다. 하지만 Array, Vector 등의 여러 원소를 포함하는 Container 뿐만 아니라 다른 방법으로도 집합을 표현할 수 있는데, BitMasking이 그 방법이다.BitMasking은 정수의 이진수 표현을 이용하여 집합을 나타내는 방법으로, 위에서 설명한 Array로 집합을 표현하는 방식에서 각 원소의 존재 여부를 0 혹은 1로 표시하는 방법을 채택한다. 4 Byte의 Integer를 구..

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

Convex Hull  2차원 좌표 평면에 여러 점이 존재하는 상황을 생각해보자. 이러한 점들을 다루는 2차원 평면은 너무 넓다. 다시 말해서, 탐색 범위나 관심을 가지는 구간을 2차원 평면 전체로 잡는 것은 너무 비효율적이며 관심 있는 구간을 설정하는 과정이 필요하다는 것이다.Convex Hull은 점들이 포함되는 영역과 포함되지 않는 영역으로 2차원 좌표 평면을 나누어 줄 수 있는 도형이다. 즉, Convex Hull 안에는 점들이 모두 포함되지만, 밖의 영역에는 점들이 존재하지 않는 것이다.  Convex Hull은 2차원 좌표 평면에 존재하는 여러 점들 중 일부를 이용하여 만들 수 있는 모든 점을 포함하는 볼록 다각형이다. 점들을 이용하여 만든 도형이기에, 다른 말로 표현하면 모든 점을 포함하는 ..

단절점과 단절선  이 글을 보기 전에, DFS Spanning Tree를 읽고 오는 것을 권장한다. DFS Spanning Tree를 통해 일반 그래프를 트리로 표현하는 방법에 대해 공부했다. 이제 간선 분류를 통해 그래프에서 의미 있는 정점, 간선들을 찾는 방법에 다룰 것이다. 그 중 대표적인 예시가 바로 Articulation Point와 Bridge이다. 이들은 무향 그래프에서만 정의되는 개념이므로, 연결 관계에 관련된 개념이다. 하나의 컴포넌트로 구성되어 있는 그래프에서, Articulation Point와 Bridge는 다음과 같이 정의한다.  특정 정점을 제거하였을 때, 컴포넌트 수가 증가하면 그 정점은 Articulation Point이며,특정 간선을 제거하면 컴포넌트 수가 증가하는 간선을 ..

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는 연속성이 정해져 있지 않다. 즉, 그래프의 형태에 따라 업데이트 하고자 하는 구간이 연속적일수도 있..

벨만 포드 알고리즘이란? 다익스트라 알고리즘처럼 최단경로를 구해주는 알고리즘이다. 시간복잡도는 다익스트라 알고리즘보다 오래 걸리는 $O(|V||E|)$이지만 간선의 가중치가 음수일 때 사용 가능하다. 다익스트라 알고리즘으로는 간선의 가중치가 음수일 때 계속해서 갱신이 일어나므로 무한 반복이 일어나 최단경로를 제대로 구하지 못할 수 있으므로 벨만 포드 알고리즘을 사용한다. 벨만 포드 알고리즘의 핵심은 음수 가중치의 판단이고, 이는 최단 경로가 갱신되는 횟수로 구한다. 다익스트라 알고리즘에서 특정 정점에 대한 최단경로 갱신은 최대 몇 번 일어날 수 있을까? 먼저 가능한 최단 경로의 길이(거치는 정점의 수)를 생각해보자. 모든 정점을 최대 1번만 지날 수 있으므로 그 길이는 |V|이다. 또한 최단 경로 갱신 ..

LCA 알고리즘이란? 트리에서 두 정점 $u$, $v$의 가장 가까운 조상을 찾는 알고리즘이다. 즉, 두 정점 $u$, $v$가 만날 때까지 루트 쪽으로 정점을 올려주면 두 정점이 만났을 때의 정점이 최소 공통 조상이 된다. 이 트리에서 $5$번 정점과 $7$번 정점의 최소 공통 조상은 $2$번이고, $4$번 정점과 $6$번 정점의 최소 공통 조상은 1번 정점이다. 최소 공통 조상을 구한다면 트리에서 두 정점 간의 최단 거리 등을 쉽게 구할 수 있고, 그 외에도 다양하게 사용할 수 있다. 이를 구하기 위해 DP를 이용해서 $O(logN)$으로 해결할 것이다. 구현 1. dfs를 통해 트리의 각 정점의 깊이와 정점들의 조상을 구한다. 이때 조상은 $2^{0}$, $2^{1}$, $2^{2}$, ...번째 ..

위상정렬이란? DAG(Directed Acyclic Graph, 방향이 있고 사이클이 없는 그래프)에서 방향을 거스르지 않고 나열하는 것을 위상정렬이라고 한다. 예를 들어 이 그래프에서 위상정렬을 하면 1->2->4->3 또는 1->2->3->4가 결과로 나올 수 있다.(위상정렬의 결과는 여러가지일 수 있다.) DFS를 이용한 구현 dfs를 수행하며 방문한 정점의 순서를 구하면 된다. dfs를 수행하며 dfs가 종료되는 순서를 기록한 후 이를 뒤집어주면 된다. 방문하는 정점들을 스택에 집어넣고 차례대로 꺼내면서 출력해줘도 된다. 아래 코드는 방문한 정점들을 벡터에 집어넣고 벡터를 뒤집었다. #include #include #include using namespace std; int n, m; bool v..

투 포인터란? 배열 내에서 연속된 값들을 이용해서 문제를 해결해야할 때, 두 개의 인덱스를 나타내는 변수들을 움직이며 문제를 해결하는 알고리즘이다. 예를 들어 $N$개의 자연수로 이루어진 수열이 주어졌을 때, 이 수열에서 연속되는 부분 수열 중 합이 $S$가 되는 부분 수열의 개수를 구하는 알고리즘을 생각해보자. $O(N^{2})$의 알고리즘 연속된 부분 수열 중 합이 S인 부분 수열의 개수를 찾아야 한다. 부분 수열의 시작 인덱스와 끝 인덱스를 각각 a, b라고 하면 가능한 모든 (a, b)의 순서쌍을 구하고 각각의 부분 수열이 합이 S가 되는지를 확인하면 된다. 예를 들어 [5, 4, 3, 2, 6, 3, 5, 9, 10]의 수열에서 부분 수열 [4, 3, 2, 6, 3]은 1번 인덱스부터 5번 인덱..