https://growth-coder.tistory.com/41 [Algorithm] 다익스트라 (Dijkstra algorithm), 벨만 포드(Bellman ford algorithm) 그래프에서 특정 노드에서 특정 노드까지 가는 최단 거리를 구하는 알고리즘에 대해서 공부해보려 한다. 다익스트라 알고리즘과 벨만 포드 알고리즘이 있는데 이 둘의 차이는 그래프의 가중치 growth-coder.tistory.com 다익스트라, 벨만 포드에 이어서 플로이드 와샬 알고리즘도 알아보려고 한다. 다익스트라와 벨만 포드의 공통점은 두 알고리즘 모두 정점 하나에서 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘이라는 점이다. 두 알고리즘의 차이는 음의 간선의 허용 여부이다. 플로이드 와샬 알고리즘은 모든 정점에..

Network flow 다음과 같은 그래프가 있다고 하자. 각 에지의 가중치는 용량인데 용량은 흐를 수 있는 유량의 최대량이다. 네트워크 플로우 문제는 시작점 s에서 t까지 보낼 때 최대값을 가지는 플로우를 구하는 문제이다. a/b라고 할 때 b는 유량의 총량인 용량을 의미하고 a는 현재 흐르는 유량을 의미한다. 당연히 a가 b보다 클 수는 없다. 다음 그림은 s에서 5만큼 t로 보낼 때의 예시이다. 최소 컷 컷이란 노드들을 두 개의 집합으로 분할하는 것이다. 시작점 s와 도착점 t는 서로 다른 집합에 있어야 한다. 아래는 두 집합 { s, a, c, d } 와 { b, t }로 나눈 예시이다. 다음과 같이 a->b, d->b, d->t 간선들이 컷에 속해있다. 해당 간선들의 비용 총합을 컷의 비용 총합..

아래 그림과 같은 점들이 있다고 하자. 모든 점들을 이어서 다각형을 만들고 싶다면 어떻게 할 수 있을까? 1. 가장 먼저 y 좌표가 가장 작은 점을 기준으로 잡고 다른 점들과 모두 연결한다. 2. 기준으로 잡은 점을 관통하는 x축에 수평인 직선을 긋고 각도를 계산한 후 작은 순서대로 번호를 매긴다. 3. 번호 순서대로 연결한다. 위와 같은 방식으로 모든 점을 지나는 다각형이 완성되었다. 물론 당연하게도 이 다각형 외에도 여러 모양의 다각형을 만들 수 있다. 각도 알아내기 점들을 각도 순서대로 정렬하려면 각도를 알아낼 수 있어야 한다. 각도를 알아내는 방법은 탄젠트 값을 구한 다음에 탄젠트의 역 함수인 아크 탄젠트 함수에 넣으면 구할 수 있다. 그런데 여기서는 정확한 각도를 알아내는 것이 중요한 것이 아니..

어떠한 세 점 A, B, C가 다음과 같이 존재한다고 하자. 선분 AB에 대하여 점 C가 왼쪽에 있는지 오른쪽에 있는지 어떻게 판별할 수 있을까? 여러가지 방법이 존재하겠지만 외적을 사용하면 쉽게 구할 수 있다. 우선 외적의 정의부터 보자. 벡터 u와 벡터 v의 외적을 구하는 공식은 아래와 같다. sin 값은 180도를 기준으로 부호가 바뀐다. 0~180도 전까지는 양수, 180도는 0, 180~360도 전까지는 음수이다. 위의 점 A, B, C도 이를 이용해보자. 먼저 선분 AB, AC를 만들어본다. 벡터 AB와 벡터 AC의 외적 값이 양수라면 C는 선분 AB의 오른쪽에 존재하는 것이고 음수라면 왼쪽에 존재하는 것이다. 다음 그림은 C가 선분 AB의 왼쪽에 있을 때이다. 각도가 180도 넘어가기 때문에..

어떤 배열의 특정 범위에 해당하는 수의 합을 구할 때 부분 합을 사용한다. 이 부분 합의 전처리 과정의 시간 복잡도는 O(N)이고 원하는 값을 구할 때의 시간 복잡도는 O(1)이다. 전처리 과정 sum[ i ]의 값을 arr의 인덱스 0부터 인덱스 i 까지의 합이라고 정의하고 아래와 같은 배열이 있다고 하자. sum[0]은 1일 것이고 sum[1]은 9일 것이고 sum[2]는 12일 것이다. 이를 구하는 과정을 파이썬을 나타내면 다음과 같고 시간 복잡도는 O(N)이다. arr=[1, 8, 3, 4, 6, 7, 4, 4] sum=[0 for _ in range(8)] sum[0]=arr[0] for i in range(1, 8): sum[i]=sum[i-1]+arr[i] 원하는 값 구하기 그런데 위 sum..

RMQ는 어떤 배열이 존재할 때 특정 범위의 가장 작은 값을 구할 때 사용하는 자료구조이다. 다음과 같은 배열이 있다고 하자. RMQ (1, 5)의 의미는 Arr[1] 부터 Arr[5] 까지의 값 중 가장 작은 값을 의미한다. 위 배열의 경우 "3"이 된다. 이 RMQ를 구하는 방법에는 여러가지가 있지만 그 중 전처리 과정의 시간 복잡도가 O(N*log N)이고 원하는 값을 얻을 때의 시간 복잡도가 O(1)인 방법을 공부해보려고 한다. RMQ 전처리 과정 우선 길이가 1인 RMQ를 구한다. RMQ (0, 0), RMQ (1, 1), RMQ(2, 2) ... RMQ(N, N)을 모두 구하는 것이다. 길이가 1이기 때문에 당연하게도 RMQ(i, i)의 값은 arr[ i ]의 값과 똑같을 것이다. 그 다음 길..