keicoon15

피보나치 힙을 다시 공부하게 되서 정리한 글. 흔히 피보나치 힙을 들으면 '피보나치 수열'을 떠올린다.그리고 '힙'을 보면 떠오르는 '트리.. 힙?'이 있다.정의로 따지면 둘 다 맞다.우선 피보나치 힙이다보니 힙 구조를 가지게 된다.힙의 주요 기능들 'INSERT, MINIMUM, EXTRACT-MIN, UNION, DECREASE-KEY, DELETE' 연산이 필수적이다.하지만 그냥 힙구조 쓰면 되지가 아니라ㅎ 성능상 이점이 다르다.OperationBinary[6]Binomial[6]Fibonacci[6]Pairing[7]Brodal[8][a]Rank-pairing[10]Strict Fibonacci[11]find-minΘ(1)Θ(1)Θ(1)Θ(1)Θ(1)Θ(1)Θ(1)delete-minΘ(log n)..

A brute-force sub string search 알고리즘1 function NaiveSearch(string s[1..n], string pattern[1..m]) 2 for i from 1 to n-m+1 3 for j from 1 to m 4 if s[i+j-1] ≠ pattern[j] 5 jump to next iteration of outer loop 6 return i 7 return not found시간 복잡도 : O(mn) Rabin-Carp 알고리즘1 function RabinKarp(string s[1..n], string pattern[1..m]) 2 hpattern := hash(pattern[1..m]); hs := hash(s[1..m]) 3 for i from 1 to ..

이전에 A* Algorithm에 대해 글을 쓴적이 있다.그 때는 이론적인 부분만 설명을 했고이번엔 직접 구현을 해서 설명을 하려한다. 아이디어는 이전 글을 참고하자.http://keicoon15.tistory.com/entry/a-search 빨간 선의 왼쪽(시작 지점)과 오른쪽(끝 지점)을 기준으로 최단경로(A* Algorithm)의 결과이다.이 때, 마우스로 검은색 사각형영역(장애물)을 생성하면 최단경로가 갱신된다. 프로그램은 c#에서 작성했으며 Pixel 단위로 영역을 정의했다.F = G + H를 계산할 때는 다른 참고 글에서(가로, 세로 : 10, 대각선 : 14)를 사용했는데이번 구현에서는 Distance를 직접 구했다(sqrt를 사용하므로 속도가 느리다)차후 수정이 필요하지만 완성되었으므로 코..

Convex Hull문제를 해결하는 방법 중에 GrahamScan이 있다. 참고 : https://en.wikipedia.org/wiki/Graham_scan 예전에 문제에서 알게되고 관심있게 보았던 알고리즘. 간단히하면 주어진 Point에서 외각의 점들을 선택하는 알고리즘이다. 이것으로 최외각 다각형을 구할 수 있으며, 응용할 여지가 많다. Wiki의 코드를 사용해 구현했다. 환경은 c#에 Graphics를 사용했다. using System; using System.Drawing; using System.Collections.Generic; using System.Windows.Forms; namespace GrahamScanTest { public partial class Form1 : Form { ..

쿼드트리는 그림에서 볼 수 있듯이 2차원(3차원) 맵을 4등분으로 나누어 트리형태로 관리하는 자료구조를 뜻합니다. 이것은 왜 필요할까요? 3차원상에 객체를 그리는 일은 간단하면서도 오래걸리는 작업입니다. 특히 광활한 맵을 그리거나 많은 객체를 그린다면 그거 나름대로 어쩔 수 없는 일이지만, 사용자 눈(PC 모니터)에 보이지 않는 영역까지 그리는데 자원을 사용한다면 비효율적입니다. 그렇다면 맵에 관하여 사용자 눈에 보이는 영역을 어떻게 구분할 것이며(절두체) 구분한 영역을 어떻게 계산하는 걸까요? 답은 "쿼드트리" 를 사용합니다. 절두체에 관한 내용은 다음에 다루기로 하고, 영역을 계산하는 것에 있어서는 위 {x} 트리구조를 따르면 됩니다. 처음은 광활한 맵을 4등분하여 쿼드트리 구조로 담아놓고 쿼드트리의..

a* search는 최단경로 검색 알고리즘이라 생각하면 된다.다만, 기존의 kruskal과 같은 탐색 알고리즘과는 달리 경로에 장애물이 있을 경우를 고려하는게 차이점이다. 초기조건은 탐색 영역을 사각형으로 나눈다. 초록색이 시작위치,파란색이 장애물,빨간색이 도착위치일 경우 아래와 같은 흐름으로 탐색이 진행된다. A. 현재 위치와 이동 위치와의 간선차 = GB. 이동 위치와 도착 위치와의 간선차(직선일 경우 멘하탄방법임) = HC. 갱신 거리값은 G + H로 계산된다. 1) 자신의 위치에서 주변(9방향)의 사각형 위치로 이동한다는 가정하에 총 간선값을 계산한다.2) 이동이 가능할 경우 스택에 쌓는다.3) 스택에서 가장 짧은 간선을 가진 사각형으로 이동 후 다시 주변(9방향)으로 간선값을 갱신한다.4) 현재..

function Rect2Rect (RECT, RECT2)for j=1,4,1 dofor i=1,2,1 dolocal d1 = {x=RECT[1+i].x-RECT[1].x,y=RECT[1+i].y-RECT[1].y}local d2 = {x=RECT[2+i].x-RECT[1].x,y=RECT[2+i].y-RECT[1].y}local p = {x=RECT2[j].x-RECT[1].x,y=RECT2[j].y-RECT[1].y}t2 = (p.x*d1.y-p.y*d1.x)/(d2.x*d1.y-d2.y*d1.x)t1 = (p.x-t2*d2.x)/d1.xif t1>=0 and t1=0 and t2=0 and t1+t2 0 and ub < 1 thenComposition = Composition + 1endendend..

아래 알고리즘을 사용해서 급하게 짜봤다.function Rect2Rect (RECT, RECT2)for j=1,4,1 dofor i=1,2,1 dolocal d1 = {x=RECT[1+i].x-RECT[1].x,y=RECT[1+i].y-RECT[1].y}local d2 = {x=RECT[2+i].x-RECT[1].x,y=RECT[2+i].y-RECT[1].y}local p = {x=RECT2[j].x-RECT[1].x,y=RECT2[j].y-RECT[1].y}t2 = (p.x*d1.y-p.y*d1.x)/(d2.x*d1.y-d2.y*d1.x)t1 = (p.x-t2*d2.x)/d1.xif t1>=0 and t1=0 and t2=0 and t1+t2

오랫만에 글을 쓰게됬다.이번에 스터디까페를 만들면서 글을 병행하며 쓰고 있다.http://cafe.naver.com/cse2study 이번 알고리즘은 기존의 AABB의 단점인 직각사각형(그것도 수직, 수평인 사각형)에만 적용되는 단점을 보완하고자OBB 모든 다각형에 대해 다각형2다각형의 충돌영역을 검출하고자 하였다. 처음으로 다각형2점 을 선별하기 위해 요즘 공부하고 있는 LUA로 코드를 짜봤다. RECT = {{x=10,y=10},{x=15,y=25},{x=20,y=5},{x=25,y=20}}P = {x=15,y=15}isInner = false for i=1,2,1 dolocal d1 = {x=RECT[1+i].x-RECT[1].x,y=RECT[1+i].y-RECT[1].y}local d2 = {x=..

void CTest2View::DrawImage(CDC* pDC){CTest2Doc* doc = GetDocument();CRect cr = doc->LoadArray(); CPen pen,pen2,pen3, *pOldPen;pen.CreatePen(PS_DOT, 1, RGB(255,255,255));pen2.CreatePen(PS_DOT, 1, RGB(0,0,0));pen3.CreatePen(PS_SOLID, 1, RGB(0,0,0)); CBrush Brush, *pOldBrush;pOldBrush = (CBrush *)pDC->SelectStockObject(NULL_BRUSH); if(plag){pDC->SetROP2(R2_NOT); pOldPen = (CPen *)pDC->SelectObject(..