들어가며
데브코스 첫 주가 끝이 났다. 시간이 어떻게 이렇게 빨리 갈 수 있는지 신기하다. 강의 시작하기 전, 어떤 방식으로 강의가 진행되는지 궁금했는데 재밌는 내용이 상당히 많다. 공부하다보면 시간이 금방 지나갈 때가 많다. 학부생일때는 전공 공부도 해야했기 때문에 프로그래밍 공부하면서 시간이 빨리 가는게 스트레스였다(결국 전공 공부도 해야해서...). 그런데 지금은 내가 하는 공부가 외부의 상황과 일치한다고 해야할까? 그래서 너무 좋다. 다른 걱정 안하고 공부만 할 수 있는 환경을 만들었다는게 뿌듯하다.
그래프 실습
어제 공부했던 그래프 실습으로 프로그래머스의 가장 먼 노드 문제를 풀었다.
1 class Queue {2 constructor() {3 this.queue = [];4 this.front = 0;5 this.rear = 0;6 }78 enqueue(value) {9 this.queue[this.rear++] = value;10 }1112 dequeue() {13 const value = this.queue[this.front];14 delete this.queue[this.front];15 this.front++;16 return value;17 }1819 isEmpty() {20 return this.front === this.rear;21 }22 }2324 function solution(n, edge) {25 const graph = {};26 edge.forEach(([start, end]) => {27 const data1 = graph[start] || [];28 const data2 = graph[end] || [];29 graph[start] = [...data1, end];30 graph[end] = [...data2, start];31 });32 const queue = new Queue();33 queue.enqueue([1, 0]);34 const visited = [1];35 const answer = [];36 while (!queue.isEmpty()) {37 const [nodeNumber, distance] = queue.dequeue();38 let tempCheck = 0;39 graph[nodeNumber].forEach((item) => {40 if (visited.indexOf(item) !== -1) {41 tempCheck++;42 } else {43 queue.enqueue([item, distance + 1]);44 visited.push(item);45 }46 });47 if (tempCheck === graph[nodeNumber].length) {48 answer.push([nodeNumber, distance]);49 }50 }51 let prev = 0;52 let count = 0;53 answer.sort((a, b) => b[1] - a[1]);54 answer.forEach((item, index) => {55 if (index === 0) {56 prev = item[1];57 } else {58 if (prev !== item[1]) return false;59 }60 count++;61 });62 return count;63 }
먼저, 그래프 문제이기 때문에 인접 리스트 방식으로 그래프를 저장하기로 했다. 주어진 edge 배열을 순회하면서 graph 객체에 각 노드번호를 키로 하고 값은 인접한 노드 번호를 배열로 담는다. 어떻게 하면 가장 먼 노드를 찾을까 고민하다가 1번부터 시작해서 끝 노드로 가면 더 이상 갈 수 있는 노드가 없다는 점을 이용해 visited 배열을 만들어 방문한 노드를 저장하고 인접한 노드중에 갈 수 있는 노드가 없다면 끝 노드라고 판단하기로 했다. 끝 노드를 answer 배열에 넣고 거리를 기준으로 내림차순 정렬한다. 마지막으로 끝 노드라도 거리가 다를 수 있기 때문에 값이 가장 큰 것들의 개수만 반환한다.
이 문제는 한시간 반 만에 스스로 풀었다! 살면서 처음으로 내 힘으로 푼 3단계 문제다. 문제 풀고 뿌듯했다. 뿌듯한 마음으로 강사님 해설 강의를 봤는데 급우울해졌다. 내가 짠 코드에 문제가 꽤 많았는데
- 그래프를 저장할 때 2차원 배열 형태로 저장하는 게 더 깔끔
- 구현하기 위해 불필요한 변수 선언
- 쉬운 방법이 있는데 복잡하게 구현
끝 노드를 구하고 가장 먼 노드의 개수를 반환할 때 Math.max() 와 filter() 를 사용하면 간단하게 구할 수 있는데 불필요한 과정을 거쳤다. 그래도 혼자 풀었다는 것에 의의를 두고 조금씩 고쳐나가면 되겠지?
트리
방향 그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 자료구조이다.
- 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
- 정점이 N개라면 간선의 개수는 N-1개이다. (1번 특징을 가지고 있기 때문)
- 루트에서 특정 노드로 가는 방법은 단 하나이다.
이진 트리
이진 트리는 각 정점이 최대 두 개의 자식을 가지는 트리이다. 이진 트리의 종류에는 마지막 레벨을 제외하고 모든 정점이 채워져 있는 완전 이진 트리, 마지막 레벨까지 모두 채워져 있는 포화 이진 트리, 한 방향으로만 정점이 이어지는 편향 트리가 있다. 이진트리의 특징으로는
- 정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있다.(편향 트리의 경우)
- 정점이 N개인 포화 또는 완전 이진 트리는 높이가 logN이다.
- 높이가 h인 포화 이진 트리의 정점의 개수는 2^h-1 이다.
- 보통 이진 트리는 다음의 자료구조에 사용된다.
- 이진 탐색 트리
- 힙
- AVL 트리
- 레드-블랙 트리
이진 트리를 구현하는 방법은 인접 행렬을 이용하는 방법과 인접 리스트를 이용하는 방법으로 나뉜다.
인접 행렬을 이용하는 경우 배열을 사용하는데, 배열의 0번째 인덱스는 비워두고 1번 인덱스부터 채워나간다. 루트 노드가 1번 인덱스에 위치하고 자식 노드는 각각 2번과 3번 인덱스에 위치한다. 부모 노드의 인덱스에 2를 곱하면 왼쪽 자식의 인덱스이고 그 값에 1을 더하면 오른쪽 자식의 인덱스이다.
위와 같은 이진 트리를 저장하기 위해 아래와 같은 방법을 사용한다.
1 const binaryTree = [2 undefined,3 2, // index: 14 7, 5. //5 2, 6, undefined, 9,6 undefined, undefined, 5, 11, undefined, undefined, 4, undefined7 ]
인접 리스트를 이용하는 경우 연결 리스트를 사용해 구현할 수 있다. 각 노드는 왼쪽 노드와 오른쪽 노드를 가질 수 있고 연결 리스트 클래스를 만들어 루트 노드를 가리키면 된다. 위의 트리를 구현하기 위해 아래와 같은 코드를 사용한다.
1 class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7 }89 class BinaryTree {10 constructor(node) {11 this.root = node;12 }1314 display() {15 const queue = new Queue();16 queue.enqueue(this.root);17 while (!queue.isEmpty()) {18 const node = queue.dequeue();19 console.log(node.value);20 if (node.left !== null) queue.enqueue(node.left);21 if (node.right !== null) queue.enqueue(node.right);22 }23 }24 }2526 const tree = new BinaryTree(new Node(9));27 tree.root.left = new Node(3);28 tree.root.right = new Node(8);29 tree.root.left.left = new Node(2);30 tree.root.left.right = new Node(5);31 tree.root.left.right.right = new Node(4);32 tree.root.right.right = new Node(7);33 tree.display(); // 9 3 8 2 5 7 4
힙
이진 트리 형태를 가지며 우선 순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있는 자료구조이다. 우선순위 큐를 구현할 때 사용된다.
우선순위 큐?
일반 큐(FIFO)와 달리 우선 순위가 높은 것이 먼저 나간다. 우선순위 큐는 자료구조가 아닌 개념이다. 우선순위 큐는 힙이 아니다. 우선순위 큐를 구현하기에 적합한 자료구조가 힙일 뿐, 다른 자료구조를 사용해도 우선순위 큐를 구현할 수 있다.
우선순위가 높은 요소가 먼저 나간다는 특징을 가지고 있는데, 나간다는 건 우선순위가 높은 요소가 루트 노드로 이동하기 때문에 이를 나간다고 표현한 것 같다. 루트 노드가 가장 큰 값인 최대 힙, 루트 노드가 가장 작은 값인 최소 힙으로 나뉜다.
힙 요소는 어떤 방식으로 추가될까?
- 요소가 추가될 때 트리의 가장 마지막 정점에 위치시킨다.
- 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.
- 이 과정을 반복한다.
코드는 다음과 같다.
1 class MaxHeap {2 constructor() {3 this.heap = [null];4 }56 push(value) {7 this.heap.push(value);8 let currentIndex = this.heap.length - 1;9 let parentIndex = Math.floor(currentIndex / 2);1011 while (parentIndex !== 0 && this.heap[parentIndex] < value) {12 const temp = this.heap[parentIndex];13 this.heap[parentIndex] = value;14 this.heap[currentIndex] = temp;1516 currentIndex = parentIndex;17 parentIndex = Math.floor(currentIndex / 2);18 }19 }20 }2122 const heap = new MaxHeap();23 heap.push(3);24 heap.push(5);25 heap.push(1);26 heap.push(2);27 heap.push(6);28 heap.push(9);29 heap.push(8);30 console.log(heap.heap); // [null, 9, 5, 8, 2, 3, 1, 6]
위 코드는 최대 힙을 코드로 구현한 것이다. 최소 힙을 구현할 때는 현재 노드와 부모 노드의 값을 비교할 때 현재 노드의 값이 부모 노드의 값보다 작을때 위치를 변경해주면 된다.
힙 요소를 제거할 때는 어떻게 해야 힙 구조를 유지할 수 있을까?
- 우선순위가 가장 높은 루트 정점만 제거가 가능하다.
- 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치시킨다.
- 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
- 두 자식 정점이 우선순위가 더 낮을 때까지 반복한다.
1 pop(){2 const returnValue = this.heap[1];3 this.heap[1] = this.heap.pop();4 let currentIndex = 1;5 let leftIndex = 2;6 let rightIndex = 3;78 while (this.heap[currentIndex] < this.heap[leftIdex] || this.heap[currentIndex] < this.heap[rightIndex]){9 if (this.heap[leftIndex] > this.heap[rightIndex]){10 const temp = this.heap[currentIndex];11 this.heap[currentIndex] = this.heap[leftIndex];12 this.heap[leftIndex] = temp;13 currentIndex = leftIndex;14 } else {15 const temp = this.heap[currentIndex];16 this.heap[currentIndex] = this.heap[rightIndex];17 this.heap[rightIndex] = temp;18 currentIndex = rightIndex;19 }20 leftIndex = currentIndex * 2;21 rightIndex = currentIndex * 2 + 1;22 }23 return returnValue;24 }2526 const heap = new MaxHeap();27 heap.push(3);28 heap.push(5);29 heap.push(1);30 heap.push(2);31 heap.push(6);32 heap.push(9);33 heap.push(8);34 console.log(heap.pop()); // 935 console.log(heap.pop()); // 836 console.log(heap.heap); // [null, 6, 5, 1, 2, 3]
트라이
문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 자동 완성, 사전 찾기 등에 응용된다. 트라이 구조의 특징은 다음과 같다.
- 루트는 비어 있다.
- 각 간선(링크)은 추가될 문자를 키로 가진다.
- 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
- 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.
코드를 살펴보자.
1 class Node {2 constructor(value = "") {3 this.value = value;4 this.children = new Map();5 }6 }78 class Trie {9 constructor() {10 this.root = new Node();11 }1213 insert(string) {14 let currentNode = this.root;1516 for (const char of string) {17 if (!currentNode.children.has(char)) {18 currentNode.children.set(char, new Node(currentNode.value + char));19 }20 currentNode = currentNode.children.get(char);21 }22 }2324 has(string) {25 let currentNode = this.root;2627 for (const char of string) {28 if (!currentNode.children.has(char)) {29 return false;30 }31 currentNode = currentNode.children.get(char);32 }33 return true;34 }35 }
루트 노드의 값은 비어있고 자식 노드들은 Map 에 문자를 키로 하고, 이전 노드의 값과 문자를 이어 붙인 값을 값으로 저장된다. Map 의 키가 간선의 역할을 한다. 자료구조의 형태는 이해했는데 이걸 사용해서 자동 완성 기능을 만들 수 있다는 게 신기하다. 혹시 블로그 검색 기능에 추가할 수도 있지 않을까 두근두근하다.
정렬
일정한 순서대로 열거하는 것을 정렬이라고 한다. 오름차순으로 정렬하거나 내림차순으로 정렬, 사용자가 정하는 기준에 따라 정렬할 수도 있다. 대부분의 언어에서 빌트인으로 정렬 기능을 제공한다. 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 방식이 존재한다.
정렬은 크게 비교식 정렬과 분산식 정렬로 구분된다.
비교식 정렬: 다른 요소와의 비교를 통해 정렬
버블 정렬: 서로 인접한 두 요소를 검사한다. O(n^2) 만큼의 시간이 소요됨.
1 function bubble(array) {2 for (let i = 0; i < array.length - 1; i++) {3 for (let j = 0; j < array.length - 1; j++) {4 if (array[j] > array[j + 1]) {5 const temp = array[j];6 array[j] = array[j + 1];7 array[j + 1] = temp;8 }9 }10 }11 return array;12 }1314 console.log(bubble([1, 8, 4, 3, 7, 0])); // [0, 1, 3, 4, 7, 8]선택 정렬: 선택 요소와 가장 우선순위가 높은 요소를 교환한다. O(n^2) 이 소요됨.
1 function selection(array) {2 for (let i = 0; i < array.length - 1; i++) {3 let minIndex = i;4 for (let j = i + 1; j < array.length; j++) {5 if (array[j] < array[minIndex]) {6 minIndex = j;7 }8 }9 const temp = array[i];10 array[i] = array[minIndex];11 array[minIndex] = temp;12 }13 return array;14 }1516 console.log(selection([1, 8, 4, 3, 7, 0])); // [0, 1, 3, 4, 7, 8]삽입 정렬: 선택 요소를 삽입할 수 있는 위치를 찾아 삽입한다. O(n^2) 만큼 소요됨.
1 function insertion(array) {2 for (let i = 1; i < array.length; i++) {3 let key = array[i];4 let position = i;5 while (position > 0 && key < array[position - 1]) {6 array[position] = array[position - 1];7 position--;8 }9 array[position] = key;10 }11 return array;12 }13 console.log(selection([1, 8, 4, 3, 7, 0])); // [0, 1, 3, 4, 7, 8]
분산식 정렬: 분할 정복을 사용해 정렬하는 방법
분할 정복이란?
문제를 작은 2개의 문제로 분리하고 처리 후 병합하는 방법
합병 정렬: 분할 정복 알고리즘을 사용한 정렬 방법. 최악의 경우와 최선의 경우가 같기 때문에 안정적인 정렬 방법이다. O(nlogn)이 소요된다.
1 function mergeSort(leftArr, rightArr) {2 let leftPos = 0;3 let rightPos = 0;4 let tempArr = [];5 while (leftPos < leftArr.length && rightPos < rightArr.length) {6 if (leftArr[leftPos] > rightArr[rightPos]) {7 tempArr.push(rightArr[rightPos]);8 rightPos++;9 } else {10 tempArr.push(leftArr[leftPos]);11 leftPos++;12 }13 }14 if (leftPos < leftArr.length) {15 tempArr.push(...leftArr.slice(leftPos));16 }17 if (rightPos < rightArr.length) {18 tempArr.push(...rightArr.slice(rightPos));19 }20 return tempArr;21 }2223 function merge(array) {24 if (array.length <= 1) return array;25 let mid = Math.ceil(array.length / 2);26 let leftArr = array.slice(0, mid);27 let rightArr = array.slice(mid);28 return mergeSort(merge(leftArr), merge(rightArr));29 }3031 console.log(merge([1, 8, 4, 3, 7, 0])); // [0, 1, 3, 4, 7, 8]배열을 잘게 분할하는 merge 함수와 잘게 분할된 배열을 정렬하는 mergeSort 함수로 나누어져 있다.
퀵 정렬: 매우 빠른 정렬 방법이지만 최악의 경우가 존재하기 때문에 불안정한 정렬 방법이다. O(nlogn)이 소요된다. pivot을 정해서 pivot 보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 정렬하고 같은 과정을 왼쪽과 오른쪽 값에 각각 반복한다.
1 function quick(array) {2 if (array.length <= 1) return array;3 let pivot = array[0];4 let leftArr = [];5 let equalArr = [];6 let rightArr = [];7 for (const num of array) {8 if (pivot > num) {9 leftArr.push(num);10 } else if (pivot < num) {11 rightArr.push(num);12 } else {13 equalArr.push(num);14 }15 }16 return [...quick(leftArr), ...equalArr, ...quick(rightArr)];17 }1819 console.log(quick([1, 8, 4, 3, 7, 0])); // [0, 1, 3, 4, 7, 8]
정렬 실습
정렬 실습으로 프로그래머스의 가장 큰 수 문제를 풀었다. 정렬 기준을 찾는 게 중요할 것 같아서 정렬 기준을 찾으려 했는데 실패했다. 그냥 숫자 두 개를 문자열로 변환해 어떤 숫자가 앞으로 갈 때 완성된 숫자가 더 커지는지 비교해서 정렬했다.
1 function solution(numbers) {2 if (numbers.filter((item) => item !== 0).length === 0) return "0";3 return numbers4 .map((item) => String(item))5 .sort((a, b) => {6 const case1 = a + b;7 const case2 = b + a;8 if (parseInt(case1) > parseInt(case2)) return -1;9 if (parseInt(case1) < parseInt(case2)) return 1;10 })11 .join("");12 }
자바스크립트 sort 메서드 정리 코딩테스트 문제를 풀 때 sort 를 자주 사용하게 되는 것 같다. 사용할 때마다 오름차순 또는 내림차순 정렬을 할 때 어떤 값을 반환해야 하는지 헷갈려 정리해보고자 한다.
1 arr.sort([compareFunction]);위와 같이 사용할 수 있다. compareFunction 은 정렬 순서를 정의하는 함수이다. 이 함수를 생략하면 배열값이 문자열로 변환되고 유니코드 값을 기준으로 정렬된다.
compareFunction 의 반환값이 0보다 작으면 a를 b보다 앞으로 위치시키고 0보다 크면 b를 a보다 앞으로 위치시킨다.
이진 탐색
정렬되어 있는 요소들을 반씩 제외하며 찾는 알고리즘이다. 찾아야 할 배열이 절반씩 줄어들기 때문에 O(logn)이 소요된다. 탐색의 대상이 무조건 정렬되어 있어야 하며, 배열 또는 이진 트리를 사용해 구현한다. 배열을 사용할 경우 left, mid, right 변수를 사용해 찾아야 할 배열의 범위를 줄인다. 이진 트리를 사용하면 왼쪽 서브트리는 루트값보다 작고, 오른쪽 서브트리는 루트값보다 큰 값이 위치한다.
이진 탐색 트리의 문제점 최악의 경우 한쪽으로 편향된 트리가 구성될 수 있는데 이때는 순차탐색과 동일한 시간복잡도를 가진다.
배열을 사용한 경우
1 function binarySearch(value, array) {2 let left = 0;3 let right = array.length - 1;4 let mid = Math.floor((left + right) / 2);56 while (left < right) {7 if (array[mid] === value) return mid;8 if (mid < value) {9 left = mid + 1;10 } else if (mid > value) {11 right = mid - 1;12 }13 mid = Math.floor((left + right) / 2);14 }15 return -1;16 }1718 console.log(binarySearch(5, [1, 7, 3, 5, 8, 9, 2].sort()));이진 트리
1 class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7 }89 class BinarySearchTree {10 constructor() {11 this.root = null;12 }1314 insert(value) {15 const node = new Node(value);16 if (this.root === null) {17 this.root = node;18 } else {19 let currentNode = this.root;20 while (currentNode !== null) {21 if (currentNode.value > value) {22 if (currentNode.left === null) {23 currentNode.left = node;24 break;25 }26 currentNode = currentNode.left;27 } else {28 if (currentNode.right === null) {29 currentNode.right = node;30 break;31 }32 currentNode = currentNode.right;33 }34 }35 }36 }3738 search(value) {39 let currentNode = this.root;40 while (currentNode !== null) {41 if (currentNode.value === value) return true;42 if (currentNode.value > value) {43 currentNode = currentNode.left;44 } else {45 currentNode = currentNode.right;46 }47 }48 return false;49 }50 }
이진 탐색 실습
프로그래머스 입국 심사
문제를 계속 봐도 어떻게 푸는지 감이 안잡혀서 다른 사람의 풀이를 봤다. 머리를 한 대 맞은 것 같다. 이진 탐색을 이런 식으로 사용하는구나 느끼게 되었다. 풀이의 핵심은 입국 심사에 걸리는 최소시간부터 최대시간까지 설정해두고 그 범위 내에서 입국심사에 걸리는 최소시간을 이진 탐색을 사용하는 것이었다. 이 문제는 애초에 내가 생각할 수 없는 문제였던 것 같아 많이 아쉽지는 않다. 다음에 비슷한 문제가 나왔을 때 이진 탐색을 사용할 수 있도록 공부해야겠다.
1 function solution(n, times) {2 times.sort((a, b) => a - b);3 let answer = 0;4 let left = 1;5 let right = n * times[times.length - 1];6 while (left <= right) {7 let mid = Math.floor((left + right) / 2);8 let total = n;9 for (const time of times) {10 total -= Math.floor(mid / time);11 if (total <= 0) {12 answer = mid;13 right = mid - 1;14 break;15 }16 }17 if (total > 0) {18 left = mid + 1;19 }20 }21 return answer;22 }
정리
트리, 이진 트리, 힙, 우선순위 큐, 트라이, 정렬, 이진 탐색에 대해 공부했다. 당장은 이해가 잘 되고 생각이 잘 나는데 시간이 지날수록 잊어버릴 게 분명하다. 그러지 않기 위해 복습을 꾸준히 해야겠다.
참고자료
트리 구조 https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0
정렬 알고리즘 기초 https://medium.com/@joongwon/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88-805391cb088e
퀵 정렬 https://todaycode.tistory.com/52
https://www.daleseo.com/sort-quick/
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
합병 정렬 https://velog.io/@proshy/JSmerge-sort%ED%95%A9%EB%B3%91-%EC%A0%95%EB%A0%AC
https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC
자바스크립트 sort() https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
입국 심사 풀이 https://velog.io/@ayoung0073/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC