중독에 취약 중독에 취약

1. 개요Convex Hull 알고리즘 중에서 가장 신경쓸 부분(double precision)이 적은 알고리즘으로, 어찌보면 가장 강력한 방식의 알고리즘이다. Graham's Scan 방식과 유사한 방식으로 진행되는 알고리즘이다.전체적인 방식은 유사하지만 graham scan 방식을 변형한 (위, 아래를 따로 계산하는) 방식으로 진행된다.2. 알고리즘Monotone Chain 방식은, 제일 왼쪽에 있고 가장 아래에 있는 점과 제일 오른쪽에 있고 가장 윗쪽에 있는 점이 convex hull에 포함된다는 특징을 통해 알고리즘을 진행해 나간다.주어진 점들을 x좌표와 y 좌표를 기준으로 정렬한다.아래 껍질을 넣을 스택을 초기화한다.각 점들을 정렬된 순서대로 순회한다스택의 크기가 2 이상일 때..

1. 개요 자비스의 행진 알고리즘은, convex hull 문제를 해결하기 위한 알고리즘이다. 말만 들으면 아이언맨에 나온 자비스가 생각난다. Jarvis라는 사람이 만들었고 마치 행진하듯 알고리즘이 진행되어 Jarvis's March라는 이름이 붙었다. 또 다른 이름으로는 선물 포장 알고리즘이라는 이름이 있다. 이 알고리즘은 다른 알고리즘들에 비해 상당히 속도가 느리다는 단점이 있지만, 3차원 이상의 공간으로 확장될 수 있다는 장점이 있다. 2. 알고리즘 간단하게 진행하기 위해, 3개의 정점들이 같은 직선 위에 있는 경우는 없다고 가정한다. 처음 시작할 때, 시작점 $P_0$에서 시작하고 $i = 0$으로 설정한다. 이때, $P_0$는 Convex hull에 포함되어 있는 점 중 하나로 일반적으로 가장..

1. 개요 convex hul에 속한 모든 정점들을 찾는 알고리즘으로, $O(n\log{n})$시간의 시간 복잡도를 가진다. 효과적으로 이전 값을 탐색하고 삭제하기 위해 stack 구조를 활용하여 알고리즘이 진행된다. 3차원 공간에서는 결과를 얻을 수 없다..는 단점이 있다. 컴퓨터에서는 floating point로 각도를 계산해야 하니... 오차가 꽤나 많이 생긴다는 단점도 있다. 2. 알고리즘 가장 작은 y좌표값을 갖는 정점을 시작점 $P$로 잡는다. 만약 같은 y좌표를 갖는 정점이 여러개라면 x 값이 가장 작은 것을 선택한다. 정점 목록을 $P$와 x축이 이루는 각도에 따라 정렬한다. 직접 각도를 계산할 필요는 없다. x축과 이루는 각이므로, 직선의 기울기, 내적으로도 쉽게 판별이 가능하다. 만약 ..

1. 개요 MST(Minimum Spanning Tree), MSF(Minimum Spanning Forst)를 얻기 위해 사용하는 탑욕법 기반의 알고리즘이다. 처음으로 제시된 것은 1926년에 Otakar Borůvka에 의해 고안된 알고리즘으로, 체코에 있는 Moravia의 전력망 건설을 효율적으로 하기 위한 방식으로 제안되었다. (꽤나 신기한 이유에 의해 고안된 알고리즘이라 생각된다. 사실 네트워크 연결이나... 전력망 연결이나... 거의 비슷한 느낌으로 연결하니까 그럴 법도 하다 생각된다.) 2. 과정 입력은 서로 연결된, 가중치가 존재하는 무향 그래프를 입력으로 받는다. 입력으로 받은 그래프의 정점들을 하나씩 forest T에 넣어 초기화한다. T 가 하나보다 많은 요소를 갖고 있을 경우(min..

1. 개요 Dancing Link 기법은, $O(1)$시간에 삭제를 진행하고, 삭제된 값을 다시 복구 할 수 있는 기법으로 어떤 링크의 주소값을 알 경우 바로 그 위치에 복구할 수 있는 방식이다. 2. 방법 이중연결 리스트인 $P$에서, $D$에 속한 노드 $x$에 대해 $L[x]$가 왼쪽에 위치한 노드를 의미하고 $R[x]$가 우측에 위치한 노드를 의미한다면 다음과 같은 방식으로 x 노드의 삭제가 이루어진다. $L[R[x]] := R[x]$ $R[L[x]] := L[x]$ 이때, 노드 x는 메모리에 할당되었지만 아직 할당 해제가 풀리지 않았기 때문에, 아직 메모리 상에 존재한다. 이를 활용하여 x를 다시 복구하는 것은 다음과 같이 이루어진다. $L[R[x]] := x$ $R[L[x]] := x$ 이는 ..

1. 개요X 알고리즘은 전설적인 컴퓨터공학자이자 수학자인 Knuth에 의해 Dancing Link를 소개하면서 같이 서술한 알고리즘으로  Exact Cover 문제를 좀 더 효과적으로 해결하고자 만들어진 알고리즘이다. 이때, 여타 기법들과 동일하게 Back Tracking 기법을 사용하는 알고리즘이지만 Back Tracking을 적용하는 대상에 차이가 있다는 특징이 있다. 일반적인 Back Tracking 알고리즘의 경우에는 직접 시도하며 제약조건을 만족하는지를 판단하고 다시 뒤로 돌아오는 전략을 취하지만, X 알고리즘의 경우에는 각 제약조건들을 열로 잡고 행은 가능한 경우를 넣은 0-1 행렬 내에서 Back Tracking을 진행한다.2. 방법X 알고리즘은 처음 보면 이해하기 상당히 까다롭다. 행과 열..

1. 개요 무한 원숭이 정리는 신박한 개념의 정리인데, 무한대의 원숭이가 타자기를 치는 작업을 한다면 언젠가는 분명, 셰익스피어의 희곡 전집을 타자로 옮길 수 있을 것이라는 내용의 정리이다. 여기서 중요한 가정은 원숭이는 타자를 칠 때, 각 타자를 치는 문자 사이에 관련이 없어야 한다. 충분한 시간이 흘러야 한다. 의 두 가지인데, 듣고 보면 확률적으로 보면 확실히 그럴듯한 말이다! 가능성이 있는 일은 무한정 시도하다 보면, 결국에는 성공할 수밖에 없다는 내용이기 때문이다. 2. 증명 몇 가지 가정을 하고 들어가면 원숭이가 어떤 글자를 칠지는 온전한 무작위이다. 원숭이는 하나의 글자를 1초에 한 개씩 친다. 셰익스피어의 전집에는 34개의 문자만 사용되었다.(알파벳, 마침표, 콤마, 콜론, 세미콜론, 큰따..

1. 특징 순수하게 포인터에 기반한 자료구조이다. 배열은 사용되지 않으며 key는 수치적 가정에 기반하지 않는다. 자료구조의 heap order 속성을 지키기 위해 key는 결국 증가한다. 특정 키의 값을 인위적으로 올리는 방식을 통해 자료구조의 엔트로피를 낮춘다. 비교 기반 모델에서 로그 복잡도보다 나은 성능을 보인다. e값이 어떤 값인지에 상관없이 Soft heap은 비교 기반 모델에서 최적의 성능을 가진다. insert를 제외한 연산들의 armortized complexity는 $O(1)$이며 insert의 경우 에러율이 $\epsilon$일 때, $O(log 1/\epsilon)$이다. 에러율이 $\epsilon(0 next = tail, t..