문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예 n edge ..

들어가며 이진 탐색 - JavaScript를 먼저 공부한 다음 푼 문제입니다. 바로 풀리지 않거나 설명이 필요하다면 참고하는 것을 추천드립니다. 문제 설명 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는 데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는 데 걸리는 시간이 담긴 배열 times가..

이진 탐색? 정렬 되어 있는 요소들을 반씩 제외하면서 찾는 알고리즘 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

들어가며 트라이 - 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..