Yepchani's place

문제도둑질https://school.programmers.co.kr/learn/courses/30/lessons/42897   풀이설명도둑이 훔칠 수 있는 돈의 최댓값을 구하는 문제입니다. dp를 사용해 해결할 수 있습니다. 집이 원형으로 이어지기 때문에 첫 번째 집을 털면 마지막 집을 털 수 없습니다.따라서 dp 배열 2개를 사용해 하나는 첫 번째 집을 털 때를, 다른 하나는 첫 번째 집을 털지 않을 때를 계산합니다. dp[i]는 i번째 집까지 거쳤을 때 훔칠 수 있는 돈의 최댓값입니다. 점화식은 다음과 같습니다.dp[i] = Math.max(dp[i - 2] + money[i], dp[i - 1]) 예시 코드function solution(money) { const n = money.length; ..

문제당구 연습https://school.programmers.co.kr/learn/courses/30/lessons/169198  풀이설명각 회마다 머쓱이가 친 공이 굴러간 거리의 최솟값의 제곱을 구하는 문제입니다. 머쓱이가 친 공을 S, 쳐야할 공을 T, 공이 부딪힌 벽이나 꼭짓점을 A라고 할 때,공이 굴러간 거리 = S와 A 사이의 거리 + T와 A 사이의 거리 입니다. 공이 굴러간 거리를 쉽게 계산하기 위해, T의 좌표를 S에 가까운 벽이나 꼭짓점에 대해서 대칭시킨 좌표를 구합니다. 벽과 꼭짓점에 따라서 부딪힌 후 공을 맞출 수 있는지 여부를 따로 체크해야 합니다.벽어떤 벽 W의 임의의 점 A에서 W에 수직인 직선을 하나 그었을 때 S, T,  A의 순서로 위치한 경우, S는 W에 부딪힌 후 T를 ..

문제월간 코드 챌린지 시즌 2 - 모두 0으로 만들기https://school.programmers.co.kr/learn/courses/30/lessons/76503  풀이설명트리의 모든 점들의 가중치를 0으로 만들 때 필요한 최소 횟수를 구하는 문제입니다. 그래프 탐색을 통해 가중치와 연산 횟수를 업데이트해야 합니다.연산 횟수는 가중치의 절댓값을 더해주면 됩니다. 문제를 풀 때 유의할 점이 두 가지 있습니다.dfs 재귀 방식으로 풀 경우, 재귀 호출 깊이가 깊어져 스택 오버플로우가 발생할 수 있습니다.가중치 값이 매우 커 일반적인 넘버타입으로는 연산 시 허용 범위를 넘을 수 있습니다. 그래서 저는 비재귀 방식의 dfs를 사용하고, BigInt로 값을 저장했습니다. 예시 코드function solutio..

문제2020 카카오 블라인드 채용 - 자물쇠와 열쇠https://school.programmers.co.kr/learn/courses/30/lessons/60059  풀이설명열쇠로 자물쇠를 열 수 있는지를 구하는 문제입니다. 주의할 점은 다음과 같습니다.열쇠는 회전과 이동이 가능하다.열쇠의 크기는 자물쇠의 크기와 같거나 작다.자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않는다.자물쇠 영역 내에서는 열쇠의 돌기 부분은 자물쇠의 홈 부분과 만나야 한다.자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 한다. 열쇠는 총 3번 회전할 수 있으므로 4가지 모양으로 시도 가능합니다.열쇠의 위치는 x, y 각각 -M + 1부터 N - 1까지 가능합니다. 예시 코드function s..

문제순위https://school.programmers.co.kr/learn/courses/30/lessons/49191  풀이설명정확하게 순위를 매길 수 있는 선수의 수를 구하는 문제입니다. 그래프 탐색을 통해 해결할 수 있습니다. 각 선수별로 이긴 선수와 진 선수에 대해 각각 그래프 탐색을 진행하며 카운트를 늘려갑니다.카운트의 합이 n - 1이라면 해당 선수는 순위를 매길 수 있습니다. 예시 코드class Player { constructor(id) { this.id = id; this.wins = []; this.loses = []; }}function solution(n, results) { const players = Array.from({ length: n + 1 }, (..

문제징검다리https://school.programmers.co.kr/learn/courses/30/lessons/43236  풀이설명바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중 가장 큰 값을 구하는 문제입니다. 이분탐색을 통해 해결할 수 있습니다. 바위들을 오름차순으로 정렬해주고, 편의상 도착점을 배열에 추가해줍니다.거리의 최솟값은 1, 최댓값은 도착점으로 초기화합니다.중간값에 대해서 조건을 만족하는지 확인합니다.제거한 바위 개수가 n개 이하라면, 해당 값을 저장하고 최솟값을 높입니다.n개를 초과한다면 최댓값을 낮춥니다. 예시 코드function solution(distance, rocks, n) { let left = 1; let right = distance; let answer ..

문제디스크 컨트롤러https://school.programmers.co.kr/learn/courses/30/lessons/42627  풀이설명모든 요청 작업의 반환 시간의 평균의 정수부분을 구하는 문제입니다. 우선순위 큐를 사용해 해결할 수 있습니다. 대기 큐의 작업 우선순위는 다음과 같습니다.작업의 소요시간이 짧은 것작업의 요청 시각이 빠른 것작업의 번호가 작은 것모든 작업이 끝날 때까지 아래 과정을 반복합니다.현재 시간 또는 이전에 요청된 작업들을 모두 대기 큐에 넣습니다.대기 큐가 비어있지 않은 경우, 작업을 처리합니다.대기 큐가 비어있는 경우, 현재 시간을 다음으로 큐에 넣을 작업의 요청 시각으로 업데이트 합니다. 예시 코드function solution(jobs) { const pq = new..

문제인사고과https://school.programmers.co.kr/learn/courses/30/lessons/152995  풀이설명완호의 석차를 구하는 문제입니다. 주의할 점은 만약 어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면, 그 사원은 인센티브를 받지 못하므로 등수에서 제외해야 합니다. 계산을 쉽게 하기 위해 점수합을 기준으로 내림차순으로 정렬합니다. 이렇게 하면 앞쪽에 있는 사원은 뒤쪽에 있는 사원보다 두 점수가 모두 낮은 경우는 없게 됩니다. 이제 정렬된 점수표를 순회하면서 완호의 임시 등수를 찾습니다. 이후 완호보다 점수합이 큰 사원들 중 인센티브를 받지 못하는 사원의 수를 계산해 그만큼 완호의 등수를 올립니다. 예시 코드function solution..

문제2020 카카오 블라인드 채용https://school.programmers.co.kr/learn/courses/30/lessons/60058  풀이설명균형잡힌 괄호 문자열을 올바른 괄호 문자열로 변환한 결과를 구하는 문제입니다. 다음 변환 순서에 맞춰 구하면 됩니다.입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.  문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. ..

문제가장 먼 노드https://school.programmers.co.kr/learn/courses/30/lessons/49189  풀이설명1번 노드로부터 가장 먼 노드의 개수를 구하는 문제입니다. bfs를 이용해 해결할 수 있습니다.bfs의 특성상 가까운 거리의 노드부터 먼저 방문하게 되고, 가장 마지막에 탐색한 노드가 가장 먼 거리의 노드입니다. 전체 노드를 탐색하면서 제일 먼 거리를 갱신하고, 그 거리에서의 노드 카운트를 늘려갑니다. 예시 코드function solution(n, edge) { const graph = Array.from({ length: n + 1 }, () => []); for (const [u, v] of edge) { graph[u].push(v); graph[..