class Node{ constructor(val){ this.val = val; this.next = null; this.prev = null; } } class DoublyLinkedList { constructor(){ this.head = null; this.tail = null; this.length = 0; } push(val){ var newNode = new Node(val); if(this.length === 0){ this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; newNode.prev = this.tail; this.tail = newNode; } this.length++; return this; ..

연결 리스트는 인덱스가 없이 단지 다음 노드들을 가리키고 있는 수많은 노드들이다. 배열과는 다르다. 엘리베이터가 없는 고층 빌딩과 같다. 단방향으로 연결 되어있기 때문에 다음 노드로 데이터를 읽는 게 가능하고 역방향은 안된다. 삽입과 제거가 쉽다. head와 tail을 지정해줘야한다. 1. push, pop, shift, unshift, insert, remove, reverse, get, set class Node{ constructor(val){ this.val = val; this.next = null; } } class SinglyLinkedList{ constructor(){ this.head = null; this.tail = null; this.length = 0; } push(val){ v..

1. 합병 정렬(Merge Sort) 분할, 정렬, 합병 3가지가 모두 일어난다. 배열을 더 작은 배열로 나누는 방식. 0개 또는 1개로 구성된 배열이 될 때까지 나눈 다음 다시 합치면서 정렬을 한다. 합병 정렬은 재귀를 쓴다. slice를 재귀로 사용해 0,1개의 요소가 남을 때까지 작게 쪼갠다. 이후 합병 함수를 사용해 다시 합친다. 시간 복잡도는 O(nlogn), 공간 복잡도는 O(n) function merge(arr1, arr2){ //두 개의 배열을 정렬할 때, 합병 정렬의 한 부분 let results = []; let i = 0; let j = 0; while(i arr..

정렬 알고리즘은 재배열하는 것. 아래 3가지의 정렬을 데이터의 크기가 작을 때 유용하다. 1. 버블 정렬 그다지 효율적이지 않고 잘 쓰이지 않는다. 해당 인덱스와 다음 인덱스의 크기를 비교하면서 정렬을 한다. 가장 큰 값이나 가장 작은 값을 하나씩 맞춰가는 것. 이를 반복하면서 정렬을 한다. 하나씩 값이 고정되기 때문에 정렬해야 하는 항목의 수가 감소한다. 시간 복잡도는 O(n) ~ O(n^2) function bubbleSort(arr){ var noSwaps; // 최적화를 위해 변수 선언 for(var i = arr.length; i > 0; i--){ //가장 우측의 값을 정하니 인덱스가 하나씩 줄어듦 noSwaps = true; for(var j = 0; j < i - 1; j++){ if(ar..

1. 선형 탐색 처음부터 끝까지 혹은 끝부분부터 처음까지 하나씩 돌면서 검색하는 것 (indexOf, includes, find, findIndex 등등...) 시간 복잡도는 O(n)이다. for루프 한 개. 2. 이진 탐색 이진 탐색의 경우 확인을 할 때마다 남은 항목의 절반을 없앨 수 있다. 정렬이 되어 있어야 한다. (ex. 가장 작은 수 ~ 가장 큰 수) //가장 중요!! 시간 복잡도는 O(1)~O(logn)이다. 중간 지점 기준으로 찾는다. 중간 지점보다 크다면 중간 오른쪽. 거기서 또 새로운 중간 지점을 찾으면서 반복한다. function binarySearch(arr, val) { let start = 0; let end = arr.length - 1; let middle = Math.flo..