알고리즘
-
[알고리즘] 레드-블랙트리(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)으로 매우 비효율..
-
[알고리즘] 버블정렬(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..
-
[알고리즘] 선택정렬(Select sort)프로그래밍/알고리즘 2019. 3. 26. 20:46
알고리즘 선택정렬(Selection sort) 간단 요약 가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다. 1. 0번 부터 4번 데이터 중 최솟값을 찾아 0번 데이터와 스왑한다. 2. 1번 부터 4번 데이터 중 최솟값을 1번 데이터와 스왑한다. 3. n번 반복 상세 설명 가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다. 가장 먼저 전체 인덱스 중 최솟값을 찾는다. 최솟값 1을 첫번째 인덱스와 스왑한다. 그 다음 두번째에서 네번째 데이터 중 최솟값을 찾는다. 최솟값 3을 두번째 데이터 와 스왑한다. 여기까지 하면 두번째 데이터 까지 오름차순 정렬이 완성된다. 이렇게 n번 반복하면 오름차순 정렬이 완성된다 시간복잡도 코드 123456..