문제 출처
나의 풀이 (실패)
"A행동과 B행동을 하는 데 비용이 필요하다. 이때 최소 비용(최대 이득)은?"혹은"A에서 B로 가는 데의 거리는? 최단 거리는? 최대거리는?"
이런 식의 구조를 가진 유형을 만나면 2차원 배열을 떠올려야 한다.
다익스트라, dp 등등
++ 힙을 구현할 준비도 해야 한다.
이걸 어떻게 다 구현하지? 싶으면 대부분 완전탐색이다. dfs/bfs는 여러 경우의 수를 단순한 로직으로 모두 탐색할 수 있게 해주므로.
풀지 못한 몇 가지 이유들
- 의도치 않게 문제를 그리디처럼 접근했다. (정확히는, 그리디적으로 접근하려 했으면 최소한 2차원 배열을 셋팅하고 다익스트라는 고려했어야 했다.)
문제가 여러 개 있을 때, 다음 단계의 문제만 최소한으로 풀려고 접근했다. 하지만 생각해보면 다음 단계의 문제를 최소한으로 풀더라도 전체 풀이 시간으로 봤을 때는 비효율적일 수 있기 때문에 모든 문제 풀이에 필요한 알고력/코딩력을 구해야 했다. - 어쨌든 경우의 수를 구해야 한다고 생각했는데, 완전탐색으로까지 발상이 이어지지 못했다.
처음엔 단순 조합을 먼저 떠올렸는데 문제를 중복해서 풀 수 있기에 중복 조합을 생각했다. 근데 사실 생각해보면, 뽑는 개수가 정해져 있지 않다. 정해져 있는 건 뽑는 개수가 아니라 최소 시간이다. 부분집합을 구해야 하는데, 단순 개수가 아니라 최소 시간을 만족하는 모든 경우의 수를 고려해야 하므로 완전탐색을 해야 했다. (부분집합으로 특정 조건 만족하는 경우의 수 찾는 방법을 찾다가 포기했다.)
다른 풀이
풀이 1
(초기 알고력, 초기 코딩력) 상태에서 시작해 (목표 알고력, 목표 코딩력) 상태에 도달하는 최단 시간을 구하는 문제.
targetAlp, targetCop : 모든 문제를 푸는 데 필요한 알고력/코딩력을 셋팅한다
dp[alp][cop] : 특정 알고력/코딩력에 도달하는 데 필요한 최단 시간을 표현한다
dfs 분기점는 3가지로 나뉜다.
1. 시간으로 알고력을 올리는 경우
2. 시간으로 코딩력을 올리는 경우
3. 문제를 직접 푸는 모든 경우의 수
시간 복잡도는 O(목표 알고력 * 목표 코딩력 * (problems 배열의 길이))가 된다.
let targetAlp = 0;
let targetCop = 0;
let visit = []; // visit[alp][cop]
function solution(alp, cop, problems) {
// const [alp_req, cop_req, alp_rwd, cop_rwd, cost] = problems[i]
let answer = 0;
// 단순히 i+1번째 문제를 풀기 위해 i+1번째 문제의 목표치를 target으로 잡는 게 아니라
// 전체 모든 문제를 풀기 위해 모든 문제들 중에서 가장 최대값을 각각 target으로 잡아야 한다.
// 그리디로 접근하면 전체 문제 풀이의 최소 시간을 구할 수 없다.
for (let i = 0; i < problems.length; ++i) {
targetAlp = Math.max(targetAlp, problems[i][0]);
targetCop = Math.max(targetCop, problems[i][1]);
}
// 0 <= alp_req, cop_req <= 150
for (let i = 0; i < 151; ++i) {
let temp = [];
for (let j = 0; j < 151; ++j) {
temp.push(987654321);
}
visit.push(temp);
}
// 완전탐색이 필요한 문제.
// 경우의 수를 찾아야 했는데,
// (처음엔 조합인가? => 중복조합인가? => 부분집합인가? => 그게 아니라 특정 값을 만족하는 모든 경우의 수를 찾아야 하네? DFS구나)
DFS(alp, cop, 0, problems);
// 단계별로 접근하면 안 된다.
// 전체 문제들의 최대 필요 알고력/코딩력을 위한 최소값이 각 배열에 저장되어 있다.
answer = visit[targetAlp][targetCop];
return answer;
}
// 최소값을 찾아야 하므로 max값으로 설정 후 업데이트
function DFS(a, c, cnt, problems) {
// 알고력/코딩력이 최대치를 넘어가면 최대치로 고정 (그래야 더 시간을 쓰지 않으므로)
if (targetAlp < a) a = targetAlp;
if (targetCop < c) c = targetCop;
if (visit[a][c] <= cnt) return;
visit[a][c] = Math.min(visit[a][c], cnt);
if (a === targetAlp && c === targetCop) return;
for (let i = 0; i < problems.length; ++i) {
if (a >= problems[i][0] && c >= problems[i][1]) {
let nextAlp = a + problems[i][2];
let nextCop = c + problems[i][3];
// 문제를 직접 푸는 모든 경우의 수
DFS(nextAlp, nextCop, cnt + problems[i][4], problems);
}
}
// 시간으로 알고력/코딩력을 올리는 경우
DFS(a + 1, c, cnt + 1, problems);
DFS(a, c + 1, cnt + 1, problems);
}
console.log(
solution(10, 10, [
[10, 15, 2, 1, 2],
[20, 20, 3, 3, 4],
])
); // 15다익스트라로도 풀 수 있다.
풀이 2
function solution(alp, cop, problems) {
var answer = 0;
let targetAlp = 0;
let targetCop = 0;
for (let i = 0; i < problems.length; i++) {
const [reqAlp, reqCop, rwdAlp, rwdCop, dur] = problems[i];
targetAlp = Math.max(reqAlp, targetAlp, alp);
targetCop = Math.max(reqCop, targetCop, cop);
}
problems.push([0, 0, 1, 0, 1])
problems.push([0, 0, 0, 1, 1])
const dp = Array.from({ length: Math.max(targetAlp + 1, alp + 1) }, () => new Array(Math.max(targetCop + 1, cop + 1)).fill(999));
dp[alp][cop] = 0;
for (let i = alp; i <= targetAlp; i++) {
for (let j = cop; j <= targetCop; j++) {
for (const [reqAlp, reqCop, rwdAlp, rwdCop, dur] of problems) {
if (i >= targetAlp && rwdCop === 0) continue;
if (j >= targetCop && rwdAlp === 0) continue;
if (i >= reqAlp && j >= reqCop) {
const curAlp = Math.min(i + rwdAlp, targetAlp)
const curCop = Math.min(j + rwdCop, targetCop)
dp[curAlp][curCop] = Math.min(dp[curAlp][curCop], dp[i][j] + dur)
}
}
}
}
return dp[targetAlp][targetCop];
}풀이 3
힙 구현
function createHeap() {
const list = [],
compare = (parent, child) => {
// [0]은 알고력, [1]은 코딩력, [2]는 비용
if (parent[2] == child[2]) {
return parent[0] + parent[1] > child[0] + child[1];
}
return parent[2] < child[2];
};
const swap = (i, j) => {
const tmp = list[i];
list[i] = list[j];
list[j] = tmp;
};
const push = (value) => {
list.push(value);
// 삽입할 때 트리의 끝에서 시작해서 전부 비교하며 올라간다.
let i = list.length - 1;
let parentIndex = Math.floor((i + 1) / 2) - 1;
while (i != 0 && !compare(list[parentIndex], list[i])) {
swap(i, parentIndex);
i = parentIndex;
parentIndex = Math.floor((i + 1) / 2) - 1;
}
};
const pop = () => {
const value = list[0];
list[0] = list[list.length - 1];
list.pop();
// 현재 노드 N, 부모 노드 (N-1) / 2, 왼쪽자식노드 (N*2) + 1, 오른쪽자식노드 (N*2) + 2
let parentIndex = 0;
let leftChildIndex = 2 * (parentIndex + 1) - 1;
let rightChildIndex = leftChildIndex + 1;
// 트리에서 pop을 하면,
// 뒤에서 빼주고 그걸 최상위 노드로 이동시켜준다음에
// 전체 트리를 순회해서 최소값/최대값이 최상위노드가 되도록 유지시켜줘야 한다.
while (leftChildIndex < list.length) {
let swapIndex = -1;
if (leftChildIndex == list.length - 1) {
if (!compare(list[parentIndex], list[leftChildIndex]))
swap(parentIndex, leftChildIndex);
break;
}
// 부모와 왼쪽자식 비교
else if (compare(list[parentIndex], list[leftChildIndex])) {
if (compare(list[parentIndex], list[rightChildIndex])) break;
else {
swapIndex = rightChildIndex;
}
}
// 왼쪽자식 오른쪽자식 비교
else {
if (compare(list[leftChildIndex], list[rightChildIndex]))
swapIndex = leftChildIndex;
else swapIndex = rightChildIndex;
}
if (swapIndex >= 0) {
swap(parentIndex, swapIndex);
parentIndex = swapIndex;
rightChildIndex = 2 * (parentIndex + 1);
leftChildIndex = rightChildIndex - 1;
}
}
return value;
};
return { push, pop, list };
}
function speed(problem) {
const [_, __, alpRwd, copRwd, cost] = problem;
return (alpRwd + copRwd) / cost;
}
function solution(alp, cop, problems) {
// 비용이 적게 드는 순으로 정렬한다.
const sortedProblems = problems.filter((p) => speed(p) > 1);
sortedProblems.sort((a, b) => speed(a) - speed(b));
// reduce를 사용해서 목표 알고력/코딩력을 구한다.
const targetPoint = problems.reduce(
(score, problem) => {
return [Math.max(score[0], problem[0]), Math.max(score[1], problem[1])];
},
[0, 0]
);
let answer =
Math.max(0, targetPoint[0] - alp) + Math.max(0, targetPoint[1] - cop);
// costBoard[알고력][코딩력]을 셋팅해준다.
// 최단 거리를 찾는 것이므로 Infinity로 잡아준다.
const costBoard = new Array(targetPoint[0] + 1)
.fill(undefined)
.map(() => new Array(targetPoint[1] + 1).fill(Infinity));
// 힙을 생성해주고 시작 알고력/코딩력과 비용을 셋팅해준다.
const heap = createHeap();
heap.push([alp, cop, 0]);
// 힙을 사용해서 bfs를 진행한다.
while (heap.list.length) {
// 뒤에서 빼준다.
let [currAlp, currCop, cost] = heap.pop();
// 현재 알고력/코딩력, 비용을 셋팅해주고
currAlp = Math.min(targetPoint[0], currAlp);
currCop = Math.min(targetPoint[1], currCop);
// 2차원 배열 [알고력][코딩력]에 계속 최솟값을 업데이트해준다.
// 더 적은 비용을 만나면 업데이트해준다.
if (costBoard[currAlp][currCop] > cost) {
// 더 적은 비용을 만났을 때 (한번 비용을 만났을 때 관련 있는 노드들을 전부 처리해주니까 좋으므로)
// 알고력 줄과 코딩력 줄을 각각 순회하며 최솟값으로 전부 업데이트해준다.
for (let i = currAlp; i >= alp; i--) {
if (costBoard[i][currCop] > cost) {
costBoard[i][currCop] = cost;
}
}
for (let i = currCop; i >= cop; i--) {
if (costBoard[currAlp][i] > cost) {
costBoard[currAlp][i] = cost;
}
}
// 그리고 해당 보드를 비용으로 업데이트해준다.
costBoard[currAlp][currCop] = cost;
sortedProblems.forEach((p) => {
const [alp_req, cop_req, alp_rwd, cop_rwd, problemCost] = p;
// 문제를 못 푼 경우는 건너 뛰고
if (alp_req > currAlp || cop_req > currCop) return;
// 문제를 푼 경우 현재 알고력/코딩력을 증가시켜줘야 한다.
heap.push([currAlp + alp_rwd, currCop + cop_rwd, cost + problemCost]);
});
// 그리고 문제를 푸는 게 아니라 직접 시간을 써서 알고력/코딩력을 증가시키는 경우도 고려해준다.
if (currAlp < targetPoint[0]) heap.push([currAlp + 1, currCop, cost + 1]);
if (currCop < targetPoint[1]) heap.push([currAlp, currCop + 1, cost + 1]);
}
}
return costBoard[targetPoint[0]][targetPoint[1]];
}참고
[JavaScript] 프로그래머스 - 코딩 테스트 공부
2022 테크 여름인턴십 코딩테스트 해설
[프로그래머스] - 코딩 테스트 공부 (다익스트라, Python)
https://medium.com/@wooleejaan