cloge 이야기

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

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

...set operator만 해결하면 잘 쓸줄 알았다...하지만 아니었다. 어떤 문제에서 set을 쓰다가 잘못써서 10번도 넘게 제출했다...(APIO 2007 Backup...) 다시 한 번 set을 잘 쓰길 기원하며 정리한다. insert( data key ) - set에 원소를 넣는다. 넣는 형태는 정의한 자료형begin() - 정의된 set의 operator 연산의 첫 원소의 주소를 반환한다.end() - 정의된 set의 마지막 원소 다음번 주소를 반환한다. 즉, 마지막 원소를 가리키고 있는 iterator를 ++ 시키면 end() 주소를 가리키게 된다.rbegin() - 정의된 set의 operator 연산의 마지막 원소의 주소를 반환한다.lower_bound( data key ) - data..