[JS] 코딩 테스트 공부 : 공부 팁 X, 카카오 2022 인턴 문제 O

보통 프로그래머스에서 문제 제목이 있으면

"JS PROBLEM_TITLE" 이런식으로 검색하면 쉽게 다른 블로그의 풀이를 볼 수 있는데,

이 문제는 제목이 너무.. 알고리즘에 잡히기 힘들겠더라구요ㅋㅋㅋㅋ

아무튼 가봅시다! 어제에 이은 또 dp문제네요.

---

문제 요약

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.

알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다.

문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.

예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다.

• A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다.
• B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다.

풀 수 없는 문제를 해결하기 위해서는 알고력과 코딩력을 높여야 합니다. 알고력과 코딩력을 높이기 위한 다음과 같은 방법들이 있습니다.

• 알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.
• 코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.
• 현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다. 각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있습니다.
• 문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.

당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.

초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.

모든 문제들을 1번 이상씩 풀 필요는 없습니다. 입출력 예 설명을 참고해주세요.

---

제한사항

• 초기의 알고력을 나타내는 alp와 초기의 코딩력을 나타내는 cop가 입력으로 주어집니다.
  • 0 ≤ alp,cop ≤ 150
• 1 ≤ problems의 길이 ≤ 100
• problems의 원소는 [alp_req, cop_req, alp_rwd, cop_rwd, cost]의 형태로 이루어져 있습니다.
• alp_req는 문제를 푸는데 필요한 알고력입니다.
  • 0 ≤ alp_req ≤ 150
• cop_req는 문제를 푸는데 필요한 코딩력입니다.
  • 0 ≤ cop_req ≤ 150
• alp_rwd는 문제를 풀었을 때 증가하는 알고력입니다.
  • 0 ≤ alp_rwd ≤ 30
• cop_rwd는 문제를 풀었을 때 증가하는 코딩력입니다.
  • 0 ≤ cop_rwd ≤ 30
• cost는 문제를 푸는데 드는 시간입니다.
  • 1 ≤ cost ≤ 100

정확성 테스트 케이스 제한사항

• 0 ≤ alp,cop ≤ 20
• 1 ≤ problems의 길이 ≤ 6
  • 0 ≤ alp_req,cop_req ≤ 20
  • 0 ≤ alp_rwd,cop_rwd ≤ 5
  • 1 ≤ cost ≤ 10

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

---

테스트케이스

alp	cop	problem	result
10	10	[[10,15,2,1,2],[20,20,3,3,4]]	15
0	0	[[0,0,2,1,2],[4,5,3,1,2],[4,11,4,0,2],[10,4,0,4,2]]	13

 

접근 방법

dp 문제를 걸러내는 나름의 팁이 있는데요.

반복문이 사실 선형적으로 돌아가는데, 간혹 뭔가 다양한 기준점에서 반복문이 돌아가는 느낌을 주는 문제들이 있습니다.

 

이 문제도 dp를 쓰지 않는다면, 현재의 알고력과 코딩력을 저장해두고, problems를 순회해가면서 dfs로 타고타고 갔겠죠..? 근데 이게 코드 짜기도 전에 시간 초과가 눈에 보입니다. 이럴 땐 조심스레 dp가 아닐까...? 생각해보면 대부분 맞더라구요.

---

일반적으로 dp를 사용한다하면 2차원으로 선언해주는 경우가 많습니다.

이 문제도 알고력과 코딩력을 바탕으로 2차원 dp로 표현해야겠네요.

 

dp[alp][cop] = cost

 

이런 꼴로 만들겠다고 생각하면 그 다음부터는 꽤나 명확해진답니다.

이런 식으로 구현하면 될 것 같습니다.

 

1. 최대 alp와 최대 cop를 구한다.
2. dp[alp][cop]를 만들고 Infinity(cost)로 초기화한다.
    (단, 초기에 설정된 alp와 cop는 비용 0으로 초기화 해줍시다!)
3. dp[i][j] + cost와 dp[i + alp_rwd][j + cop_rwd] 를 비교해서 작은쪽으로 갱신한다.
4. dp[i + 1][j](그리고 dp[i][j + 1] 얘도) = dp[i][j] + 1 과 비교해서 작은쪽으로 갱신한다.

 

이렇게 해주면 dp[maxAlp][maxCop]의 cost가 최소로 갱신되니.. 정답이겠군요!

 

정답 코드

function solution(alp, cop, problems) {
    let [maxAlp, maxCop] = [alp, cop];
    
    problems.forEach(v => {
        maxAlp = Math.max(maxAlp, v[0]);
        maxCop = Math.max(maxCop, v[1]);
    });
    
    const dp = Array.from({ length: maxAlp + 1 }, () => Array.from({ length: maxCop + 1 }, () => Infinity));
    dp[alp][cop] = 0;
    
    for (let i = alp; i <= maxAlp; i++) {
        for (let j = cop; j <= maxCop; j++) {
            if (i < maxAlp) dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);
            if (j < maxCop) dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);
            // 아래 이 친구 안넣으면 효율성 테케 3번 시간초과납니다. 
            if (i === maxAlp && j === maxCop) break;
            
            for (const [alp_req, cop_req, alp_rwd, cop_rwd, cost] of problems) {
                if (i < alp_req || j < cop_req) continue;
                let currAlp = i + alp_rwd > maxAlp ? maxAlp : i + alp_rwd;
                let currCop = j + cop_rwd > maxCop ? maxCop : j + cop_rwd;
                dp[currAlp][currCop] = Math.min(dp[currAlp][currCop], dp[i][j] + cost);
            }
        }
    }
    
    return dp[maxAlp][maxCop];
}

 

팁 1. index의 적절한 조정을 통한 효율성 확보

if (i < maxAlp) dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);
if (j < maxCop) dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);
if (i === maxAlp && j === maxCop) break;

 

당연하지만 이런 최소 시간, 거리 문제는 언제나 배열의 index를 잘 지켜주고 있나?

이걸 생각해줘야합니다. 넘지 않게 잘 조정을 해줍시다!

 

위에 코드에도 적었지만, 아래 problems의 순회 루프를 마지막 루프에선 걸러줘야합니다.

안그러면 시간 초과가 나더라구요.

---

진짜 dp...

막상 풀고 나면 이해가 명확한데, 항상 저 초기화하고 형태 만들어주기까지가 너무 어렵네요.

계속 연습해줍시다!

 

그럼 이만!