문제 설명 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다. 경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭 0 [] [] [7,4,5,6] 1~2 [] [7] [4,5,6] 3 [7] [4] [5,6] 4 [7] [4,5] [..

문제 설명 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 제한사항 가로의 길이 n은 60,000이하의 자연수 입니다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. 입출력 예 n result 4 5 ..

들어가며 최단 경로 탐색 - JavaScript를 먼저 공부한 다음 푼 문제입니다. 바로 풀리지 않거나 설명이 필요하다면 참고하는 것을 추천드립니다. 문제 설명 N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다. 위..

최소 신장 트리? 신장 트리란 그래프 내에 모든 정점을 포함하는 최소 연결 그래프이다. 최소 신장 트리가 되려면 아래 조건을 만족해야한다. - 최소한의 간선으로 모든 정점이 연결되어야 한다. - 모든 신장 트리 중 가중치의 값이 최소여야 한다. - Cycle이 발생해서는 안된다. 최소 신장 트리를 구현하기 위한 대표적인 알고리즘이 크루스칼 알고리즘이다. 크루스칼 알고리즘? 그리디 개념을 이용해서 구현할 수 있다. 모든 그래프를 부분 집합으로 분리하고 가중치가 낮은 간선을 선택해 연결한다. 이때 Cycle이 발생하지 않도록 주의한다. => Cycle을 판단하기 위해서 Union-Find 알고리즘을 이용한다. Union-Find 알고리즘? 공통 원소가 없는 두 집합을 구하기 위한 알고리즘이다. 서로 다른 두..

순열? 모든 경우의 수를 계산하는 알고리즘이다. ( 순서 고려 O ) [ 1, 3, 5 ] 가 주어졌다면 1 3 5 1 5 3 3 1 5 3 5 1 5 1 3 5 3 1 처럼 모든 경우의 수를 구하는 방법이다. function permutations(arr, n) { if (n === 1) return arr.map((v) => [v]); let result = []; arr.forEach((fixed, idx, arr) => { const rest = arr.filter((_, index) => index !== idx); const perms = permutations(rest, n - 1); const combine = perms.map((v) => [fixed, ...v]); result.push..

재귀 함수를 이용하는 트리 순회는 전위 순회, 중위 순회, 후위 순회가 있다. 전위 순회 루트 노드를 방문하고, 왼쪽 서브 트리를 전위 순회한 뒤 오른쪽 서브 트리를 전위 순회하는 방식이다. 1 / \ / \ 2 3 / \ / \ 4 5 6 7 트리가 있다면 1. 루트 노드 [ 1 ] 을 방문한다. 2. [ 2 ]를 방문한다. 3. [ 2 ]의 왼쪽 서브 트리로 이동한다. 4. [ 4 ]를 방문한다. 5. [ 4 ]의 왼쪽, 오른쪽 서브 트리가 없으므로 올라간다. 6. [ 2 ]의 오른쪽 서브 트리로 이동한다. ... 방식으로 [ 1, 2, 4, 5, 3, 6, 7 ] 순서대로 순회한다. preorder(tree) { 방문(tree.root); preorder(tree.left); preorder(tre..

재귀함수? 자기 자신을 호출하는 함수이다. 이때 호출은 Call Stack에 쌓여서 스택 자료구조와 유사하게 동작한다. 함수형 프로그래밍에선 루프 구현을 재귀로 하는 경우가 많다. 자바스크립트에서의 재귀함수 콜 스택에 제한이 있다. 자바스크립트 엔진마다 다르지만 크롬의 경우 약 1만개이다. 성능이 그렇게 좋지는 않다. 재귀함수를 사용하는 경우 피보나치 수열 앞 두 항의 합이 뒤 항의 값이 되는 수열 function fibonacci(x) { if(x

들어가며 소수구하기 - JavaScript를 먼저 공부한 다음 푼 문제입니다. 바로 풀리지 않거나 설명이 필요하다면 참고하는 것을 추천드립니다. 문제 설명 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 1000000이하의 자연수입니다. 입출력 예 n result 10 4 5 3 입출력 예 설명 입출력 예 #1 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환 입출력 예 #2 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환 나의 풀이 const n = 10; function solution(n) { co..