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..