[프로그래머스/C++] 코딩 테스트 공부

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

https://school.programmers.co.kr/learn/courses/30/lessons/118668

프로그래머스

코딩 테스트 공부

문제

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

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

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

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

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

 

풀이

입출력 예시

 

풀이

 

항상 나를 괴롭히는 DP 문제. 처음에는 문제 하나하나 풀어간다는 생각으로 코드를 작성하다가 무언가 잘못되었다는 생각이 들어 다시 생각을 했다. 분명 문제에도 모든 문제들을 1번 이상 풀 필요가 없다고 되어있는데 문제를 제대로 읽지도 않았나 보다.

 

모든 문제를 풀 필요가 없이, 문제에서 가장 높은 알고력과 가장 높은 코딩력을 찾아 그 값에 맞춰주어야 한다.

 

아래 풀이는 카카오 테크 공식 풀이를 참고하였다.

https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/

 

2차원 dp배열을 하나 선언해준다.

dp[알고력][코딩력] = { { INF, ... } }

 

dp[alp][cop] = 0 으로 초기화시키고, dp[목표 알고력][목표 코딩력]을 구하기 위해 다음 과정들을 거쳐준다.

 

알고력을 i, 코딩력을 j라고 하자. 다음과 같은 과정으로 알고력과 코딩력을 올릴 수 있다.

 

1. 알고리즘 공부로 알고력을 1 올린다.

알고리즘 공부를 통해서는 1의 시간이 필요하다. 따라서, 아래의 식과 같이 비용을 구할 수 있다.

dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1)

 

2. 코딩 공부로 코딩력을 1 올린다.

코딩 공부를 통한 방법도 1의 시간이 필요하다.

dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1)

 

3. 문제를 풀어서 알고력과 코딩력을 올린다.문제를 풀기 위한 조건이 있다. 문제에서 요구하는 알고력과 코딩력이 있어야 그 문제를 풀 수 있다.

if ( alp >= alp_req && cop >= cop_rwd ) {

    dp[i + alp_rwd][j + cop_rwd] = min(dp[i + alp_rwd][j + cop_rwd], dp[i][j] + cost)

}

 

최종적으로 구한 dp[alp_req][cop_req]가 우리가 구하고자 하는 답이 된다.

 

 

1차 풀이(오답)

#include <string>
#include <vector>

using namespace std;

const int INF = 1999999999;

// 모든 문제를 풀 필요가 없이, 가장 높은 알고력과 코딩력을 만들면 된다.
int solution(int alp, int cop, vector<vector<int>> problems) {
    int answer = 0;
    int last = problems.size() - 1;
    int min_time;
    int alp_req = -1;
    int cop_req = -1;
    
    for (int i = 0; i <= last; i++) {
        if (alp_req < problems[i][0]) {
            alp_req = problems[i][0];
        }
        if (cop_req < problems[i][1]) {
            cop_req = problems[i][1];
        }
    }
    
    vector<vector<int>> dp(alp_req + 1, vector<int>(cop_req + 1, INF));
    dp[alp][cop] = 0;
    
    if (alp_req <= alp && cop_req <= cop) {
        return 0;
    }
    
    for (int k = 0; k <= last; k++) {
        for (int i = alp; i <= alp_req; i++) {
            for (int j = cop; j <= cop_req; j++) {
                if (j + 1 <= cop_req) {
                    dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);
                }
                if (i + 1 <= alp_req) {
                    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
                }
                if (i + problems[k][2] <= alp_req && j + problems[k][3] <= cop_req) {
                    if (i >= problems[k][0] && j >= problems[k][1]) {
                        dp[i + problems[k][2]][j + problems[k][3]] = min(dp[i + problems[k][2]][j + problems[k][3]], dp[i][j] + problems[k][4]);
                    }
                }
            }
        }
    }
    
    answer = dp[alp_req][cop_req];
    return answer;
}

 

수정 1. 배열 범위

alp 또는 cop의 초기값이 alp_req 또는 cop_req 보다 큰 경우를 고려해야 한다. (정확성, 효율성 10번 케이스로 추정)

 

수정 2. 증가한 알고력(또는 코딩력)이 alp_req(또는 cop_req)를 넘어설 때

이 경우를 처음에는 배제했다. 하지만, 알고력(또는 코딩력)이 alp_req(또는 cop_req)의 값을 넘어서는 경우도 생각해주어야 한다. 무조건 요구 알고력에 맞춰야 하는 문제가 아니었기 때문..

초과하는 경우를 일일이 고려해줄 수는 없기에, 이 경우는 그냥 alp_req(또는 cop_req)의 값을 넘어가기 시작하면 항상 alp_req(또는 cop_req)로 고정되게 해 주었다.

 

최종 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

const int INF = 1999999999;

// 모든 문제를 풀 필요가 없이, 가장 높은 알고력과 코딩력을 만들면 된다.
int solution(int alp, int cop, vector<vector<int>> problems) {
    int answer = 0;
    int last = problems.size() - 1;
    int min_time;
    int alp_req = -1;
    int cop_req = -1;
    
    for (int i = 0; i <= last; i++) {
        if (alp_req < problems[i][0]) {
            alp_req = problems[i][0];
        }
        if (cop_req < problems[i][1]) {
            cop_req = problems[i][1];
        }
    }
    
    if (alp_req <= alp && cop_req <= cop) {
        return 0;
    }
    
    vector<vector<int>> dp(alp_req + 1, vector<int>(cop_req + 1, INF));
    
    if (alp > alp_req) {
        alp = alp_req;
    }
    if (cop > cop_req) {
        cop = cop_req;
    }
    
    dp[alp][cop] = 0;
    
    
    for (int i = alp; i <= alp_req; i++) {
        for (int j = cop; j <= cop_req; j++) {
            if (j + 1 <= cop_req) {
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);
            }
            if (i + 1 <= alp_req) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
            }
            for (int k = 0; k <= last; k++) {
                if (i >= problems[k][0] && j >= problems[k][1]) {
                    // 알고력 요구치(또는 코딩력 요구치)를 넘어서면 최댓값으로 고정
                    dp[min(i + problems[k][2], alp_req)][min(j + problems[k][3], cop_req)] = min(dp[min(i + problems[k][2], alp_req)][min(j + problems[k][3], cop_req)], dp[i][j] + problems[k][4]);
                }
            }
        }
    }
    
    answer = dp[alp_req][cop_req];
    return answer;
}