띵동

연결 리스트란 자바스크립트 내장 array처럼 문자열, 숫자 등 원하는 데이터를 저장하는 자료구조이다. array와의 차이점은 인덱스 유/무이다. 연결 리스트는 인덱스가 없어 array처럼 인덱스를 통해 값에 접근할 수 없다. 연결 리스트는 다수의 노드들로 구성되고, 각 노드는 하나의 데이터 엘리먼트를 저장하는데 각 노드들은 next 포인터를 통해 연결되어 있다. 즉, 각 노드들은 next 포인터를 통해 다음 노드의 정보를 저장하고 있다. (다음 노드가 없다면 null 저장) 연결 리스트에서 중요한 것은 head, tail, length이다. head는 연결 리스트의 시작 노드, tail은 연결 리스트의 마지막 노드, length는 연결 리스트의 길이이다. head 노드가 어디 있는지 알면, 그 노드로 ..

퀵 정렬은 재귀를 통해 해결하기 가장 쉬운 방식 중 하나로 배열 길이가 0~1까지 분할하여 개별적으로 정렬되는 방식이다. 퀵 정렬은 pivot이라 부르는 단일 요소를 선택하여 수행하는 것이 특징으로, pivot보다 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 옮기는 과정 반복하며 정렬해 나아간다. 아래는 배열이 주어지면 pivot을 정해 배열 속 요소를 재배치하는 함수이다. 매개변수로 배열, 시작 인덱스, 끝 인덱스를 받으며 pivot idx를 반환해 준다. // 배열이 주어지면 요소를 pivot으로 지정하여 배열 속 요소를 재배치하는 함수 function pivot(arr, start=0, end=arr.length-1) { const swap = (arr, idx1, idx2) => { [arr[idx1..

합병 정렬은 분할 + 정렬 + 병합으로 이루어진 정렬로, 주어진 배열이 단일 요소가 될 때까지 분할한 후 정렬해 가며 합병한다. 합병 정렬은 분할, 합병으로 나눌 수 있는데 배열을 합칠 때는 주어진 배열이 정렬되어 있어야 한다. 즉, merge(arr1, arr2)가 있다면 각 arr1, arr2는 정렬되어 있어야 한다. 가장 먼저 합친 배열을 담을 빈 배열이 필요하다. 그리고 while문을 돌며 각 배열의 첫 번째 요소끼리 비교를 시작하며 arr1의 첫 번째 요소가 더 작다면 해당 요소를 빈 배열에 넣고 인덱스를 증가시킨다. 위 과정을 반복하여 배열을 합병시키는 것이다. function merge(arr1, arr2) { let result = []; let i=0, j=0; while(i < arr1..

삽입 정렬은 처음 요소가 정렬되어 있다고 가정하고, 그다음 요소와 비교하여 알맞은 자리에 삽입한다. 삽입 정렬에서 중요한 것은 첫 번째 값이 정렬되어 있다고 가정하여 두 번째 요소에서 시작하는 것이다. 두 번째 요소를 앞에 있는 값과 비교하여 교환이 필요하다면 swap 한다. function insertionSort(arr) { for (let i=1; i= 0 && arr[j] > currVal) { arr[j+1] = arr[j]; j--; } arr[j+1] = currVal; } return arr; } // while문 -> for문 function insertionSort(arr) { for (let i=1; i= 0 && arr[j] > currVal; j--) { arr[j+1] = arr..

선택 정렬은 가장 작은 값을 찾아 맨 앞에 위치하는 인덱스와 교환한다. 가장 작은 값을 찾는 게 루프 하나를 돈 것이고, 정렬된 데이터는 누적된다. 선택 정렬에서 중요한 점으로 3가지가 있다. - 최솟값 저장할 변수 생성 (처음에는 시작값에 대입) - 다음 항목과 비교해 가며 더 작은 값이 있다면 최솟값 변수에 저장 (실제값이 아닌 인덱스 값) - 루프 하나 돌면 시작 인덱스와 최솟값 인덱스 교환 선택 정렬과 버블 정렬의 차이점으로는 버블 정렬은 다음 원소와 비교하여 swap을 하며 진행하면서 가장 큰 값을 마지막으로 밀어내지만, 선택 정렬은 최솟값을 찾아 마지막에 교환한다는 것이다. function selectionSort(arr) { const swap = (arr, idx1, idx2) => { [..

버블 정렬은 오름차순 기준으로 정렬한다면 더 큰 숫자가 한 번에 하나씩 뒤로 가는 것이다. 루프를 돌면서 자신의 오른쪽 항목과 비교하고, 자신이 오른쪽 항목보다 크면 swap 하여 정렬한다. 그래서 루프 하나를 다 돌면 가장 큰 수가 오른쪽으로 정렬되어 반복할 때마다 정렬할 항목 줄어든다. 따라서 데이터가 거의 다 정렬된 상태에서 버블 정렬을 사용하면 좋다. 아래는 버블 정렬에서 가장 중요한 swap 코드이다. function swap (arr, idx1, idx2) { let tmp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = tmp; } // ES6 문법 구조 분해 할당을 사용해 교환 const swap = (arr, idx1, idx2) => { [arr[i..

선형 검색 (linear search) - 세트 간격으로 이동하면서 한 번에 하나의 항목을 확인하는 식으로 모든 항목 확인 - 자바스크립트에서 선형 검색 기능을 하는 메서드 => indexOf, includes, find, findIndex function linearSearch(arr, val) { for (let i=0; i left idx = 0, right idx = arr.length-1 (left < right 일 때만 실행) - 구하려는 수와 주어진 배열의 중간 인덱스 값을 비교하여 탐색 항목을 절반씩 줄여감 function binarySearch(arr, val) { let left = 0; let right = arr.length - 1; let mid = Math.floor((left+..