코딩못하는사람

CCW ( Counterclockwise) 말 그대로 시계 반대 방향이다. 외적을 이용하여 유도할 수 있다. CCW알고리즘을 이용하여 세점의 방향성을 알 수 있다. 1. 반시계 방향인 경우 2. 시계 방향인 경우 3.세 점이 평행한 경우 출처: https://jason9319.tistory.com/358 [ACM-ICPC 상 탈 사람] 각각의 점을 A(x1, y1) , B(x2, y2), C(x3, y3) 이라고 좌표를 두고, A,B,C 순서로 방향관계를 구한다면, CCW 함수의 return값은 x1y2 + x2y3 + x3y1 - (x2y1 + x3y2 + x1y3) 이 된다.(신발끈 공식과 같다) RETURN값이 음수이면 시계방향. 양수이면 반시계방향. 0이면 세점이 평행하다. 이 알고리즘을 이용하여..

1.접근 N의 범위를 모르고 (1 ≤ N ≤ 100,000) 모든간선을 만드는 N^2으로 풀었다가 시간초과를 받았다. 그래서 NlogN으로 풀려고 정렬을 생각했다. 2.풀이 정점들이 주어진다고 해서 이전문제들 같이 모든 간선을 만들 수 없다. 근데 만들필요도 없다. 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이라고 했으므로 x,y,z축들의 값을 따로 따로 보면된다. 이 부분이 생각하기 힘들었는데 x,y,z축 좌표들을 각각 정렬해놓고 바로 앞,뒤 값들의 차이로 간선들을 만들고 힙에 넣으면 된다. 이렇게 되면 힙에서 빠져 나오는 값들은 비용의 최소값부터 나올 것이다. x,y,z축을 정렬해줄때 좌표의 값도 같이 넣어주어야 쉽다. 이후 유니온 파인드와 크루스칼 알고리즘을..

플로이드-와샬 알고리즘 다익스트라 알고리즘이 한 정점에서 모든 정점까지의 최단거리를 구해주는 알고리즘이라면 플로이드-와샬 알고리즘은 모든정점에서 모든정점으로의 최단거리를 구해주는 알고리즘이다. 다이나믹 프로그래밍을 기반으로 거쳐가는 정점을 기준으로 한다는 특징이 있다. 다익스트라와 다른점은 다익스트라는 힙을 이용하여 일차원 배열에 값을 나타냈으므로 입력을 받을 때 adj[시작점]=(가중치,목적지)를 받았다면 플로이드는 2차원배열 adj[시작점][목적지]=가중치로 저장한다는 차이가 있다. 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다. 식으로 설명해보자면 현재의..

벨만-포드 알고리즘 다익스트라와 마찬가지로 SSP알고리즘인 벨만-포드 알고리즘은 음의 가중치를 다룰 수 있다. 그런데 다음과 같이 음의 가중치로 인해 순환 구조를 가진다면 최단경로를 구할 수 없다. 따라서 벨만-포드 알고리즘은 최단경로를 구하는 것과 이 그래프에서 최단경로를 구할 수 있는지 없는지를 판별하는 과정 두 과정으로 나눠진다. 벨만 포드 알고리즘은 V-1번 모든 간선을 Relax하는 작업을 수행한다. 최단경로구하기 동작과정은 각 정점들을 돌아 가면서 모든 간선들을 탐색한다, 단 맨 처음은 시작점부터 탐색한다( 처음 이후에는 순서 상관없음) D(s,v)=D(s,u)+w(u,v) 이 과정을 V-1번 탐색하는 이유는 s에서 v까지 가는 경우에서 v를 뺀 모든 경로가 각각 최단거리일 수 있기 때문이다(..