VennTum 이야기 VennTum 이야기

보통의 점화식의 경우, 매 항의 값을 식의 정의를 통해 구하게 된다. 하지만 구하고자하는 항이 10억번째 항과 같이 매우 큰 수번째 항을 구해야 하는 경우, 모든 값을 일일이 계산하기엔 처리 속도에서 문제가 생긴다. 하지만 최대 10억번째 항까지의 값이 필요하다고 해도 한 개의 항의 값만 필요하거나 그 범위 내 10만개 등 몇 개의 항의 값만을 알아내야한다면 전체를 다 계산하는 것이 아닌, 일부를 계산하는 방법으로 해결할 수 있다. 행, 열의 길이가 최대 m인 행렬로 표현 가능한 점화식의 한 항을 O(lgN * m^3)에 해결할 수 있는 방법 위와 같이 주어진 점화식이 있을 경우, 이를 행렬로 다음과 같이 표현 가능하다. 이 때, 라 정의하면, 행렬의 거듭제곱의 성질을 이용하면 임을 알 수 있고, 이로써..

Sliding Window(슬라이딩 윈도우)란 수행 과정에서 필요한 전체 메모리를 할당하는 것이 아닌 매 수행마다 필요한 부분만큼만을 저장하여 사용함으로 메모리를 절약, 공간 복잡도를 낮추는 기법이다. 즉, 수행한 이후에 사용하지 않게 되는 기록을 버림으로 매 순간 필요한 정보들만을 저장, 이용한다. 이러한 형태가 실제로 필요한 메모리 할당들을 지정된 크기의 창문에 할당한 이후, 그 메모리를 창문으로 밀어넣음으로서 매 순간에는 창문 크기 내의 정보만을 이용하는 것과 같아 Sliding Window라고 불린다. 창문 창문에 밀어넣을 배열 창문과 배열에서 값의 이동 피보나치 함수를 예로 들어보자. Fn+1 = Fn + Fn - 1 (n > 2) , F2 = 1, F1 = 1 DP를 이용하여 임의의 N에 대해..

Spanning Tree(신장 트리)란 연결 그래프에서 모든 정점과 그래프 내의 간선들을 이용하여 구성하는 트리를 말한다. 즉, 연결 그래프 내의 간선들을 이용하여 모든 정점을 잇는 트리들을 신장 트리라고 부른다. 연결 그래프와 신장 트리 Minimum Spanning Tree(MST, 최소 신장 트리)란 가중치를 가진 연결 그래프에서 신장 트리를 만들 때에 간선의 가중치 합이 최소가 되는 신장 트리를 말한다. 이 때의 Minimum Spanning Tree는 연결 그래프 내에서 유일하지 않을 수 있다. 가중치 연결 그래프와 최소 신장 트리 최소 신장 트리는 전자 회로의 설계 시, N개의 핀을 연결 하기 위해 N-1개의 전선을 이용하여 전기적으로 동등하게 만드는 경우, 전선의 길이를 최소로 사용하는 방법..

Floyd-Warshall 플로이드 워셜 알고리즘(흔히 플로이드라고 부른다)은 그래프에서 모든 정점 사이의 최단경로 및 최단거리를 구하는 알고리즘이다. Bellman-Ford, Dijkstra와는 다르게 한 정점으로부터 나머지 모든 정점으로의 최단경로가 아닌 모든 정점 사이의 최단경로를 구할 수 있으며, 음수 사이클이 없는 그래프라면 음수 가중치가 있어도 동작한다. 플로이드 알고리즘은 다음과 같은 점화식에 기반하고 있다. 정점의 수가 V인 그래프에서 플로이드의 점화식 D[i][j] = (정점 i로부터 정점 j로의 최단거리) D[i][j] = min(D[i][j], D[i][k] + D[k][j]) (1

Bellman-Ford 벨만 포드 알고리즘은 음수 가중치가 있고, 음수 사이클이 없는 그래프에서 한 정점으로부터 다른 모든 정점으로의 최단경로 및 거리를 구하는 알고리즘이다. 다익스트라와는 달리 간선에 음수 가중치가 있어도 본래의 시간복잡도를 가지고 동작하며(단, 이 때에는 무방향 그래프가 아니어야 한다), 음수 사이클이 있는 경우는 무한히 사이클을 루프할 수 있다는 점에서 최단경로를 구할 수 없다. 단, 벨만 포드 알고리즘의 장점은 그래프 내에 음수 사이클이 있을 경우, 음수 사이클이 있음은 판단할 수 있다. 벨만 포드는 다음과 같이 동작한다. 시작점을 제외한 모든 정점으로의 최단거리를 무한으로 설정한다(시작점은 0). 이후 다음 수행을 반복한다. 1. 그래프 내에 모든 간선에 대해 2번을 시행한다. ..

Dijkstra 다익스트라 알고리즘은 그래프에서 한 정점에서부터 다른 모든 정점으로의 최단경로를 구하는 알고리즘이다. 여기서 최단경로란, 정점과 정점 사이를 잇는 간선이 가중치를 가지고 있을 때, 한 정점에서 다른 정점으로 간선을 타고 이동할 수 있는 경로중 가중치의 합이 가장 작은 경로를 말한다. 다익스트라는 한 정점으로부터 다른 정점으로의 최단경로와 그 과정에서 거치는 간선들의 가중치 합을 알아낼 수 있다. 일단, 다익스트라를 설명하기에 앞서 다익스트라는 그래프 내에 음의 가중치 합을 가지는 사이클이 없을 때에만 동작하고, 음의 가중치를 갖는 간선이 없을 경우에만 언급하는 시간복잡도에 동작함을 언급하고 가겠다. 다익스트라는 아래와 같이 동작한다. (가중치를 거리로 표현하겠다.) 처음, 시작점을 제외한..

Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말한다. 서로 다른 원소들이 같은 집합에 속해있는지 판별하는데 쓰인다. 이를 활용하기 위해서는 Disjoint Set Union(DSU, 분리합집합) 자료구조를 만들 수 있어야 한다. Disjoint Set 사이에는 교집합이 없기 때문에(정의로 인해), 서로간을 합해주는 연산으로 집합이 합쳐지는 과정이 있을 수 있다. 합하는 과정을 매우 빠르게, 그리고 원소를 판별하는 과정또한 매우 빠르게 하기 위해서 DSU를 사용한다. 먼저, Disjoint Set는 트리를 이용하여 표현하는데, 같은 집합에 속한 원소들 중 하나를 루트로 하고, 나머지 원소들을 각각 루트 원소의 자식이 되도록 표현하는 것이다..

Sparse Table이란 전체 N개의 원소들 중 임의의 원소 A에 대해, A를 바로 앞서서 있는 원소가 1개 이하 존재하는 상황에서, 원소 A의 K번째 앞에 있는 원소를 찾는 경우 사용하는 방법이다. (단, 임의의 원소 A를 바로 앞서서 있는 원소는 여럿일 수 있다. 즉, 원소 A의 바로 뒤에 있는 원소의 제한은 없다.) '임의의 원소 A의 K번째 앞에 있는 원소를 찾아라' 라는 질문이 Q번 들어올 경우, 이를 해결하기 위해 Sparse Table이란 방법을 이용하여 빠르게 구할 수 있다. Sparse Table을 이용하지 않고 가장 단순한 방법으로는 O(QN)의 시간복잡도를 가지는 방법이 있다. Naive - O(QN) A의 바로 앞 원소를 알고 있으므로, 쿼리마다 주어진 A에서 바로 앞으로 K번 이..