Linked List연결 리스트는 각 노드가 선형적으로 연결되어 있는 자료구조를 말한다.특징맨 처음 삽입한 노드의 주소를 가진다.각각의 노드는 데이터와 다음 노드의 주소를 가진다.데이터가 추가될 때마다 새로운 노드를 할당한다. -> 노드끼리의 메모리는 불연속적이다.요소의 삭제와 추가는 O(1)이며, 특정 원소 접근은 n이다.장점동적인 크기의 데이터를 다루기 좋다. 데이터를 삽입할 때마다 메모리를 추가로 할당하기 때문이다.일반 배열은 크기를 늘릴 수 없음동적배열(vector) 은 크기가 늘어날 때 재할당과 복사로 오버헤드 발생 O(n)각 요소 사이에 데이터를 추가하더라도 O(1)로 굉장히 빠르다.일반 배열과 동적배열은 해당 구역의 뒷부분을 한 칸씩 밀어서 공간을 만들어 내며 오버헤드가 발생 O(n)단점각 ..

Quick sort일정한 기준(pivot)에 따라서 큰 값과 작은 값으로 나누는 것의 반복으로 정렬.시간 복잡도는 nlogn이다. 하지만 최악의 경우 (pivot이 가장 크거나 작다면) n^2이 되어버린다.구현보통은 재귀를 이용하여 구현한다.사용자가 설정한 특정 값을 기준으로 그 값보다 더 큰값과 더 작은 값으로 나누는 과정을 반복한다.이때, 특정한 값의 경우는 사용자의 맘. -> 보통은 가장 왼쪽의 값으로 한다.1. 초기상태. pivot 값과 store 값 모두 left로 설정. store에서는 pivot보다 작은 값을 가진 idx의 최대값. store번째 까지는 pivot 보다 작은 값. store 이후에는 더 큰값이 들어감.2. left+1, right까지 탐색.3. arr[pivot] > a..

heap힙은 주어진 데이터들 중에서 특정 기준에 부합하는 '최대' 혹은 '최소'를 빠르게 찾아낼 수 있는 자료구조이다.힙은 완전이진트리 를 기반으로 한다. 완전이진트리란 하나의 부모당 자식이 최대 2개까지만 존재하는 트리중에서 왼쪽부터 차례대로 삽입된 형태를 가진 트리를 말한다.부모노드의 값이 자식노드 보다 클때는 "최대힙" 작은 때에는 "최소힙"이라고 부른다. 힙에서는 "형제노드" 간의 관계는 존재하지 않는다. 오로지 자식노드만을 비교한다.즉, 최대힙을 가정했을 때, 트리의 가장 꼭대기 층에 있는 추트노의 값이 트리에 존재하는 값들 중 가장 큰 값이다.힙의 장점기본적인 정렬은 nlogn이다. 따라서 전체 어레이값들에 대해서 작은 값부터 하나씩 가져온다면, nlogn이 필요하다. 힙을 사용하다해도 삽입에..