프로그래밍/알고리즘
-
[알고리즘] KD 트리 , KDB 트리프로그래밍/알고리즘 2019. 4. 30. 10:26
개념 이진검색트리를 확장한 것으로 두개 이상의 key 를 사용합니다. 다른 말로 다차원 검색트리로 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기합니다. 현재 그림은 두개의 key 를 갖고있는 KD 트리이다. 왼쪽 key 를 x, 오른쪽 key 를 y 라고 생각 한다면 깊이 1 위치에 A 에서는 처음에 x 를 기준으로 작으면 왼쪽 크면 오른쪽으로 분리한다. 그리고 깊이 2 위치에 B,C 에서는 y 의 값을 기준으로 깊이 3 에서는 x의 값을 기준으로 삽입을 한다. 삭제 1. 자식이 없는 경우 : 노드만 제거 2. 자식이 하나뿐인 경우 : 자식이 둘인 경우와 같이 해결 : 왼쪽 자식만 있는경우, 왼쪽 서브트리 중 노드 r에서의 분기에 사용한 필드 값이 가장 큰 노드를 찾아서 이동 3. ..
-
[알고리즘] B 트리프로그래밍/알고리즘 2019. 4. 29. 16:44
기본개념 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 쉽게 말해서 키를 다수 보유하고 있는 트리라고 할 수 있다. B-트리의 조건 모든 단말노드는 동일한 높이를 가진다. 각 내부노드의 자식노드는 M/2 이상 M 이하이다. (M은 2보다 큰 정수로서 트리노드의 최대 자식 수) 루트의 자식 수는 두개 이상이다. ...더보기 우리는 트리의 높이를 최소화 하기 위해 자가균형트리를 배웠다. (레드블랙트리, AVL 트리) B트리는 키의 갯수를 증가시켜 트리의 좌우를 넓히는 방법으로 높이를 낮췄다고 생각하면 도움이 될것이다. 탐색 B트리는 이진트리와 마찬가지로 중위순..
-
[알고리즘] 레드-블랙트리(Red-BlackTree) -Insert프로그래밍/알고리즘 2019. 4. 8. 23:20
이진탐색트리(BST)를 기반으로 구성된 자료구조입니다. BST의 설명은 여기에 있습니다. 따라서 BST의 설명은 본 게시물에서는 하지 않습니다. 개념설명 : 우선 이진탐색트리를 잠깐 봅시다. 이진탐색트리는 Search, Insert, Delete 가 가능한 이진트리였습니다. 이때, 평균 시간복잡도는 O(log n) 이였죠. 하ㄴ지만 이진트리가 극단적으로 편향됬을때시간복잡도는 O(N) 이 됩니다. 이건 이진트리의 깊이(h) 많큼 탐색을 한다는 의미입니다. 이러한 문제들을 해결하기 위해 나온 것이 바로 레드-블랙트리(Red-BlackTree) 입니다. 다른 말로 Balanced Binary Search Tree 라고도 합니다. 이유는 이진탐색트리의 깊이를 항상 log N 으로 유지시켜주기 때문입니다. 따라서..
-
[알고리즘] 이진탐색트리(BST)프로그래밍/알고리즘 2019. 4. 7. 16:11
이진탐색트리(BST)는 링크드리스트를 기반으로 한 탐색 알고리즘입니다.그래서 링크드리스트를 모르시면 꼭! 자료구조를 통해 공부를 하시고 읽으시길 바랍니다. 본 게시물이선 BST에 대해서만 설명합니다. 이해 순서 포인터를 정확히 이해한다. 링크드리스트를 이해한다. 완전 이진트리를 이해한다. 이진 탐색트리를 이해한다. 이진탐색트리(BST) 란 ? : 방탄소년단(BST) ? 죄송합니다. 이진탐색트리는 이진탐색(Binary Search)와 연결리스트(Linked List)를 결합한 자료구조의 일종입니다. 이진탐색은 탐색에 필요한 시간복잡도가 O(logN)으로 빠르지만 자료 입력과 삭제가 불가능합니다. 연결리스트의 경우는 입력과 삭제의 시간복잡도가 O(1)로 빠르지만 탐색하는 시간복잡도는 O(n)으로 매우 비효율..
-
[알고리즘] 힙정렬(Heap sort)프로그래밍/알고리즘 2019. 3. 28. 15:41
알고리즘 힙정렬(Heap sort) 힙 정렬은 트리 구조를 이용하기 때문에 이해하는데 가장 오랜시간이 걸렸어요. 저는 자료구조를 배우지 않은 상태에서 알고리즘을 시작했거든요. 그래서 이번엔 저 처럼 자료구조를 배우지 않고 알고리즘을 먼저 시작한 사람들을 대상으로 설명할 예정입니다. 이해 순서 1. 트리의 구조를 이해한다. 2. 이진 트리를 이해한다. 3. 완전 이진 트리를 이해한다. 4. 최대힙과 최소힙을 이해한다. 5. 힙정렬을 이해한다. 주의 : 1 ~ 4 과정은 자료구조 게시판에 자세히 올릴 예정이므로 간단하게 설명하겠습니다. 트리 구조란 ? : 나무의 뿌리(root) , 줄기(trunk), 잎(leaf) 처럼 특정한 관계를 갖고 있는 자료들을 의미합니다. 그림을 보면 마치 뒤집어 놓은 나무처럼 보..
-
[알고리즘] 퀵정렬(Quick sort)프로그래밍/알고리즘 2019. 3. 28. 15:37
알고리즘 퀵정렬(Quick sort) 간단 요약 1. 임의의 값을 피벗(Pivot) 으로 정한다. 2. 피벗을 기준으로 하나씩 비교하여 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 정리한다. 3. 피벗을 기준으로 왼쪽 과 오른쪽의 배열을 비균등 분할을 한다. 4. 각각의 배열에서 순환 호출을 통해 더 이상 분할되지 않을 때 까지 반복 상세 설명 병합 정렬은 분할, 정복, 결합 세단계의 과정을 거쳐서 완성된다. 분할 : 피벗을 기준으로 비균등 분할 정복 : 각 배열의 크기가 더 이상 분할 할 수 없을 때 까지 순환 호출을 통해 분할을 반복한다. 결합 : 한회의 분할,정복이 끝날 때 마다 최소 하나이상의 피벗값이 생긴다. -> 각 회마다 결정되는 피벗값의 위치는 정렬이 완성되었을때의 위치와 같기 때문에 각..
-
[알고리즘] 병합정렬(Merge sort)프로그래밍/알고리즘 2019. 3. 27. 17:03
알고리즘 병합정렬(Merge sort) 간단 요약 가정) Array[8]= { 20, 18, 50, 40, 9, 19, 5, 25 } 을 오름차순으로 정렬한다. 1. 배열을 반으로 분할 2. 반으로 나누어진 배열들을 다시 반으로 분할한다. 3. 각각의 배열의 인덱스가 하나만 남을 때까지 분할 4. 하나씩 남은 배열들을 빈배열에 오름차순으로 합친다. -> 병합정렬은 이해하기 까다로울수 있다. 복잡하지만 이렇게 하는 이유는 시간복잡도를 줄이기 위해서 이다. 예를 들어 n*n 의 시간복잡도를 갖고 있다고 하자 10개 의 배열을 정렬하는데 걸리는 시간은 100 이된다. 하지만 반으로 쪼개서 5개씩 정렬후 합치는 작업을 한다면 25 + 25 = 50 이라는 시간이 걸린다. 이런 부분에서 분할정복이 강함을 알 수 ..
-
[알고리즘] 버블정렬(Bubble sort)프로그래밍/알고리즘 2019. 3. 27. 00:50
알고리즘 버블정렬(Bubble sort) 간단 요약 가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다. 특징) 선택정렬은 앞에서 부터 작은수를 정렬시키지만 버블정렬은 뒤에서 부터 큰수를 정렬시킨다. 1. 첫번째 데이터 15와 두번째 데이터 11을 비교한다. 2. 15가 더 크기 때문에 서로 자리를 바꿔준다. 3. 다시 한칸 앞으로 이동해서 두번째 15 와 1을 비교한다. (2번에서 15가 두번째 데이터로 이동한상태) 4. 이번에도 15가 더 크기 때문에 서로 자리를 바꾼다. (현재 상태 { 11, 1, 15, 3, 8 } ) 5. 1회차가 끝나면 { 11, 1, 3, 8, 15 } 형태가 되고 최대값이 마지막 배열에 위치한다. 6. n 번 반복 상세 설명 가정) Arr..