Koo's.Co

Counter Clock Wise는 오른손 법칙을 이용해 주어진 세 점의 방향성을 알 수 있는 알고리즘입니다. 위와 같이 세 점이 주어질 때 이들 벡터와 CCW 알고리즘을 이용해 세 점의 방향을 구할 수 있습니다. A를 기준으로 B와 C에 대한 벡터들의 외적을 구합니다. 여기서는 외적의 결과가 음수기 때문에 오른손 법칙에 의해 세 점이 시계 방향을 갖는 것을 확인할 수 있습니다. 2차원에서의 외적은 z값을 0으로 놓고 계산하여 구할 수 있습니다. x1, y2, z3 = map(int, input().split()) x2, y2, z3 = map(int, input().split()) x3, y3, z3 = map(int, input().split()) u = (x2 - x1, y2 - y1, z2 - z..

1. 프림 알고리즘(Prim's Algorithm) 프림 알고리즘은 방향이 없는 무방향 그래프에서 비용이 최소가 되는 최소 신장 트리(MST, Minimum Spanning Tree)를 찾기 위한 알고리즘이다. 프림 알고리즘은 그리디 알고리즘이 적용된 방법으로 임의의 노드에서 시작하여 노드를 발견할 때마다 연결된 간선 중 가중치가 가장 작은 노드의 방향으로 순회하는 알고리즘이다. 다음과 같은 그래프가 주어질 때 프림 알고리즘을 이용해 최소 신장 트리를 구하려 한다. 여기서는 1번 노드에서 시작해보자. 최종적으로 다음과 같은 최소 신장 트리를 구할 수 있다. 프림 알고리즘을 이용해 최소 신장 트리를 구하면 어느 위치에서 시작해도 동일한 형태의 최소 신장 트리를 구할 수 있다. 프림 알고리즘은 매번 노드가 ..

1. union-find 알고리즘 union-find 알고리즘은 서로 다른 원소가 하나의 집합에 속하는지 확인하기 위한 알고리즘이다. 서로소 집합(Disjoint-set) 알고리즘으로 서로 다른 두 노드가 같은 그래프에 속하는지 확인하는 것이 목적이다. 그래프에서 cycle을 형성하는지 확인하기 위해 사용 두 원소가 같은 집합에 속하는지 확인하기 위해 사용 2. 동작 방법 위와 같은 그래프가 주어질 때, union-find 알고리즘을 이용해 같은 부분집합에 속하는지 확인하려 한다. 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 union-find 알고리즘에서는 각 노드들의 부모 노드들에 대한 테이블을 생성하는데 스스로를 부모 노드로 초기화시켜준다. 1 2 3 4 5 6 7 8 1 2 1 4 5..

1. 그래프의 표현 그래프를 표현할 때는 해당 노드가 어떤 노드와 이어져 있는지를 저장한다. 인접 행렬을 이용해 노드의 관계를 나타내면 메모리의 낭비가 크기 때문에 보통 이어져 있는 노드들의 관계만을 나타내는 방법을 사용한다. # dict를 이용한 그래프 표현 table = {1: [2, 3, 8], 2: [1, 7], 3: [1, 4, 5], 4: [3, 5], 5: [3, 4], 6: [7], 7: [2, 6, 8], 8: [1, 7]} # 리스트를 이용한 그래프 표현 table2 = [[2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]] 생성을 할 때는 아래와 같은 방법으로 생성해줄 수 있다. # dict table = {i +..

1. 유클리드 호제법 유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘 a와 b가 주어질 때, a를 b로 나눈 나머지가 r이라 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 과정을 반복하여 나머지가 0이 될 때까지 반복하면 a와 b의 최대공약수를 구할 수 있다. 2. 예제 ① a = 54, b = 36 r1 = 54 % 36 = 18이므로 ② a = 36, b = 18 r2 = 36 % 18 = 0이다. ③ a = 18, b = 0 ∴ 최대공약수는 18이 된다. def gcd(a, b): while b != 0: r = a % b a, b = b, r return a