DataStructure & Algorithm4 정렬 알고리즘 - Merge Sort 병합 정렬 이란? 배열을 절반씩 계속 잘라서 가장 작은 조각들을 기준으로 정령, 병합하는 방식 장점 데이터분포에 상관없이 시간 복잡도는 O(nolog2n)으로 동일하다 레코드를 연결리스트(Linked List)로 구성하면, 링크 인덱스만 변경되기 때문에 데이터의 이동에 필요한 리소스는 작아진다. 따라서 연결리스트를 정렬할때는 Linked List 자료형을 사용하는 것이 좋다. 단점 배열로 구성하게 되면 임시 배열이 필요하다. 레코드의 크기가 큰 경우 이동횟수가 많으므로 시간정 낭비를 초래한다. 2021. 12. 30. 정렬알고리즘 - Quick Sort 퀵소트란? 특정한 값(pivot)을 기준으로 해당 값의 오른쪽은 큰값, 왼쪽은 작거나 같은 값으로 정렬 일반적으로 물리적으로 중간에 있는 값을 지정한다. (배열 크기 / 2) 정렬하는 방법은 아래의 과정을 반복한다. 시작의 값 (Left Pointer)과 Pivot값을 비교하여 Left > Pivot 이 나올때까지 Left Pointer++ 끝의 값 (Right Pointer)과 Pivot값을 비교하여 Pivot >= Right 이 나올때까지 Right Pointer-- Left Pointer에 있는 값과 Right Pointer에 있는 값을 바꿔준다. Left Pointer > Right Pointer가 될때까지 반복한다. 위 과정을 모두 정렬이 될때까지 반복하면되는데 백번 강의 듣는거보다 코드 한번 .. 2021. 12. 26. Heap Heap이란 최대값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 최소힙이란? 작은 값을 항상 위에 있게하여 트리의 루트에는 가장 작은값이 오도록 함. 최대힙이란? 큰값을 항상 위에 있게하여 트리의 루트에 가장 큰 값이 오도록 함. 최소힙에 노드 삽입하기 완전 이진트리에 값을 추가 하듯이 마지막 leaf에 값을 추가 추가한값과 부모노드를 비교해서 자기보다 값이 작은 경우 자리 변경 루트에 도착하거나 자기보다 값이 작은 부모를 만나기 전까지 반복 최소힙은 부모노드와 비교할때마다 전체 값의 절반이 사라지기 때문에 O(log n)의 시간 복잡도를 가진다 최소힙에서 노드 꺼내오기 최소힙에 최솟값을 요청할때 루트의 값을 빼온 다음에는 마지막 하위 노드의 값을 가져와 루트.. 2021. 12. 18. Hash Hash란? Key / Value 시스템 데이터를 관리/유지하는 자료구조 리소스 해시함수의 규칙 (ex. /100)으로 분류 -> 인덱스 >> 일련의 과정을 "해싱"이라고 부른다. Hash 관련 용어 정리 해시테이블 : 데이터가 저장되는 장소이며 인덱스와 해시값으로 분류 인덱스(키) / 인덱스 컬럼 내에 있는 값은 버켓 해시값(밸류) / 해시값 컬럼 내에 있는 값은 엔트리 Hash의 특징 선형탐색(Array)은 O(n)의 시간 복잡도를 가지는 반면, Hash Table은 O(1)의 시간 복잡도를 가진다. 선형탐색과 같은 Array구조를 가지고 있는 Hash Table이 검색속도가 더 빠른 이유는 인덱스를 바로 찾아가기 때문인데 인덱스를.. 2021. 12. 7. 이전 1 다음
