이진 탐색? 정렬 되어 있는 요소들을 반씩 제외하면서 찾는 알고리즘 O(log n)만큼의 시간 복잡도가 걸린다. 이진 탐색의 특징 반드시 정렬이 되어 있어야 사용이 가능하다. 배열 혹은 이진 트리를 사용하여 구현할 수 있다. O(log n) 시간 복잡도로 상당히 빠르다. JavaScript에서 사용하기 const arr = [1, 1, 2, 5, 10, 100, 300, 5000, 120000]; function binarySearch(array, findValue) { let left = 0; let right = array.length -1; let mid = Math.floor((left + right) / 2); while (left

트라이? 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 트라이의 특징 검색어 자동완성, 사전 찾기 등에 사용할 수 있다. 문자열을 탐색할 때 단순 비교보다 효율적으로 찾을 수 있다. L이 문자열의 길이일 때 탐색, 삽입은 O(L) 만큼의 시간 복잡도를 가진다. 자식에 대한 링크를 전부 가져야 하기 때문에 저장 공간을 많이 차지한다. JavaScript에서 사용하기 class Node { constructor(value = "") { this.value = value; this.children = new Map(); } } class Trie { constructor() { this.root = new Node(); } insert(string) { let currentNode = thi..

힙? 이진 트리 형태를 가지며 우선 순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다. 힙의 특징 우선 순위가 높은 요소가 먼저 나가는 특징이 있다. 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙이 있다. 자바스크립트에선 직접 구현해야지 사용이 가능하다. JavaScript에서 사용하기 class MaxHeap { constructor() { this.heap = [null]; } push(value) { this.heap.push(value); let currentIndex = this.heap.length - 1; let parentIndex = Math.floor(currentIndex / 2); while (parentIndex..

그래프? 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다. 정점 집합과 간선 집합으로 표현할 수 있다. 그래프의 특징 정점은 여러 개의 간선을 가질 수 있다. 크게 방향 그래프와 무방향 그래프로 나눌 수 있다. 간선은 가중치를 가질 수 있다. 사이클이 발생할 수 있다. 무방향 그래프 간선으로 이어진 정점끼리 양방향으로 이동이 가능한 그래프이다. 표현에 ( A, B )와 ( B, A )는 같은 간선으로 취급한다. 방향 그래프 간선에 방향성이 존재하는 그래프이다. 양방향으로 갈 수 있더라도 ( A, B )와 ( B, A )는 다른 간선으로 취급한다. JavaScript에서 사용하기 인접 행렬 const graph = Array.from( Array(5), () => Array(5).fill..

해시 테이블? 키와 값을 받아 키를 해싱해서 나온 index에 값을 저장하는 선형 자료구조이다. 삽입은 O(1)의 시간 복잡도를 가지며, 삭제와 탐색도 키를 알고 있다면 O(1)의 복잡도를 가진다. JavaScript에서 사용하기 const hashTable = []; hashTable["key"] = 100; hashTable["key2"] = "Hello"; delete hashTable["key"]; 배열은 객체로 구성되어 있기 때문이라 해시 테이블처럼 사용할 수 있다. 하지만 이 방법은 올바른 사용방법이 아니기 때문에 추천하지 않는다. const hashTable = {}; hashTable["key"] = 100; hashTable["key2"] = "Hello"; delete hashTable..

큐? First In First Out 개념을 가지고 있는 선형 자료구조이다. 먼저 들어간 자료가 먼저 나오는 방식이다. 자료를 넣는 것을 EnQueue, 빼는 것을 DeQueue라고 한다. JavaScript에서 사용하기 class Queue { constructor() { this.queue = []; this.front = 0; this.rear = 0; } enqueue(value) { this.queue[this.rear++] = value; } dequeue() { const value = this.queue[this.front]; delete this.queue[this.front]; this.front += 1; return value; } peek() { return this.queue[..

스택? Last In First Out 개념을 가지고 있는 선형 자료구조이다. 마지막에 들어간 요소가 먼저 나오는 방식의 자료구조이다. 자료를 넣는 것을 Push, 빼는 것을 Pop이라고 부른다. 스택의 동작 원리 스택의 동작 원리는 간단하다. Push와 Pop 밖에 가능한 행동이 없기 때문에 그것이 끝이다. 스택 자료구조의 사용처 스택 자료구조를 사용하는 가장 대표적인 곳은 스택 메모리이다. 스택 메모리는 함수가 호출되면 생성되는 지역변수와 매개변수가 저장되는 메모리다. sum 함수가 실행되면 스택 메모리에 지역 변수, 반환 주소값과 매개 변수가 저장된다. 실행 후 함수가 종료되면 Pop이 실행되어 스택 메모리에서 사라진다. 이어서 print 함수가 실행된다. 함수가 실행되면 내부에 있는 console..

0. 들어가며 프로그래머스 후보키를 풀다가 기준이 되는 배열을 가지고 크기가 2, 3, 4 , ... 모든 경우의 배열을 만들어야 했는데 이런 경우도 생각보다 많이 나와서 한번 정리해보았다. 1. 사용 방식 [ 1, 10, 30, 50, 100, 300 ]인 기준 배열이 있다면 기준 배열을 가지고 [ 1 ], [ 10 ], [ 30 ], ... [ 300 ], [ 1, 10 ], [ 1, 30 ], ... [ 1, 10, 30, 50, 100, 300 ] 의 배열을 만든다. 한번에 만들 수 있지만, 원하는 크기의 배열을 만드는 방식으로 작업했다. 2. 코드 구현 const obj = []; const numberArr = [ 1, 10, 30, 50, 100, 300 ]; function makeArr(..