Computer Science/Algorithm, Data Structure 12

자바스크립트 자료구조 그래프(Graph)

그래프(Graph)에 대해 알아보자. 그래프는 두 가지로 나눠진다. 방향 그래프(Directed Graph) 무방향 그래프(Undirected Graph) 위의 사진의 방향성이 없는 그래프를 의미한다. 그래프에선 노드를 정점(Vertex)이라고도 하고 정점을 이어주는 것을 간선(Edge)이라 한다. 차수(Degree)란 하나의 정점에 닿는 간선의 수를 의미하고 간선을 한 번만 통해 갈 수 있으면 인접(Adjacent)하다고 한다. 그래프를 인접 리스트(Adjacency List), 인접 행렬(Adjacency Matrix)로 구현 할 수 있다. 인접 리스트를 활용하여 간단한 그래프를 구현해보자. class Graph { constructor() { this.AdjacencyList = new Map();..

자바스크립트 알고리즘 선형 탐색(Linear Search), 이진 탐색(Binaray Search)

선형 탐색과 이진 탐색 알고리즘에 대해 알아보자. 선형 탐색(Linear Search) 찾으려고 하는 것을 처음부터 하나하나 탐색을 하고 찾으려고 하는 값과 일치하면 멈춘다. function linearSearch(arr, find) { for (let i = 0; i < arr.length; i++) { if (arr[i] === find) return `탐색(find)의 값이 들어있는 배열의 인덱스는 ${i}`; } return; } linearSearch([4, 5, 2, 1, 9], 9) // '탐색(find)의 값이 들어있는 배열의 인덱스는 4' 이진 탐색(Binaray Search) 시작과 끝의 값을 더하여 2로 나눈 중간값부터 탐색을 한다. 탐색하는 값과 중간 값을 비교를 한 후 작으면 왼쪽..

자바스크립트 알고리즘 선택 정렬(Selection Sort)

선택 정렬(Selection Sort) 선택한 값을 최소 요소로 선택하고 선택한 값보다 작은 요소가 있다면 그 값과 스왑 한다. 예를 들면, [4, 3, 5, 1] [1, 3, 5, 4] [1, 3, 4, 5] for 중첩 구문으로 min으로 지정한 값을 배열의 끝까지 비교를 하여 제일 작은 수를 찾아낸 후 temp라는 임시 변수를 생성하여 값을 스왑 한다. function selectionSort(arr, length = arr.length) { for (let i = 0; i < length; i++) { let min = i; for (let j = i + 1; j < length; j++) { if (arr[min] > arr[j]) { min = j; } } if (i !== min) { let..

자바스크립트 알고리즘 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort) 배열의 두 번째부터 시작하고, temp라는 변수를 만들어서 값을 임시로 저장을 하고, 저장한 임시의 값보다 0번째 인덱스 값이 크다면 스왑 해준다. 예를 들면, array[0] = 4, array[1] = 1 temp = array[1] array[1] = array[0] array[0] = array[1] array[0] = 1, array[1] = 4 for문 중첩 구문 및 조건을 생각하기가 난이도 있는거 같다. function insertionSort(array, length = array.length) { for (let i = 1; i < length; i++) { let temp = array[i]; let j; for (j = i - 1; j > -1 ..

자바스크립트 알고리즘 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort) 배열의 두 수를 연속적으로 비교하여 위치를 바꾸어 정렬하고 시간 복잡도 O(n^2)인 알고리즘이다. [6, 5, 3] 을 예를 들면, [5, 6, 3] [5, 3, 6] 다시 처음부터 비교 [3, 5, 6] function bubbleSort(arr, length = arr.length) { while (length) { for (let i = 0; i < arr.length; i++) { if (arr[i] > arr[i + 1]) { let swap = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = swap; } } length--; } return arr; } console.log(bubbleSort([5,2,3,6,8])) // [2,..

자바스크립트 알고리즘 합병 정렬(Merge Sort)

합병 정렬(Merge Sort) 알아보자. 분할 정복(divide and conquer) 알고리즘 활용한 알고리즘이다. 재귀적으로 배열을 쪼갠 후 값을 비교하여 정렬한다. 개인적으로 퀵 정렬보다 난이도가 있다고 생각한다. 2019/06/16 - [Computer Science/Algorithm, Data Structure] - 자바스크립트 알고리즘 퀵 정렬(Quick Sort) 자바스크립트 알고리즘 퀵 정렬(Quick Sort) Quick Sort(퀵 정렬)에 대하여 알아보자. 병합 정렬(Merge Sort) 및 힙 정렬(Heap Sort)보다 빠르게 수행되는 큰 데이터 세트의 효율적인 정렬 알고리즘이다. 배열의 임의의 기준 값을 pivot, 피벗보다 작으면 왼.. jeongw00.tistory.com ..

자바스크립트 알고리즘 퀵 정렬(Quick Sort)

Quick Sort(퀵 정렬)에 대하여 알아보자. 병합 정렬(Merge Sort) 및 힙 정렬(Heap Sort)보다 빠르게 수행되는 큰 데이터 세트의 효율적인 정렬 알고리즘이다. 배열의 임의의 기준 값을 pivot, 피벗보다 작으면 왼쪽, 크면 오른쪽으로 이동하여 정렬한다. 여기서는 피벗의 기준을 배열의 마지막으로 잡고 피벗보다 작으면 left 배열로 추가 크면 right 배열에 값을 추가한다. 위에서 했던 방법을 왼쪽, 오른쪽 부분에서 재귀적으로 실행하고 그다음 전개 연산자(spread operator)로 left, pivot, right 합친 후 리턴한다. function quickSort(arr, length = arr.length - 1, start = 0) { if(arr.length < 2)..

자바스크립트 자료구조 트리(Tree)

트리의 용어에 대해 알아보면 Root: 트리의 최상위 노드 Child: 자식 노드 Parent: 부모 노드 leaf: 자식 노드가 없는 노드 ancestor: 조상 노드 descendant: 자손 노드 sibling: 형제 노드 트리는 다양한 종류가 있는데 이진 탐색 트리(Binary Search Tree)에 대해 알아보자. 여기서 이진 트리란 최대 두 개의 자식 노드를 가지는 트리 자료 구조이다. 이진 탐색 트리는 아래와 같은 속성이 있는 이진 트리의 자료 구조이다. 모든 노드에는 최대 2개의 하위 노드가 있고 각 노드의 키가 왼쪽 하위 트리에 저장된 키보다 크거나 같고 오른쪽 하위 트리에 저장된 키보다 작거나 같아야 한다. class Node { constructor(data) { this.right..

자바스크립트 자료구조 힙(Heap), 힙 정렬(Heap Sort)

2019/05/30 - [Computer Science/Algorithm, Data Structure] - 자바스크립트 자료구조 해시 테이블(Hash Table) 자바스크립트 자료구조 해시 테이블(Hash Table) 2019/05/26 - [Computer Science/Algorithm, Data Structure] - 자바스크립트 자료구조 연결 리스트(Linked List) 자바스크립트 자료구조 연결 리스트(Linked List) 모든 자바스크립트 개발자가 알아야 하는 33가.. jeongw00.tistory.com 해시 테이블에 이어서 Heap(힙)에 대해 알아보자. Heap(힙)은 max-heap(최대 힙), min-heap(최소 힙) 속성을 충족시키는 완전 이진 트리의 일종으로 우선순위 큐를 ..

자바스크립트 자료구조 해시 테이블(Hash Table)

2019/05/26 - [Computer Science/Algorithm, Data Structure] - 자바스크립트 자료구조 연결 리스트(Linked List) 자바스크립트 자료구조 연결 리스트(Linked List) 모든 자바스크립트 개발자가 알아야 하는 33가지 개념 지난 글에서 Stack과 Queue에 대해 알아보았고 오늘은 연결 리스트(Linked List)를 알아보자. 배열과 마찬가지로 연결 리스트는 데이터를 순차적으로 저장.. jeongw00.tistory.com 연결리스트에 이어서 Hash Table(해시 테이블)에 대해 알아보자. 해시 테이블은 키(key)를 값(value)에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 여기서 매핑이란 키(key) 역할을 하는 데..