GRAY | 추천 알고리즘의 과학 저자

문제설명 문제분석 이 문제는 targets를 순회하며 각 요소(target) 문자열이 keymap을 통해 최소 몇 번만에 만들어지는 지 구하는 문제입니다. 이때 target을 구할 수 없다면 -1을 담으면 됩니다. keymap과 targets 배열의 길이가 100 이하이므로 완전탐색을 이용해 문제를 해결할 수 있습니다. 이해하기 쉽게 코드작성하기 function solution(keymap, targets) { const answer = new Array(targets.length).fill(-1); // targets을 탐색 for(let i = 0; i < targets.length; i++) { const target = targets[i]; let count = 0; // target의 각 문자를..

문제설명 문제분석 시소가 평형을 이루기 위해서는 양쪽의 토크가 같아야 합니다. 먼저 토크를 구하는 공식을 살펴보겠습니다. t = F(N) * r(m) * sinΘ 토크(t)는 회전축으로부터의 거리(r)와 아래로 누르는 힘(F)과 누르는 각도(sinΘ)의 곱입니다. 이 문제에서는 시소에 사람이 탑승하므로 각도를 제외하고, 아래로 누르는 힘을 대신해 몸무게를 사용합니다. 회전축으로부터의 거리는 2m, 3m, 4m 중 하나이고, 반대쪽에도 같은 거리에 사람이 탑승합니다. 따라서 다음과 같은 공식을 구할 수 있습니다. t_1 = N_1 * r_1 = N_2 * r_2 = t_2 먼저 탑승한 사람을 정하고, 먼저 탑승한 사람의 토크를 계산합니다. 그리고 나머지 사람을 순회하며 토크를 구하고 먼저 탑승한 사람의 토..

문제설명 문제분석 이 문제는 입력 maps의 모든 요소를 순회하면서 상하좌우의 숫자로 이어진 구간의 합을 배열에 담아 리턴하는 문제입니다. bfs, dfs 모두 사용할 수 있지만 dfs를 사용할 경우 스택오버플로우가 날 수 있기때문에 bfs로 접근하도록 하겠습니다. 이해하기 쉽게 코드작성하기 function solution(maps) { const answer = []; const isVisited = new Array(maps.length).fill(0).map((x) => new Array(maps[0].length).fill(false)); const isNotVisitedIsland = (r, c) => isVisited[r][c] === false && maps[r][c] !== 'X' cons..

문제설명 문제분석 - 수도코드 이 문제는 BFS 알고리즘을 이용하여 최소 시간을 구하는 문제입니다. 시작 지점부터 출구까지의 최소 시간을 구하면 되는데, 이 때 레버를 끌어야 하는 경우를 고려해야 합니다. 우선 문제에서 주어진 문자열 배열 maps를 2차원 배열로 변환하여 저장합니다. 그리고 시작 지점부터 BFS 탐색을 시작합니다. BFS 탐색을 진행하면서, 현재 위치가 레버인 경우는 레버를 당긴 상태와 끄는 상태를 나누어서 큐에 넣어줍니다. 이 때 레버를 당긴 상태에서는 레버 위치에서부터 탐색을 시작하고, 끄는 상태에서는 현재 위치에서부터 탐색을 시작합니다. 이렇게 함으로써 레버를 끄지 않고 출구까지 갈 수 있는 경우와 레버를 끄고 출구까지 갈 수 있는 경우를 모두 고려할 수 있습니다. 마지막으로, B..

문제설명 문제분석 먼저 단순하게 접근해 모든 벽을 칠할 때 필요한 count를 세아리는 방법으로 접근합니다. function solution(n, m, section) { const wall = Array.from({ length: n + 1}).map((_, i) => section.includes(i) ? false : true); let count = 0; for(let i = 1; i paintedWall) { answer++; paintedWall = wall + m - 1; } } return answer; } section에 포함된 요소는 페인트 칠이 필요한 벽입니다. 따라서 이 벽부터 시작해서 m칸 만큼 칠하고 count를 올립니다. section의 이전요소에서 칠해진 벽을 (현재 벽 + ..

문제설명 문제분석 이 문제는 x에서 출발하여 y까지 도달하는 여정을 BFS 형태로 접근해서 해결하면 됩니다. memoization을 이용해 접근하면 반복된 연산을 줄일 수 있습니다. 이해하기 쉽게 코드작성하기 function solution(x, y, n) { let answer = Infinity; // 최초 방문하는 num과 그 depth const queue = [{ num: x, depth: 0 }]; const visitedNum = { [x]: true }; do { const { num, depth } = queue.shift(); if(num === y) return depth; const nextNums = [num + n, num * 2, num * 3]; // 각 연산에 대해 for(..

문제설명 문제분석 유사 칸토어 비트열을 생성하고, 해당 비트열의 l부터 r에 포함된 1의 갯수를 리턴하는 문제입니다. 최초 접근은 문제에서 요구한 대로 n-1번째의 "1"을 "11011"로, "0"을 "00000"으로 치환해 f(n)을 구해 slice(l-1, r)로 범위를 구하고 1을 카운트했습니다. 이해하기 쉽게 코드작성하기 function solution(n, l, r) { const similarContorBits = getSimilarCantorBits(n); return countOnes(similarContorBits.slice(l - 1, r)); } function getSimilarCantorBits(n) { let bits = "1"; if(n === 0) return bits; fo..

문제설명 문제분석 먼저 문제를 있는 그대로 바라보면, 입력받은 numbers의 각 요소를 순회하면서, 각 요소를 2진법으로 표기했을 때 비트가 1~2개 다른 수를 찾아 그 수로 해당 요소를 업데이트하는 문제입니다. 문제를 해석했으니 코드를 작성해보겠습니다. 이해하기 쉽게 코드작성하기 다음 코드에는 주석이 없습니다. 주석을 굳이 달지 않은 이유는 해당 코드의 다음에 나옵니다. 다음의 코드를 이해하려는 분들을 위해 간단히 설명하면, 각 요소와 요소로부터 1씩 증가한 값을 각각 2진법으로 변환하고 memo에 기록해둡니다. 그리고 이 두 값을 getDiffFromBits 함수로 보냅니다. 이 함수는 비트로 구성된 두 숫자의 길이를 맞춰주고, 뒤에서부터 서로 다른 비트의 수를 카운트합니다. 이때 카운트가 3이되면..

문제설명 문제분석 이 문제는 (1) 두 문자열을 입력받아 각 문자열에 대해 2글자씩 끊어서 집합을 만드는 문제와 (2) 두 집합의 교집합과 합집합의 길이를 구하고 자카드 유사도를 계산하는 문제로 구분할 수 있습니다. 각 문제별로 살펴보면 다음과 같습니다. 두 문자열을 입력받아 각 문자열에 대해 2글자씩 끊어서 집합을 만드는 문제 두 문자열이지만, 결국 하나의 함수를 작성해서 두 문자열에 대해 함수를 호출한다. 반복문을 돌면서 i번째 요소 + (i+1)번째 요소가 각각 문자인 경우, toLowerCase를 적용해 결과에 저장한다 반복문이 끝나면 결과를 리턴한다. 두 집합의 교집합과 합집합의 길이를 구하고 자카드 유사도를 계산하는 문제 두 집합(A, B)의 교집합을 구하기 위해서는 집합 A를 순회하며 집합 ..

문제설명 문제분석 - 수도코드 이 문제는 skill_trees를 순회하며 skill의 조건에 부합하는 요소를 필터링한 길이를 찾는 문제입니다. 따라서 solution 함수는 다음과 같이 간단하게 작성할 수 있습니다. function solution(skill, skill_trees) { return skill_trees.filter(x => isPossible(skill, x)).length; } 이제 isPossible 함수를 통해 skill_trees의 요소와 skill을 비교해 가능한 스킬트리인지 아닌지 리턴하면 됩니다. 이해하기 쉽게 코드작성하기 function solution(skill, skill_trees) { return skill_trees.filter(x => isPossible(ski..