두 선분의 교차 판정(2), CW/CCW, python
두 선분의 교차 판정(1), python 두 선분의 교차 판정(1), python선분 교차 판정이란점 A, 점 B를 양 끝으로 하는 선분 AB와 점 C, 점 D를 양 끝으로 하는 선분 CD가 최소 1개 이상의 공통점을 가지는 경우를 두 선분이 교차한다고 말한다. 첫번째 그림과 같이 한점aiden0413.tistory.com 이전글에서는 매개변수 방정식을 이용해서 두 선분이 교차하는지를 판별했다.벡터의 외적을 이용해서 선분 교차를 판별하는 방법도 있다. 벡터의 외적을 통한 CCW(반시계 방향), CW(시계방향) 판별 방법 A, B, C 세 점이 있을때 벡터 \(\vec{AB}\)와 벡터 \(\vec{AC}\)의 외적 \(\vec{AB}\times \vec{AC}\)의 부호를 통해 A, B, C가 시..
이분 그래프(bipartite graph), python
이분 그래프란? 이분 그래프란 그래프의 정점들을 2개의 집합으로 나누었을 때 각 집합 내의 정점들 간에 서로 연결된 간선이 없도록 분리할 수 있는 그래프를 말한다. 위 그래프에서 집합1 = [1, 3, 5], 집합 2 = [2, 4, 6]으로 분리하게 되면 집합 1에서 1, 3, 5번 정점들 사이에 연결된 간선이 없고, 집합 2에서도 2, 4, 6 사이에 연결된 간선이 없다.이렇게 그래프를 2개의 집합으로 분리 할 수 있으면 이분 그래프라고 한다. 여기서 집합1을 파란색, 집합 2를 빨간색으로 칠하게 되면 한 정점에서 인접한 정점들은 반대색이 됨을 알 수 있다. 그래프가 이분 그래프인지 판별하는 방법 인접한 정점들의 색이 반대가 된다는 점을 이용해서 이분 그래프인지 판별할 수 있다. ..
강한 연결 요소(SCC), 코사라주(Kosaraju) 알고리즘, python
강한 연결 요소란? 강한 연결 요소, SCC(Strongly connected component)란 방향이 있는 그래프의 정점 u, v에서 u → v, v → u로 가는 경로가 모두 존재하는 최대 정점 집합이다. 즉 양방향으로 연결된 하나의 큰 덩어리 같은 거다. 1과 4는 1에서 4로 1 → 4 가 존재하고, 4에서 1로 4 →5 →1가 존재하므로 같은 SCC이다.1과 5도 1 →4 →5 와 5 →1이 존재하므로 같은 SCC이다.하지만 1과 6은 1 →6은 존재하지만 6 →1 이 존재하지 않으므로 같은 SCC가 아니다. 따라서 위 그래프에서 SCC는 [1, 4, 5], [6], [2, 3, 7] 3개로 나눌 수 있다. SCC를 구하는 방법 SCC는 코사라주 알고리즘을 통해 구할 수 있다.코사라..
LIS(가장 긴 증가하는 부분 수열), python
가장 긴 증가하는 부분 수열이란? 가장 긴 증가하는 부분 수열, LIS(Longest Increasing Subsequence) 란 오름차순으로 정렬된 부분 수열 중에 가장 긴 것을 말한다. 예를 들면 수열이 [10, 20, 5, 30, 15, 50]에서 [10, 20 ,30, 50]이다. LIS의 길이를 구하는 방법 첫 번째로 가장 간단하게 LIS를 구하는 방법은, k번 인덱스에서 0~k-1번째 요소까지 확인하면서 찾는 것이다.시간 복잡도가 O(n^2)이 나오기 때문에 수열의 길이가 커지면 이 방법은 사용할 수 없다. 두 번째 방법은 LIS를 저장하는 별도의 리스트를 만들어서 구할 수가 있다.수열에서 하나씩 탐색하면서 LIS배열이 비어있다면 집어넣어 준다.만약 LIS배열이 비어있지 않다면..
세그먼트 트리, python
세그먼트 트리란? 세그먼트 트리란 완전 이진 트리에 배열의 구간 정보(최대, 최솟값, 합, 곱 등)를 저장하고 빠르게 구간 쿼리를 처리할 수 있는 자료구조이다.완전 이진트리란 리프노드를 제외한 모든 노드들의 자식노드들을 2개씩 가지고 있어야 하고 왼쪽부터 채워져 있어야 한다. 이 트리는 리프노드 8,9,10,11,12를 제외한 모든 노드들의 자식노드가 2개씩 있고 왼쪽부터 채워져 있으므로 이진트리이다. 완전 이진트리는 배열로 구현할 수 있다.루트노드의 인덱스는 1번이다.왼쪽 자식노드는 부모노드의 인덱스 * 2번이 되고, 오른쪽 자식노드는 부모노드의 인덱스 * 2 + 1이 된다. 세그먼트 트리의 크기 구하기 세그먼트 트리는 완전 이진트리로 구현할 수 있다.배열이 [6 , 3 , 7, ..