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

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

프로그래머스

<풀이>

1. 알고력, 코딩력, 문제들을 입력받는다.

2. 문제들을 풀며 알고력, 코딩력을 향상시킨다.

3. 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 반환한다.

 

<해법>

1. 문제를 접근해 나가는 방법(저가 문제를 풀었던, 지극히 개인적인 방법입니다.)

=>

(1) '코딩문제를 어떤 순서로 풀어야할까?'를 먼저 고민해야합니다. 내 알고력과 코딩력에 가장 근접한 문제? 아닙니다. 알고력과 코딩력을 1시간 당으로 계산해서 가장 많이 올려줄 수 있는 문제? 아닙니다. 여러 방법을 생각해보면 모두 아니라는 것을 알 수 있습니다. 그렇다면, 남은 것은 모든 경우를 해보는 방법(브루트포스) 밖에 없습니다.

 

(2) 효율성은 일단 생각하지 않고, 정확성에만 초점을 둔 채 재귀를 이용해 구현합니다.

 

(3) 정확성 부분을 모두 통과가 되었다면, 어떻게 효율성을 높일지 생각해야합니다. 재귀를 이용한 브루트포스이므로 가장 먼저 메모이제이션을 떠올릴 수 있습니다. 따라서, 해당 코드에 메모이제이션을 추가하여 완성합니다.

---

사실... 저는 정확성 테스트 케이스 제한사항에 있는 '1 <= problems의 길이 <= 6'을 보고 재귀를 이용한 브루트포스를 떠올렸습니다. 그리고, 바로 효율성은 메모이제이션을 떠올릴 수 있었습니다. 위에 해법을 거창하게 써놨지만, 결국 저는 꼼수로 풀었습니다ㅜㅜ.

 

정확성 코드와 효율성 코드를 모두 올리겠습니다. 두 개의 차이점을 보시면서, 메모이제이션을 느끼셨으면 좋겠습니다.

 

- 정확성 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#define INF 987654321
 
using namespace std;
 
vector<vector<int>> problems;
int maxAlp, maxCop;
int answer;
 
int solveProblems(int alp, int cop) {
 
    //종료조건
    if (alp >= maxAlp && cop >= maxCop) {
        return 0;
    }
 
    int ret = INF;
 
    for (int i = 0; i < problems.size(); i++) {
        //문제를 풀 수 있는 경우
        if (alp >= problems[i][0] && cop >= problems[i][1]) {
 
            //문제를 풀 필요가 없는 경우
            //(1) alp가 maxAlp를 넘었는데, 문제가 cop를 올려주지 못할 경우
            if (alp >= maxAlp && problems[i][3] == 0) {
                continue;
            }
 
            //(2) cop가 maxCop를 넘었는데, 문제가 alp를 올려주지 못할 경우
            if (cop >= maxCop && problems[i][2] == 0) {
                continue;
            }
            
            //재귀
            ret = min(ret, 
                      solveProblems(alp + problems[i][2], cop + problems[i][3]) + problems[i][4]);
        }
    }
 
    return ret;
}
 
int solution(int alp, int cop, vector<vector<int>> problems_given) {
 
    //초기화
    problems = problems_given;
    problems.push_back({ 0,0,1,0,1 });
    problems.push_back({ 0,0,0,1,1 });
    maxAlp = 0;
    maxCop = 0;
    answer = -1;
 
    /* 해법 */
    //1. problems의 alp, cop 최댓값 구하기
    for (int i = 0; i < problems_given.size(); i++) {
        if (problems_given[i][0] > maxAlp) {
            maxAlp = problems_given[i][0];
        }
        if (problems_given[i][1] > maxCop) {
            maxCop = problems_given[i][1];
        }
    }
 
    //2. 브루트포스(재귀)
    answer = solveProblems(alp, cop);
 
    //반환
    return answer;
}

 

- 효율성 코드

#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iostream>
#define INF 987654321
 
using namespace std;
 
vector<vector<int>> problems;
int maxAlp, maxCop;
int cache[151][151];
int answer;
 
int solveProblems(int alp, int cop) {
 
    //캐시 크기 벗어남 방지
    if (alp > maxAlp) {
        alp = maxAlp;
    }
    if (cop > maxCop) {
        cop = maxCop;
    }
 
    //alp, cop가 최대치 달성됐을 경우
    if (alp == maxAlp && cop == maxCop) {
        return 0;
    }
 
    int& ret = cache[alp][cop];
 
    //메모이제이션
    if (cache[alp][cop] != -1) {
        return ret;
    }
 
    ret = INF;
 
    for (int i = 0; i < problems.size(); i++) {
 
        //문제를 풀 수 있는 경우
        if (alp >= problems[i][0] && cop >= problems[i][1]) {
 
            //문제를 풀 필요가 없는 경우
            //(1) alp가 maxAlp가 되었는데, 문제가 cop를 올려주지 못할 경우
            if (alp == maxAlp && problems[i][3] == 0) {
                continue;
            }
 
            //(2) cop가 maxCop가 되었는데, 문제가 alp를 올려주지 못할 경우
            if (cop == maxCop && problems[i][2] == 0) {
                continue;
            }
 
            //재귀
            ret = min(ret, 
                      solveProblems(alp + problems[i][2], cop + problems[i][3]) + problems[i][4]);
        }
    }
 
    return ret;
}
 
int solution(int alp, int cop, vector<vector<int>> problems_given) {
 
    //초기화
    problems = problems_given;
    problems.push_back({ 0,0,1,0,1 });
    problems.push_back({ 0,0,0,1,1 });
    maxAlp = 0;
    maxCop = 0;
    memset(cache, -1, sizeof(cache));
    answer = -1;
 
    /* 해법 */
    //1. problems의 alp, cop 최댓값 구하기
    for (int i = 0; i < problems_given.size(); i++) {
        if (problems_given[i][0] > maxAlp) {
            maxAlp = problems_given[i][0];
        }
        if (problems_given[i][1] > maxCop) {
            maxCop = problems_given[i][1];
        }
    }
 
    //2. 메모이제이션
    answer = solveProblems(alp, cop);
 
    //반환
    return answer;
}

 

메모이제이션에 대해 알아볼 수 있는 문제였습니다.