Yepchani's place

문제동전https://www.acmicpc.net/problem/9084  풀이설명동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 구하는 문제입니다. DP를 이용해 해결할 수 있습니다. dp[i]는 금액 i를 만들 수 있는 방법의 수입니다.동전 종류와 개수만 가지고 방법을 세므로 누적합을 이용할 수 있습니다.dp[0] = 1로 초기화 해줍니다. 동전 종류가 coin이라고 한다면, i원을 만들 수 있는 방법의 수는 다음과 같습니다.이전까지의 동전 종류로 민들 수 있는 방법의 수 + (i - coin)원을 만들 수 있는 방법의 수입니다.따라서 dp[i] = dp[i] + dp[i - coin]입니다. 예시 코드function solution() { const T = Number(input())..

문제주사위 쌓기https://www.acmicpc.net/problem/2116  풀이설명주사위들을 규칙에 따라 쌓아 올렸을 때, 한 옆면의 숫자의 합이 가장 큰 값을 구하는 문제입니다. 주사위에 대한 설명입니다.주사위는 모두 크기가 같은 정육면체이며, 각 면에는 1부터 6까지의 숫자가 적혀있습니다. 그러나 마주 보는 면에 적힌 숫자의 합이 반드시 7인 것은 아닙니다. 주사위를 쌓는 규칙은 다음과 같습니다.아래에서부터 1번, 2번, 3번, ..., N번 주사위 순으로 쌓습니다.서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 합니다.e.g. 1번 주사위의 윗면에 있는 숫자 = 2번 주사위의 아랫면에 있는 숫자각 주사위는 위..

문제2022 카카오 블라인드 채용 - 양궁대회https://school.programmers.co.kr/learn/courses/30/lessons/92342  풀이설명라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 구하는 문제입니다. 백트래킹을 이용해 해결할 수 있습니다. 각 점수마다 라이언은 두 가지 선택이 가능합니다.해당 점수를 얻기 위해 화살을 사용합니다. 어피치보다 한 발 더 사용해야 합니다.해당 점수를 얻지 않습니다. 화살을 사용하지 않습니다. 주의해야 할 점은 다음과 같습니다.가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 구합니다.가장 낮은 점수를 맞힌 개수가 같..

문제혼자서 하는 틱택토https://school.programmers.co.kr/learn/courses/30/lessons/160585   풀이설명게임판이 규칙을 지켜서 틱택토를 진행했을 때 나올 수 있는 상황인지를 구하는 문제입니다. 규칙은 다음과 같습니다.선공이 "O", 후공이 "X"를 번갈아가면서 빈칸에 표시합니다.한 줄이 같은 문양으로 채워지면 해당 플레이어의 승리로 게임을 종료합니다. 다음과 같은 상황은 무효처리됩니다.자신의 차례가 아닌데 플레이한 경우한 플레이어의 승리로 게임이 종료되었음에도 그 게임을 진행한 경우 위 사항들을 고려했을 때, 올바른 게임판의 조건은 다음과 같습니다.O의 개수는 X의 개수와 같거나 하나 더 많아야 합니다.선공과 후공 둘 중 하나만 승리할 수 있습니다.선공이 승리..

문제PCCP - 석유 시추https://school.programmers.co.kr/learn/courses/30/lessons/250136  풀이설명시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 구하는 문제입니다. 매 열마다 행을 하나씩 내려가며 그래프 탐색을 진행해야 합니다.dfs를 사용할 경우, 재귀 방식을 사용하면 스택 오버플로우가 발생 가능하므로, 비재귀 방식으로 풀어야 합니다. 모든 칸에서 그래프 탐색을 진행할 경우, 시간 초과가 발생합니다.시간을 줄이기 위해서, 한 번 방문한 석유 구역은 번호를 지정한 후, 총량과 방문 기록을 저장하고, 재탐색 대신 미리 저장한 총량을 반환하면 됩니다. 예시 코드function solution(land) { const EMPTY = 0; cons..

문제2021 데브매칭 - 행렬 테두리 회전하기https://school.programmers.co.kr/learn/courses/30/lessons/77485  풀이설명각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 구하는 문제입니다. 회전마다 시작 인덱스의 원소 값을 따로 저장하고, 회전이 끝난 뒤 그 값을 다시 넣어주면 쉽게 회전을 처리할 수 있습니다. 예시 코드function solution(rows, columns, queries) { const matrix = Array.from({ length: rows }, (_, i) => Array.from({ length: columns }, (_, j) => i * columns + j + 1..

문제2019 카카오 블라인드 채용 - 길 찾기 게임https://school.programmers.co.kr/learn/courses/30/lessons/42892  풀이설명노드들로 구성된 이진트리를 전위 순회, 후위 순회환 결과를 구하는 문제입니다. y 값이 큰 순서대로, x 값이 작은 순서대로 정렬한 후, 이진트리를 구성한 다음, 순회를 하면 됩니다. 예시 코드function solution(nodeinfo) { const nodes = nodeinfo.map((info, index) => ({ x: info[0], y: info[1], index: index + 1, })); nodes.sort((a, b) => b.y - a.y || a.x - b.x); const preO..

문제2020 카카오 인턴십 - 경주로 건설https://school.programmers.co.kr/learn/courses/30/lessons/67259  풀이설명경주로를 건설하는데 필요한 최소 비용을 구하는 문제입니다. 다익스트라 알고리즘을 사용해 해결할 수 있습니다. 이 문제에서 다익스트라 알고리즘을 사용할 때 주의해야 할 부분은 다음과 같습니다.어떤 지점 C를 거쳐서 바로 오른쪽인 D로 가는 루트가 2개 있다고 하겠습니다. 1번 루트는 C의 위쪽인 A에서 C로 도착하기까지 2100원의 비용이 들고, 2번 루트는 C의 왼쪽인 B에서 C로 도착하기까지 2500원이 들었습니다. 1번 루트를 통해 D까지 간다면 코너를 하나 추가해야 하므로 총 2700원이 들지만, 2번 루트를 통한다면 코너를 추가할 필요..

문제2020 카카오 인턴십 - 수식 최대화https://school.programmers.co.kr/learn/courses/30/lessons/67257   풀이설명우승 시 받을 수 있는 가장 큰 상금 금액을 구하는 문제입니다. 가능한 모든 조합을 구해 계산하면 됩니다. 정규식을 이용하면 수식을 토큰으로 쉽게 분리할 수 있습니다. 주의할 점은 금액이 음수가 나올 경우 절댓값을 취해줘야 합니다. 예시 코드function solution(expression) { const operators = ["+", "-", "*"]; const operatorPermutations = getPermutations(operators); let maxResult = 0; for (const order of ope..

문제2023 카카오 블라인드 채용 - 이모티콘 할인행사https://school.programmers.co.kr/learn/courses/30/lessons/150368  풀이설명행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 구하는 문제입니다. 서비스 가입자 수를 최대한 늘리고, 가입자 수가 같다면 판매액을 최대로 늘려야 합니다.가능한 모든 조합을 구해 계산하면 됩니다. 예시 코드function solution(users, emoticons) { const discountRates = [10, 20, 30, 40]; const discounts = []; let maxSubscribers = 0; let maxSales = 0; dfs(0); retu..