Yepchani's place

문제2021 카카오 블라인드 채용 - 합승 택시 요금https://school.programmers.co.kr/learn/courses/30/lessons/72413  풀이설명A, B 두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 할 때, 최저 예상 택시 요금을 구하는 문제입니다. A, B 둘이서 임의의 지점 x까지 합승해서 간다고 할 때, 최저 택시 요금은 다음과 같습니다.s에서 x까지의 택시요금 + x에서 a까지의 택시 요금 + x에서 b까지의 택시 요금 s, a, b 각각에서 그래프 탐색을 통해 각 노드까지의 최소 요금을 구합니다.모든 노드를 순회하며 s, a, b에서 해당 노드까지의 요금을 구하고, 최소 요금을 업데이트합니다. 예시 코드class PriorityQueue { ..

문제2019 카카오 블라인드 채용 - 후보키https://school.programmers.co.kr/learn/courses/30/lessons/42890  풀이설명후보 키의 개수를 구하는 문제입니다. 모든 조합에 대해서 유일성과 최소성을 만족하는 조합의 개수를 구합니다. 예시 코드function solution(relation) { const candidateKeys = []; const numRows = relation.length; const numCols = relation[0].length; for (let i = 1; i relation[r][index]).join("|"); if (rowsMap.has(tuple)) return false; rowsMap.add(..

문제거스름돈https://school.programmers.co.kr/learn/courses/30/lessons/12907 풀이설명n원을 거슬러 줄 방법의 수를 구하는 문제입니다. dp를 사용해 해결할 수 있습니다. dp[i]는 i원을 거슬러 주는 방법의 수를 의미합니다.dp[0] = 1로 초기화합니다. 각 화폐 단위에 대해서 그 화폐 단위까지 도달하는 방법의 수를 누적해 계산합니다. 점화식은 다음과 같습니다.dp[i] = dp[i] + dp[i - coin] 예시 코드function solution(n, money) { const MOD = 1000000007; const dp = Array(n + 1).fill(0); dp[0] = 1; for (const coin of money) { ..

문제2021 카카오 블라인드 채용 - 메뉴 리뉴얼https://school.programmers.co.kr/learn/courses/30/lessons/72411  풀이설명새로 추가하게 될 코스요리의 메뉴 구성을 구하는 문제입니다. 메뉴 개수 별로 최소 2번 이상 주문된 단품메뉴 조합 중 가장 많이 주문된 조합을 찾아야 합니다.그런 조합이 여러 개라면 전부 포함합니다. 예시 코드function solution(orders, course) { const combinationCountsByMenuSize = new Map(); const result = []; for (const c of course) { combinationCountsByMenuSize.set(c, new Map()); } ..

문제2020 카카오 인턴십 - 보석 쇼핑https://school.programmers.co.kr/learn/courses/30/lessons/67258  풀이설명모든 보석을 하나 이상 포함하는 가장 짧은 구간을 구하는 문제입니다. 슬라이딩 윈도우를 이용해 해결할 수 있습니다.해시맵에 각 보석의 개수를 저장해 모든 보석이 포함되었는지를 확인합니다. 예시 코드function solution(gems) { const gemTypes = new Set(gems).size; const gemCount = new Map(); let left = 0, right = 0; let minLength = Infinity; let result = [0, gems.length - 1]; while (right

문제2019 카카오 개발자 겨울 인턴십 - 불량 사용자https://school.programmers.co.kr/learn/courses/30/lessons/64064  풀이설명제재 아이디 목록을 만들 수 있는 경우의 수가 몇 개인지 구하는 문제입니다. 백트래킹을 이용해 해결할 수 있습니다. 가능한 모든 사용자 아이디 조합을 시도해야 합니다.현재 아이디가 매칭되면 재귀호출을 통해 다음 매칭으로 넘어갑니다. 불가능하면 이전 단계로 돌아갑니다. 예시 코드function solution(user_id, banned_id) { const bannedSet = new Set(); const selected = []; dfs(0); return bannedSet.size; function dfs(depth..

문제최고의 집합https://school.programmers.co.kr/learn/courses/30/lessons/12938  풀이설명다음 조건을 만족하는 최고의 집합을 구하는 문제입니다.각 원소의 합이 S가 되는 수의 집합위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합 조건을 만족하려면, 각 원소가 가능한 한 평균에 가까워야 합니다. 방법은 다음과 같습니다.quotient (s를 n으로 나눈 뒤 내림한 값)와 remainder (s를 n으로 나눈 나머지)를 구합니다.배열에 quotient를 (n - remainder)만큼 넣습니다. 이후 (quotient + 1)을 remainder만큼 넣습니다. 예시 코드function solution(n, s) { if (n > s) return [-1..

문제야근 지수https://school.programmers.co.kr/learn/courses/30/lessons/12927  풀이설명야근 피로도를 최소화한 값을 구하는 문제입니다. 최대 힙을 이용해 해결할 수 있습니다. 모든 작업량을 최대 힙에 넣고, 가장 큰 작업량을 빼서 1 감소시키고 다시 넣어주기를 반복합니다.모든 작업이 끝난 후, 최대 힙에 남은 작업량을 순서대로 꺼내 제곱하여 더해줍니다. 예시 코드function solution(n, works) { let totalFatigue = 0; const maxHeap = new MaxHeap(); for (const work of works) { maxHeap.insert(work); } for (let i = 0; i

문제쿼드압축 후 개수 세기https://school.programmers.co.kr/learn/courses/30/lessons/68936  풀이설명쿼드압축을 진행 후, 최종적으로 남는 0의 개수와 1의 개수를 구하는 문제입니다. 압축은 다음과 같이 진행됩니다.압축하고자 하는 특정 영역을 S라고 정의합니다. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다. 3번 과정은 재귀 방식을 통해 값을 반환받아 더하는 방식으로 구현할 수 있습니다. 예시 코드function solution(arr) { return compress(0, 0, arr.len..

문제호텔 대실https://school.programmers.co.kr/learn/courses/30/lessons/155651  풀이설명필요한 최실 객실 수를 구하는 문제입니다. 최소 힙을 사용해 해결할 수 있습니다. 최소 힙에는 현재 시간 이전에 입실 후 아직 청소가 마무리되지 않은 방들의 (퇴실 시간 + 청소시간)이 들어있습니다.예약 시간을 입실 시간이 빠른 순으로 정렬 후, 순회하며 현재 시간 기준으로 청소까지 마무리가 된 방들을 최소 힙에서 빼줍니다.최소 힙에 현재 예약의 (퇴실 시간 + 청소 시간)을 넣어주고, 현재 사용중인 방 개수와 지금까지 최대로 사용한 방 개수를 비교해 더 큰 값을 저장합니다.순회를 마치고 가장 큰 값을 반환하면 됩니다. 예시 코드function solution(book..