소수 ? 1 또는 자기 자신만을 약수로 가지는 수를 의미한다. 소수를 구하는 방법 2부터 N - 1까지 루프를 돌며 나눠보기 소수를 구할 때 가장 먼저 생각할 수 있는 방법으로 O(n) 시간 복잡도를 가진다. function is_prime(num) { for (let i = 2; i < num; i += 1) { if(num % i === 0) { return false; } } return true } 다른 소수 구하는 방법에 비해 느린편에 속한다. 제곱근으로 확인하기 어떤 소수라도 N의 제곱근보다 큰 수로 나눠지지 않는다는 공식을 이용한다. 시간 복잡도는 O(sqrt(n)) 으로 훨씬 빠른 방법이다. function is_prime(num) { for (let i = 2; i * i < num; i..

들어가며 이 전에 배달 문제를 풀었는데, 그땐 BFS를 정확하게 이해하지 못한 상태로 문제를 풀어서 코드 자체가 엉성했는데, 이번에 가장 먼 노드 문제를 풀고 다시 한번 도전해보았다. 문제 설명 N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, ..

문제 설명 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)이 있을 때 배상 비용을 최소화한 결과를 반환하는 함수를 만들어 주세요. ..