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

문제설명 문제분석 이 문제는 대진표를 탐색하면서 A와 B가 만날 때까지 걸리는 라운드 수를 구하는 문제입니다. 대진표는 계속 반으로 나누어지므로, 이진 탐색(binary search)을 이용하여 해결할 수 있습니다. A와 B가 만날 때까지 걸리는 라운드 수를 계산할 때, A와 B가 같은 그룹에 속하는지를 판단하면 됩니다. 두 참가자의 번호를 비교해서 둘 중 작은 번호가 짝수이고, 큰 번호가 작은 번호보다 1 크다면 같은 그룹에 속하는 것으로 볼 수 있습니다. 이 경우에는 두 참가자는 다음 라운드에서 서로 만나게 됩니다. 이해하기 쉽게 코드작성하기 function solution(n,a,b) { let answer = 1; // 같은 그룹(또는 b 가 짝수이고, 남은 참가자가 1이 큰 경우)에 속하지 않으..

문제설명 문제분석 이 문제는 다이나믹 프로그래밍(DP)을 사용하여 해결할 수 있습니다. 문제에서는 1칸 또는 2칸을 뛰어서 n칸을 뛸 수 있다고 하였으므로, n칸을 뛰기 위해서는 (n-1)칸에서 1칸을 뛰는 경우와 (n-2)칸에서 2칸을 뛰는 경우의 합과 같습니다. 이를 점화식으로 나타내면 다음과 같습니다. f(n) = f(n-1) + f(n-2) 이해하기 쉽게 코드작성하기 function solution(n) { let answer = 0; let num1 = 1, num2 = 2; if (n

문제설명 문제분석 이 문제는 모바일 키패드를 누르는 문제입니다. 정확히는 눌러야하는 번호에 따라 가까운 위치의 손을 기록하는 문제입니다. 왼쪽의 1, 4, 7은 왼손으로, 오른쪽의 3, 6, 9는 오른손으로 누르며, 가운데 2, 5, 8, 0은 두 손 중 가까운 손이 누릅니다. 이때 두 손의 거리가 같다면, 오른손잡이인지 왼손잡이인지에 따라 누르는 손이 결정됩니다. 거리는 키패드의 상하좌우를 한칸 이동할 때 1씩 증가하며, 가운데 번호를 누를 때에는 반드시 현재 손가락의 위치부터 눌러야하는 번호까지의 거리를 구해야 합니다. 따라서 현재 손가락의 위치를 기억하고 있어야 합니다. 문제가 조금 복잡한 관계로 풀어서 정리하겠습니다. 키패드는 가로 3, 세로 4로 정해져 있다. 키패드의 왼쪽 3개 숫자 1, 4,..

문제설명 문제분석 - 수도코드 이 문제는 로또 당첨번호 중 N개의 번호를 확인할 수 없는 상태라는 전제 조건이 있습니다. 이 상황에서 이번주 당첨번호가 주어졌을 때, 가장 희망적인 경우와 그 반대의 경우의 당첨등수를 확인하는 문제입니다. 저 같아도 알아볼 수 없는 번호가 있다면, 이런 희망회로를 돌리면서 잠시나마 즐거운 상상을 할 것 같긴 합니다. 충분히 공감되는 김에 문제를 후딱 해결하도록 하겠습니다. 먼저 민우가 가지고 있는 로또 용지에서 번호를 확인할 수 없는 0으로 된 요소의 갯수를 기록한다. 민우의 로또용지를 순회하며 각 번호가 당첨번호인지 확인한다. 민우의 로또용지에서 당첨번호의 갯수와 알아볼 수 없는 번호를 더해 가장 높은 등수를 구한다. 민우의 로또용지에서 당첨번호의 갯수만으로 가장 낮은 ..

문제설명 문제분석 이 문제는 입력값인 ingredient 요소를 하나씩 stack에 쌓고, stack에 쌓인 최근 4개가 햄버거를 만들 수 있는 순서대로 쌓여있는지 확인합니다. 만약 햄버거를 만들 수 있다면, stack의 4개를 빼내고 answer 카운트를 1증가합니다. ingredient를 탐색하며 stack에 하나씩 추가한다. stack에 쌓인 최근 4개의 요소로 햄버거를 만들 수 있는지 검사한다. 햄버거를 만들 수 있다면 stack의 최근 4개 요소를 제거하고, answer를 증가한다. 요약했으니, 코드를 짜보겠습니다. 이해하기 쉽게 코드작성하기 function solution(ingredient) { var answer = 0; const stack = []; for(let i of ingredi..

문제설명 문제분석 이 문제는 각 문자를 탐색하면서 조건에 부합하는지 확인하는 문제입니다. 여러 형태로 접근할 수 있겠지만, 저는 한 단어의 구분을 공백으로 보기로 했습니다. 각 문자를 탐색한다. 문자가 공백이 아닌 경우, strArr에 현재의 문자를 추가한다. 문자가 공백인 경우, strArr.join("") + 공백을 answer에 추가한다. 이때 strArr.length가 0이면 toUpperCase를 한다. 이때 strArr.length가 0이 아니면 toLowerCase를 한다. 반복문이 끝난 후에도 strArr에 담겨있는 단어가 있다면 answer에 추가한다. 요약했으니, 코드를 짜보겠습니다. 이해하기 쉽게 코드작성하기 function solution(s) { let answer = ""; co..

문제설명 문제분석 주어진 숫자에 중복은 없고, 3개를 골라서 더했을 때 소수가 되는 경우를 세아리면 되는 간단한 문제입니다. 소수를 판별하는 함수를 구현한다. 배열의 요소 중 3개를 선택하는 로직을 구현한다. 문제를 단순화 했으니 이해하기 쉽게 코드를 짜보겠습니다. 이해하기 쉽게 코드작성하기 function solution(nums) { let answer = 0; const arr = []; // nums 배열에서 3가지 요소를 임시 배열 arr에 담고, 요소의 합이 소수인지 검사 (function recursion(nums, idx) { if (arr.length === 3) { if (isPrime(arr.reduce((a,c)=>a+c),0)) { answer++; return; } } for (..

문제설명 문제분석 이 문제는 옛날 콜라 문제의 2, 1 자리에 a, b를 넣으면 해결되는 문제입니다. 현재 가지고 있는 빈 병 중 a개 묶음이 몇 개 나오는지 구합니다. 이 묶음의 수와 묶음에 포함되지 못한 낱병의 합으로 다시 한 번 a개 묶음이 몇 개 나오는지 구합니다. 동일한 과정을 빈 병의 총 갯수가 한 묶음에 묶여야하는 a개 미만인 경우까지 반복합니다. 문제를 단순화 했으니 이해하기 쉽게 코드를 짜보겠습니다. 이해하기 쉽게 코드작성하기 function solution(a, b, n) { return recursion(a, b, n); } function recursion(a, b, emptyBottles) { // 빈 병의 갯수가 한 묶음의 기준인 a개보다 적은 경우 0을 리턴 if(emptyBo..

문제설명 문제분석 두 행렬의 같은 요소를 더해주면 되는 문제입니다. 매우 간단하므로 예시를 작성하되 자세한 설명은 생략합니다. /* arr1: arr2: return: * [ [ [ * [1, 2], [3, 4], [4, 6], * [2, 3], [5, 6], [7, 9], * ] ] ] */ 이해하기 쉽게 코드작성하기 function solution(arr1, arr2) { var answer = []; for(let r = 0; r < arr1.length; r++) { const row = []; for(let c = 0; c < arr1[r].length; c++) { row.push(arr1[r][c] + arr2[r][c]); } answer.push(row); } return answer; ..

문제설명 문제분석 문자열 암호 문제입니다. 문자열 s의 각 요소를 index만큼 뒤의 알파벳으로 치환하여 리턴하면 됩니다. 다만 이때 skip에 포함된 알파벳은 (index 만큼)에 포함되지 않습니다. 가벼운 마음으로 풀어보겠습니다. 문자열 s의 각 요소를 skip에 포함되지 않은 뒤의 알파벳 중 index 만큼 건너간 알파벳으로 치환한다. 이해하기 쉽게 코드작성하기 function solution(s, skip, index) { // 모든 알파벳 중 skip에 포함된 알파벳 제외 const remainAlphabet = "abcdefghijklmnopqrstuvwxyz".split("").filter(x => !skip.includes(x)); // 문자열 s의 각 요소를 남은 알파벳 중 index 만..