CS/알고리즘

[ Javascript ] 계수정렬

개념 계수정렬은 굉장히 특이한 녀석이다. 똑같은 수가 많이 존재하는 배열을 정렬하는데 가장 좋다. 로직은 무식하게 각 숫자의 갯수를 세는 것 괜히 영어로 CountingSort가 아니다. 구현 const countingSort = (inputArray) => { const maxNumber = Math.max(...inputArray); const result = []; const countArray = Array.from({ length: maxNumber + 1 }).map(() => 0); inputArray.forEach((num) => { countArray[num]++; }); countArray.forEach((numberCount, index) => { for (let x = 0; x < ..

[ Javascript ] 큐과 기수정렬

큐 큐는 간단하다. FIFO. First In First Out 먼저들어온게 먼저나가는 자료구조이다. 원래는 링크드리스트로 구현하지만, 배열로 간단하게 구성해주었다. class Queue { constructor() { this.queue = []; } inqueue(value) { this.queue.push(value); } dequeue() { const [node, ...newQueue] = this.queue; this.queue = newQueue; return node; } isEmpty() { return this.queue.length === 0; } } module.exports = Queue; 기수정렬 개념 양수를 정렬하는경우, 0부터 9까지의 각각 큐를 준비한다. 제일 큰 숫자의 자..

[ Javascript ] 힙정렬과 힙

힙이란? 힙은 이진트리구조이다. 최대힙과 최소힙이 있으며 자식노드로 올수록 커지면 최소힙, 작아지면 최대힙이라 할 수 있겠다. 최소힙기준으로 설명을 하자면 양 자식노드의 값은 루트노드보다 작아야한다. 힙 구현 힙은 배열형태로 구현할 수 있다. 부모노드 인덱스 * 2가 왼쪽자식, 부모노드 인덱스*2+1이 오른쪽 자식 되시겠다. 삽입 힙의 삽입은 배열로 구현할 경우, 배열의 마지막 인덱스에 요소를 추가하는 것으로 시작된다. 그리고 해당 인덱스와 부모노드를 인덱스값이 작을떄까지(클때까지) 비교하며 둘의 위치를 조정한다. 루트까지 진행한다. add(value) { this.heap.push(value); let currentIndex = this.heap.length - 1; let parentIndex = M..

[ Javascript ] 퀵 정렬

개념 파티션 퀵정렬은 임의의 값인 피봇을 지정(나같은 경우 배열의 첫값을 설정했다.)하고, 그 인덱스를 제외한 배열 들을 좌측과 우측끝에서 비교하며 진행한다. 좌측은 pivot보다 작은 경우 진행하고 우측은 pivot보다 큰 경우 진행한다. 좌측이 pivot보다 크면 좌측인덱스는 거기서 정지한다. 우측이 pivot보다 작으면 우측 인덱스는 거기서 정지한다. 더이상 진행이 되지않는데 좌측인덱스가 우측인덱스보다 왼쪽에 있으면 좌우측값을 교환한다. 이후, 좌측인덱스가 우측인덱스보다 커지면 pivot과 오른쪽인덱스를 교환하고, 오른쪽 인덱스를 반환한다. 이때 pivot은 배열에서 자기 위치에 맞는 위치를 갖게된다. 분할정복 파티션이 완료되면 해당 인덱스를 기준으로 왼쪽 배열과 오른쪽 정렬에 대해 파티션을 진행한..

[ Javascript ] 병합정렬

개념 병합정렬은 배열의 중간 인덱스를 찾고, 그 값을 기준으로 반을 나눈다. 이걸 배열 길이가 1일때까지 반복한 뒤에, merge라는 함수를 통해 나눴던 두 배열을 동시에 인덱스를 진행시키며 새로운 배열에 결과를 저장한다. 이걸 다시 원본 배열에다가 복사해 넣어주면된다. 이게 재귀적, 병렬적으로 일어나기 때문에 아주 빠르고 안정적으로 작동한다. 구현 mergeSort 이 함수가 배열의 중간 인덱스를 찾아서 반으로 나눈 뒤 배열의 길이가 1일때까지 재귀적으로mergeSort를 부른다. 이후, 나눈 인덱스 기준 왼쪽배열과 오른쪽배열의 처리가 끝났다면, 두 배열을 다시 merge해준다. const mergeSort = (inputArray, left, right) => { if (left < right) { ..

[ Javascript ] 삽입정렬

개념 전체 배열을 돌면서 현재 인덱스를 진행시키는데, 이때 값은 key라고 한다면, key가 현재인덱스값보다 작을때까지, 현재 인덱스를 배열의 왼쪽끝까지 옮겨가며 값을 비교한 뒤에, 현재인덱스값을 현재인덱스-1의 값으로 바꾸고 인덱스를 줄인다. 이 과정이 끝나면, key를 현재 인덱스에 넣어준다. 구현 const insertSort = (inputArray) => { for (let index = 1; index 0 && inputArray[currentIndex - 1] > key) { inputArray[cu..

[ Javascript ] 선택정렬

개념 전체 배열을 회문하며 가장 작은(큰) 원소를 찾아서 인덱스와 값을 기억한뒤, 현재 비교가 되고 있는 범위의 첫번째 원소와 값을 바꾼다. 구현 const selectionSort = (inputArray) => { for (let currentIndex = 0; currentIndex inputArray[compareIndex]) { let temp = inputArray[currentIndex]; inputAr..

[ Javascript ] 버블정렬

개념 버블 정렬은 처음부터 끝-1의 인덱스에 대해서 해당 인덱스의 오른쪽 값과 비교하여 값을 변경해주는, 간단한 정렬 알고리즘이다. 실제 값끼리 수를 비교하여 진행하므로 비교기반의 알고리즘이고, 추가적인 메모리가 필요하지 않다. 구현 const bubbleSort = (inputArray) => { for (let x = 0; x inputArray[currentIndex + 1]) { let temp = inputArray[currentIndex +..