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의..

1. IP(Internet Protocol) IP는 Network Layer에서 송신자와 수신자가 패킷을 교환하기 위해 사용하는 프로토콜입니다. IP는 패킷(데이터그램)을 여러 개의 덩어리로 나누어 전송하게 됩니다. IP는 패킷의 형식을 정의하고 주소 시스템을 사용하는 프로토콜입니다. IP는 다음과 같은 특징을 갖습니다. IP는 비신뢰성(unreliability)이다 비신뢰성은 전송 흐름에 관여하지 않기 때문에 보낸 정보가 제대로 갔는지 보장하지 못하는 것을 의미합니다. 패킷은 손상되거나 loss될 수 있고 순서가 바뀌거나 중복으로 전달될 수도 있습니다. 패킷 전송과 순서를 보장하기 위해서는 상위 Layer에서 TCP와 같은 프로토콜들을 이용해야 합니다. IP는 비연결성(connectionlessness..

1. Client-Server model client는 네트워크를 통해 서버에 접속하여 데이터나 서비스를 제공받는 역할을 합니다. 보통 end host라 하며 일반 사용자가 client에 해당합니다. 엄밀히 말하면 서버에게 정보를 요청하는 응용 프로그램이나 서비스를 의미합니다. server는 서비스를 제공하는 컴퓨터를 의미하며 Http 서버, Database 서버, 웹 서버, DNS 서버 등 client에게 데이터나 서비스 등을 제공하는 역할을 합니다. client-server model은 정보 공유에 초점을 두고, 데이터 관리가 서버에 의해 이루어집니다. 클라이언트는 서버에게 정보를 요청할 수 있고, 서버는 이에 응답해주는 방식으로 동작합니다. 여러 클라이언트가 동시에 서버에 접속하면 서버에 부하가 늘..