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

배수 판정법 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 배수 판정법은 배수인지 확인하려는 수의 배수가 맞는지 간단히 확인하는 절차이다. 일반적으로 정수 m , n {\displaystyle m,n} 에 대해 m {\displaystyle m} 이 n {\displaysty ko.wikipedia.org 확인하려는 수가 배수인지 확인하기 위해 사용하는 방법이다. 1: 모든 수는 1의 배수 3: 각 자리 수의 합이 3의 배수인 수 4: 가장 끝 두 자리수가 0이거나 4의 배수인 수 6: 2와 3의 공배수, 짝수이면서 각 자리 수의 합이 3의 배수인 수 7: 일의 자리를 두 배 한 것을 나머지 수에서 뺀 결과가 0 또는 7의 배수가 나오는 수 8: 가장 끝 세 자리수가 0이거나 8의..

전에 파이썬의 bisect 라이브러리의 bisect_left와 bisect_right을 다룬 적이 있었습니다. 그 때는 기본적인 함수의 동작방식과 사용방법에 대해서만 공부해봤는데 최근에 LIS 문제를 다시 풀어보면서 lower bound를 다시 공부할 기회가 생겼었습니다. 오늘은 직접 bisect_left, bisect_right를 구현해보려 합니다. 오늘 게시물을 보기 전에 아래 게시물에서 lower bound와 upper bound에 대해 읽어보고 오시길 추천드립니다. 간단하게 lower bound: target "이상(target 포함o)"이 처음 나오는 위치 upper bound: target"보다 큰(target 포함x)" 값이 처음 나오는 위 [Python] bisect 라이브러리 (lower..

1. 피보나치 수열 피보나치 수는 첫째 항과 둘째 항이 1이고 뒤에 나오는 모든 항이 앞 두 항의 합인 수열이다. 앞의 두항의 합만 구하면 다음 항을 구할 수 있으므로 코드로 구현하면 다음과 같이 간단하게 표현할 수 있다. N = int(input()) def fibo(x): if x == 0: return 0 if x == 1: return 1 return fib(x - 1) + fib(x - 2) print(fibo(N)) 하지만 이 코드에는 큰 문제점이 있는데... 앞서 구했던 피보나치 수의 값을 기억하질 못한다... N=5라고 할 때 피보나치 수를 구하면 위와 같다. 동일한 계산을 여러 번하는데 전에 이미 값을 구했는데도 하위 연산을 하면서 값을 다시 구한다. 값이 하나 증가할 때마다 연산의 횟수..