체셔's blog

자료구조 카테고리를 만들까 하다가 알고리즘 카테고리에 작성합니다. 쿼드트리란? 트리 자료구조중 하나로 부모 노드 아래에 자식 노드를 4개(Quad)씩 가지고 있는 트리입니다. 이미지 용량, 충돌, 컬링 등 다양한 곳에서 최적화 기법으로 사용되고 있습니다. 알고리즘 오늘은 쿼드트리를 이용해 흑백 이미지를 간단하게 압축해보도록 하겠습니다.검은색을 0, 흰색을 1로 한다면 왼쪽 이미지는 오른쪽과 같이 나타낼 수 있습니다. 0000111100001111000000110000001111110001111111111111111111111110 해당 이미지를 쿼드트리를 이용해 압축을 하면 결과는 이렇게 나옵니다.(0(1101)1((0011)(0111)1(1110)) 그림으로 보신다면 왼쪽과 같은 형태로 압축하는 것입니..

참고 : www.dyn4j.org/2010/01/sat/ 분할 축 정리(Separating Axis Theorem)란? 분할축 정리(Separating Axis Theorem, 이하 SAT)란 "두 물체를 투영한 구간이 겹치지 않는 축이 하나라도 존재한다면 두 물체는 교차하지 않은 상태이다."라는 명제에 관한 정리입니다. 그리고 이것을 통해 충돌을 검출해내는 알고리즘을 만들것입니다. 충돌 유무, 충돌 위치, 충돌 량을 검출하며 2D물리 시뮬레이션에서 일반적으로 사용하게 됩니다. (http://chessire.tistory.com/entry/%EC%84%A0%EB%B6%84%EA%B3%BC-%EC%84%A0%EB%B6%84%EC%9D%98-%EC%B6%A9%EB%8F%8C-%EC%A0%95%EB%A6%AC..

(원래 기준점은 최하단 왼쪽 점을 고르게 되지만 PIXI는 DirectX처럼 y최소값이 상단에 위치합니다.) Graham scan이란? Graham scan이란 유한개의 점 중 다른 점을 가둘 수 있는 외곽점을 찾는 알고리즘 중 하나입니다. 이 외곽점을 이으면 볼록 껍질(Convex hull)이 됩니다. 시간 복잡도는 입니다. 알고리즘y 값이 가장 작은 점을 찾습니다.(만약 여러 개 존재시 x값이 가장 작은 점을 선택합니다.) 이 때, 이 점을 P0이라 부르겠습니다.P0을 기준으로 다른 모든 점의 각도를 구하여 각도가 작은 순서대로 정렬합니다.P0과 정렬된 점을 2개를 Convex hull에 추가합니다.그 다음 점부터 다음 조건을 반복하여 수행합니다.Convex hull의 마지막 직선에서 현재 점이 왼쪽..

참고 - https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 소스코드 사용하실 때, 댓글을 남겨주세요. 정의 힙은 2진 힙(바이너리 힙)이라고도 부르며 최댓값과 최솟값 찾기 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조로써 다음과 같은 힙 속성(property)을 만족합니다. - A가 B의부모노드(parent node)이면 A의 키(key)값과 B의 키 값 사이에는 대소관계가 성립한다. 최대 힙 - 부모노드의 키값이 자식 노드의 키값보다 항상 큰 힙 최소 힙 - 부모노드의 키값이 자식 노드의 키값보다 항상 작은 힙 형제 사이에는 대소관계가 정해지지 않습니다. (Max heap 이미지입니다.) ..

Javascript로 구현한 Hanoi tower 하노이 탑은 세개의 기둥과 n개의 크기가 다른 원판이 크기가 큰 순서대로 첫번째 기둥에 꽂혀있습니다. 그리고 다음의 규칙에 맞게 세번째 기둥에 옮기면 되는 퍼즐의 일종이다.첫번째, 한번에 하나의 원판을 옮길 수 있다.두번째, 크기가 작은 원판 위에 큰 원판이 올 수 없다. 원판이 n개일 때, 번 이동하게 됩니다.하노이 탑 설화인도 베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓..

Javascript로 구현한 Merge sort 오늘은 분할 정복 알고리즘의 기초인 MergeSort에 대해 알아보겠습니다.MergeSort는 원소의 개수가 1개가 될때까지 나눈 후, 역순으로 2개의 그룹을 병합 정렬해 가는 알고리즘입니다. 시간 복잡도는 로 원소들의 상태에 영향을 받지 않고 안정적으로 정렬하며 정렬 전의 순서와 정렬 후의 순서가 동일함을 보장하는 stable sort입니다. 하지만 원소 개수만큼의 임시 배열을 만들어 줘야하는 단점이 있습니다. 오늘은 동영상으로 어떻게 병합정렬이 진행되는지 봅시다. 재귀로 작성한 코드 123456789101112MergeSort.prototype.mergeSort = function(first, last){ if(first 대그룹 정렬위에 보이는 동영상처..

Javascript로 구현한 Select sort 주어진 배열 이외에 다른 저장공간을 필요로 하지 않는 제자리 정렬 알고리즘의 하나로 시간 복잡도는 입니다. 어떤 상황에서든 에 비례하는 시간이 걸립니다. 1 5 6 8 7 4 3 9 2 1 5 6 8 7 4 3 9 21 2 6 8 7 4 3 9 5 1 2 6 8 7 4 3 9 51 2 3 8 7 4 6 9 5 1 2 3 8 7 4 6 9 51 2 3 4 7 8 6 9 5 1 2 3 4 7 8 6 9 51 2 3 4 5 8 6 9 7 1 2 3 4 5 8 6 9 71 2 3 4 5 6 8 9 7 1 2 3 4 5 6 8 9 71 2 3 4 5 6 7 9 8 1 2 3 4 5 6 7 9 81 2 3 4 5 6 7 8 9 소스코드12345678910111213..

Javascript로 구현한 Bubble sort 거품 정렬이란? 인접한 두 원소를 비교하여 정렬하는 방법입니다. 거품이 수면위로 떠오르는 것 처럼 보여서 붙혀진 이름이라고 합니다. 시간 복잡도는 입니다. 예시 1 5 6 8 7 4 3 9 2 1 5 6 8 7 4 3 9 21 5 6 8 7 4 3 9 21 5 6 8 7 4 3 9 21 5 6 8 7 4 3 9 21 5 6 7 8 4 3 9 2 1 5 6 7 8 4 3 9 21 5 6 7 4 8 3 9 21 5 6 7 4 8 3 9 2 1 5 6 7 4 3 8 9 2 1 5 6 7 4 3 8 9 2 1 5 6 7 4 3 8 9 2 1 5 6 7 4 3 8 2 9 첫번째 이터레이션 종료 1 5 6 7 4 3 8 2 9 1 5 6 7 4 3 8 2 9 1 5..

Javascript로 구현한 선분충돌 투영을 통한 선분충돌1번2번하지만 2번 이미지에서 초록 선분도 투영 결과는 같지만 충돌하지는 않은 상태입니다. 그렇기 때문에 파랑 선분의 직교 벡터에도 똑같이 투영을 하여 같은 결과가 나오는지 확인해주어야 합니다. 3번3번 이미지는 파랑 선분의 직교 벡터인 파랑 직교 벡터에 투영을 한 결과입니다. 보라 선분은 아까와 같은 결과이지만 초록 선분은 그렇지 않습니다. 예외 : 두 선분의 벡터가 같은 방향을 가지고 있을 때,4번 4번 이미지는 두 선분의 벡터가 같은 방향을 가지고 있을 때를 보여주는 이미지입니다. 해당 경우에는 직교 벡터에서 한 점에 투영이 됩니다. 이 경우에는 선분의 벡터에 투영하여 빨강 선분의 각 점 중 하나라도 파랑 선분의 사이에 있다면 충돌 된 것입니..