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

문제설명 문제분석 이 문제는 특정 조건에서는 현재 위치를 벗어나지 않고, 그 외에는 산책로를 이동하며 위치를 변경하는 문제입니다. 특정 조건은 다음과 같습니다. 주어진 방향으로 이동할 때 공원을 벗어나는지 확인합니다. 주어진 방향으로 이동 중 장애물을 만나는지 확인합니다. 이 문제를 풀면서 조금 난감했던 지점이 있었는데, 코드와 함께 설명토록 하겠습니다. 이해하기 쉽게 코드작성하기 import ( "strings" "strconv" "github.com/thoas/go-funk" ) func solution(park []string, routes []string) []int { answer := getPosition(park, "S") for _, route := range routes { way, fe..

문제설명 문제분석 모든 좌표를 순회하며 파일을 찾아 최소 x, 최소 y, 최대 x, 최대 y를 각각 구해 하나의 배열에 담아 리턴하는 문제입니다. 새로 올라온 level 1이기도 하고, 주말이기도 하니 빠르게 코딩해보겠습니다. 이해하기 쉽게 코드작성하기 function solution(wallpaper) { const file = "#"; let offset = { minX: Infinity, minY: Infinity, maxX: -1, maxY: -1 }; for(let row = 0; row < wallpaper.length; row++) { for(let col = 0; col < wallpaper[row].length; col++) { if(wallpaper[row][col] === file) ..

문제설명 문제분석 이 문제는 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이되면..