Dev.Basic/자료구조&알고리즘 (11) 썸네일형 리스트형 [Sorting] 1. Insertion Sort (삽입 정렬) / Bubble Sort (버블 정렬) 1. Insertion Sort Space-Complexity = In-place sort : O(1)의 보조 메모리를 사용한다. Time-Complexity = O(n^2) 원리n개의 원소를 가진 배열을 정렬할 때, i번째를 정렬할 순서라고 가정하면, 0부터 i-1까지의 원소들은 정렬되어있다는 가정하에, i번째 원소와 i-1번째 원소부터 0번째 원소까지 비교하면서 i번째 원소가 비교하는 원소보다 클 경우 서로의 위치를 바꾸고, 작을 경우 위치를 바꾸지 않고 다음 순서(i+1)의 원소와 비교하면서 정렬해준다. 이 과정을 정렬하려는 배열의 마지막 원소까지 반복해준다. c code>1234567891011121314151617//Insertion Sortvoid insertion_sort(int * arr,.. [DataStructure] 2. 자료구조 기본 - Heap(Max heap, Min heap)에 대해서 Heap 자료구조자료구조의 일종으로 Tree의 형식을 하고 있으며, Tree 중에서도 배열에 기반한 Complete Binary Tree 이다. 배열에 트리의 값들을 넣어줄 때, 0번째는 건너뛰고 1부터 루트노드가 시작된다. 이는 노드의 고유번호 값과 배열의 index를 일치시켜 혼동을 줄이기 위함이다. 힙에는 최소힙(min heap), 최대힙(max heap) 두 종류가 있다. Max Heap이란, 각 노드의 값이 children 의 값보다 크거나 같은 complete binary tree를 말한다. ( min heap은 그 반대이다. ) Max heap에서는 Root node에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 time complextiry이 O(1)이다. 그리고 complet.. [DataStructure] 1. 자료구조 기본 - Array, Linked List, Stack, Queue, Tree 1. 자료구조 기본 - 기본적인 자료구조 종류선형 자료 구조Array vs Linked List가장 기본적인 자료구조인 Array 자료구조는, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스로 해당 원소에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 즉 random access가 가능하다는 장점이 있는 것이다. 하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤, 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift.. 이전 1 2 다음
