들어가며 트라이 - JavaScript를 먼저 공부한 다음 푼 문제입니다. 바로 풀리지 않거나 설명이 필요하다면 참고하는 것을 추천드립니다. 문제 설명 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다. 효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다. 예를 들어, 학습된 단어들이 아래와 같을 때 go gone guild go를 찾을 때 go를 ..

트라이? 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 트라이의 특징 검색어 자동완성, 사전 찾기 등에 사용할 수 있다. 문자열을 탐색할 때 단순 비교보다 효율적으로 찾을 수 있다. 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를 먼저 공부한 다음 푼 문제입니다. 바로 풀리지 않거나 설명이 필요하다면 참고하는 것을 추천드립니다. 문제 설명 OO 조선소에서는 태풍으로 인한 작업지연으로 수주한 선박들을 기한 내에 완성하지 못할 것이 예상됩니다. 기한 내에 완성하지 못하면 손해 배상을 해야 하므로 남은 일의 작업량을 숫자로 매기고 배상비용을 최소화하는 방법을 찾으려고 합니다. 배상 비용은 각 선박의 완성까지 남은 일의 작업량을 제곱하여 모두 더한 값이 됩니다. 조선소에서는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다. 조선소에서 작업할 수 있는 N 시간과 각 일에 대한 작업량이 담긴 배열(works)이 있을 때 배상 비용을 최소화한 결과를 반환하는 함수를 만들어 주세요. ..

힙? 이진 트리 형태를 가지며 우선 순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다. 힙의 특징 우선 순위가 높은 요소가 먼저 나가는 특징이 있다. 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙이 있다. 자바스크립트에선 직접 구현해야지 사용이 가능하다. 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..

0. 들어가며 자바스크립트로 개발을 하다 보면 배열이 5개의 배열을 가지고 있는 형식으로 만들 때가 있다. 예를 들어 제공되는 것이 " N : 3 "이 끝이고 배열이 3개의 배열을 가지고 있는 이차원 배열을 만들 때가 있다. 그럴 경우, const arr = []; for(let i = 0; i [] ); 이렇게 사용하면 간단하게 원하는 사이즈의 2차원 배열을 만들 수 있다.

들어가며 해시 테이블 - JavaScript를 먼저 공부한 다음 푼 문제입니다. 바로 풀리지 않거나 설명이 필요하다면 참고하는 것을 추천드립니다. 문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solut..

해시 테이블? 키와 값을 받아 키를 해싱해서 나온 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..