두번째 자료부터 시작, 그 앞 자료들과 비교하여 삽입 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘 def insertionSort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and key < arr[j]: arr[j+1] = arr[j] j -= 1 arr[j+1] = key 시간복잡도 최선: O(n), 평균/최악: O(n^2) 공간복잡도 O(n) 장점 단순 이미 정렬되어 있을 경우 효율적 제자리 정렬 안정 정렬 단점 비효율적 배열의 길이가 길어질수록 비효율적 References https://github.com/GimunLee/tech-refrigerator/blob/master..
자료구조 알고리즘/이론
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 최소값을 찾고 위치 값과 교환. 나머지도 같은 방법으로 교체. A = [64, 25, 12, 22, 11] for i in range(len(A)): min_idx = i for j in range(i+1, len(A)): if A[min_idx] > A[j]: min_idx = j A[i], A[min_idx] = A[min_idx], A[i] 시간복잡도 O(n^2) 공간복잡도 O(n), swap을 주어진 배열 안에서 수행 장점 단순한 알고리즘 제자리 정렬(in-place sorting) 정렬을 위한 비교횟수는 많으나 bubble sort에 비해 실제 교환횟수는 적음 단점 비효율적. 시간 복잡도 O(n^2) 불안정..
서로 인접한 두 원소의 대소를 비교, 조건에 맞지 않으면 자리를 교환하며 정렬하는 알고리즘 void bubbleSort(int arr[], int n) { int i, j; for(i = 0; i arr[j+1]) swap(arr[j], arr[j+1]); def bubbleSort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[i] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] 시간복잡도 모두 O(n^2) 공간복잡도 O(n), 주어진 배열 안에서 swap 사용으로 장점 구현 간단, 직..
B-Tree의 노드의 추가적인 생성관 연산을 최소화하기 위해 삽입, 삭제 시 발생하는 노드 분리를 줄이려고 고안됨 노드가 가득찰 경우 분열 대신 형제 노드로 재배치 정렬되어있고 중복 X 모든 leaf node는 같은 레벨 root node는 leaf node가 아닌 경우 적어도 2개 이상의 자식 노드를 가짐 root node, leaf node 가 아닌 내부 노드는 2((M-2)/3) + 1 ~ M 개의 자식 노드를 가지고 있음 References https://ssocoit.tistory.com/217 [자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree 위 글을 보고 정리를 하지 않을 수 없었습니다. 가슴이 시키네요;; 그렇다면 바로 B-Tree, B*Tree, B+Tree의 특징에 ..
같은 레벨의 모든 키값들이 정렬됨 같은 레벨의 sibling node는 연결리스트 형태로 연결되어있음 모든 leaf node는 연결리스트로 연결되어 있음 키값 중복 X, 탐색 유리 블럭 사이즈를 더 많이 이동할 수 있음(key 값에 대한 하드디스크 주소 X) 그러나 무조건 leaf node 까지 내려가야함 삽입, 삭제 모두 leaf node에서 이루어짐 모든 leaf node는 같은 레벨 leaf node가 아닌 node의 키 값의 수는 그 노드의 서브트리수-1 단말 노드 비단말 노드 인덱스 노드 : leaf node가 아닌 자료, value값에 다음 노드를 가리키는 포인터 주소 존재 데이터 노드 : lead node 자료, value값에 데이터가 존재 References https://ssocoit.t..
정렬된 균형이진트리 하나의 노드에 많은 정보를 가지거나, 두 개 이상의 자식을 가질 수 있음 중복없음 모든 leaf node는 같은 레벨에 있음 root node는 자신이 leaf node가 아닌 이상 최소 2개 이상의 자식을 가짐 내부 노드(root, leaf node 이외) M/2 ~ M개의 자식을 가짐 노드는 M/2 - 1 ~ M - 1 개의 데이터(키)가 포함될 수 있음 자식 수의 하한값이 t, M = 2t - 1 데이터가 k, 자식 노드의 수는 k+1 검색은 O(logn) 구조 유지를 위해 추가적인 연산이 수행되거나 새로운 노드를 생성함 -> 최소화를 위해 B*Tree 등장 탐색을 위해서 노드를 찾아서 이동해야함 -> 해소를 위해 B+Tree 등장 아래의 조건 위반 시 재구조화 내부노드는 M/2..
모든 노드는 RED or BLACK root 와 leaf(NIL)은 BLACK 노드가 RED이면 자식은 모두 BLACK (No Double Red) 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 BLACK 노드를 포함 NIL을 하나의 객체로 고나리하면 하나의 노드로 관리하기에 메모리 절야 까능 삽입 시 연속된 RED 해결 Recoloring: 삽입된 노드의 부모의 형제 색깔이 RED Restructing : 삽입된 노드의 부모의 형제 색깔이 BLACK인 경우, NULL인 경우 삭제 시 RED는 그냥 삭제 BLACK의 경우 삭제 연산으로 트리 속성을 깨지 않도록 복잡도 Space : O(n) 삽입, 삭제, 검색 : O(logn) AVL vs RB 검색 : AVL > RB (AVL가 ..
Binary Search Tree의 속성을 가짐 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 삽입, 삭제, 검색 시 시간복잡도는 O(logN), N은 노드의 개수 Node는 key, left node pointer, right node pointer, height 로 구성 Balance Factor 균형을 파악할 때 활용 BF(k) = k의 왼쪽 서브트리의 높이 - k의 오른쪽 서브트리의 높이 (-1, 0, 1 중 하나) Rotation RR, Right Rotation : 회전의 기준이 되는 노드가 오른쪽으로 감. LR, Left Rotation : 회전의 기준이 되는 노드가 왼쪽으로 감. Case LL(Left Left) Case : 중심 노드를 기준으로 왼쪽에 노드가 깊이 있는 경우 -> RR을..
