[프로그래머스] 코딩 테스트 공부 풀이 (2022 카카오 인턴십)

| |
프로그래머스 - 코딩 테스트 공부 C++ 풀이 (2022 카카오 인턴십 코딩테스트 기출)


문제 설명

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

알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 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


풀이

문제 제목이 코딩 테스트 공부 인지라 구글링으로 해설을 찾아보기 난감하여 본 포스트의 검색 유입이 걱정되는 문제였습니다.

카카오 코딩테스트 문제 치고는 문제 자체는 굉장히 직관적이므로, 따로 해석을 하거나 이해해야 하는 부분은 없었습니다. 다만 한 가지 얕은 함정이 있는 문제였습니다.

최단시간을 구한다는 점과, 한 번의 턴에서 소모할 수 있는 시간이 고정되어 있지 않다는 점에서 다익스트라를 직관적으로 떠올리기 쉽습니다. 그것과 더불어 더 작은 문제의 해답이 전체 문제 해답의 일부가 된다는 점도 직관적으로 파악하기 쉬워 DP를 떠올리기도 쉽습니다. 이 문제는 두 가지 방법으로 모두 풀이가 가능하며, 사실 다익스트라 또한 개념적으로는 DP에 기반합니다.

필자가 생각하는 실전에서의 가장 자연스러운 풀이는, 정확성과 효율성이 존재하는 문제이므로 재귀를 통한 완전탐색으로 우선 정확성을 통과한 뒤, 거기에 메모이제이션만 얹어 DP 방식으로 효율성까지 통과하는 풀이입니다.

다음과 같은 재귀함수를 정의해봅시다.

solve(alp, cop) = 현재 알고력이 alp, 코딩력이 cop일 때 모든 문제를 풀 수 있게 되기까지 걸리는 시간

그리고 하나의 상태에서 할 수 있는 행동은 다음과 같이 3가지입니다.

  • 알고리즘 공부
    • solve(alp, cop) = min(solve(alp, cop), solve(alp + 1, cop) + 1)
  • 코딩 공부
    • solve(alp, cop) = min(solve(alp, cop), solve(alp, cop + 1) + 1)
  • 문제 해결
    • solve(alp, cop) = min(solve(alp, cop), solve(alp + alp_rwd, cop + cop_rwd) + cost)

그런데 이 문제에서는 한 가지 주의할 점이 있습니다. 바로 dp로 잡을 공간의 크기입니다. 문제에 대하여 극단적인 상황을 생각해보면, 어떠한 문제의 alp_rwd가 cop_rwd에 비해 비약적으로 크고, 반드시 이 문제를 여러 번 풀어야 모든 문제를 풀 수 있게 된다고 가정해봅시다. 그렇다면 alp에 해당하는 dp의 크기를 넉넉히 잡아야 하는데, 이때 dp 공간의 크기는 곧 연산 수와 직결됩니다. 따라서 문제에서 제시한 제한사항에서 충분히 통과하는 시간복잡도를 갖는 알고리즘을 사용해도, 최댓값의 크기가 제한사항보다 훨씬 커져 더욱 많은 연산을 수행하게 되어 통과하지 못하게 됩니다. 따라서 최대 알고력과 최대 코딩력을 넘어가게 될 경우 이를 최댓값으로 고정시켜주는 후처리가 필요합니다. 후처리 이후에도 dp 계산을 통해 정답을 반환하는 데에는 영향을 끼치지 않음은 쉽게 알 수 있습니다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

int maxAlp, maxCop;
int cache[151][151];

int solve(int alp, int cop, vector<vector<int>>& problems) {
    if(alp >= maxAlp && cop >= maxCop) return 0;
    
    // 최댓값을 넘어갈 시 공간 크기 조정
    if(alp > maxAlp) alp = maxAlp;
    if(cop > maxCop) cop = maxCop;
    
    int& ret = cache[alp][cop];
    if(ret != 0) return ret;
    ret = 1e9;
    
    // 문제 풀이
    for(vector<int> v : problems) {
        if(alp < v[0] || cop < v[1]) continue;
        ret = min(ret, solve(alp + v[2], cop + v[3], problems) + v[4]);
    }
    
    // 공부
    ret = min(ret, solve(alp + 1, cop, problems) + 1);
    ret = min(ret, solve(alp, cop + 1, problems) + 1);
    
    return ret;
}

int solution(int alp, int cop, vector<vector<int>> problems) {
    for(vector<int> v: problems) {
        maxAlp = max(maxAlp, v[0]);
        maxCop = max(maxCop, v[1]);
    }
    
    return solve(alp, cop, problems);
}
0%