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

📙 1. 문제

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

문제 설명

풀이 1 : 내 풀이

풀이 과정

1. problems배열을 순환하며 [0], [1] 즉 alp_req와 cop_req가 가장 큰 값을 찾는다.

2. 내 알고력과 코딩력이 필요한 최대 점수를 넘어설 수 있기에, 문제의 필요한 최대 점수를 targetAlp와 targetCop에 각각 저장한다.

3. 2차원 배열 visit를 만든다. 이는 현재 가진 코딩력과 알고력을 가지기 위한 시간의 최솟값을 저장하는 배열이다.

4. 모든 경우를 탐색하기 위해 DFS를 돌린다. 인자 : alp, cop, cnt, problems이다.

4.1. 만약, 현재 내 알고력알고력 >= targetAlp이거나, 내 코딩력 > targetCop라면 내 알고력 및 코딩력을 targetAlp, targetCop에 맞춘다. 이는 DFS 종료 이후 visit배열에서 찾을 수 있도록 하기 위함이다.

4.2. 만약 현재 알고력과 코딩력을 가지기 위한 시간 (즉, visit [a][c])이 현재 시간 이하라면, 종료한다. 현재 시간이 더 작다면, 계속 이어나간다.

4.3. 4.1과 4.2에 해당하지 않았다면, 현재 가진 a와c,cnt는 지금까지의 a와 c의 경우의 수 중 최솟값이다. 그래서 visit [a][c]를 업데이트해 준다. : visit [a][c] = Math.min(visit [a][c], cnt)

4.4. 풀 수 있는 문제라면 : a>=problems[i][0] && c>=problems [i][1], 문제를 풀 때 증가하는 알고력과 코딩력을 더하여 DFS를 또 돌립니다 : DFS(a+problems [i][2], c+problems [i][3], cnt+problems [i][4], problems)

4.5. 1문제를 공부하여 풀었을 때 DFS도 돌린다.

let targetAlp = 0;
let targetCop = 0;
let visit = [];
function solution(alp, cop, problems) {
    let answer = 0;
    for(let i=0; i<problems.length; ++i){
        targetAlp = Math.max(targetAlp, problems[i][0]);
        targetCop = Math.max(targetCop, problems[i][1]);
    }
    for(let i=0; i<151; ++i){
        let temp = [];
        for(let j=0; j<151; ++j){
            temp.push(987654321);
        }
        visit.push(temp);
    }
    DFS(alp, cop, 0, problems);
    answer = visit[targetAlp][targetCop];
    return answer;
}
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);    
}

 

---

🤔 2. 느낀 점

이 문제는 매우 어려웠고, 해결하는데 상당한 시간을 소요하였다. 처음에는 효율성 테스트를 고려해 모든 가능성을 DFS나 BFS로 탐색하는 것이 적절하지 않다고 판단하였다. 그러나 내가 원래 알고 있던 DFS와는 다른 방식이 필요했다.

문제는 탐색을 통해 해결할 수 있었다. 각 문제를 푼 경우(case)마다 DFS를 실행하고, 그다음엔 각각의 경우에 대해 알고리즘 능력을 1 증가시킨 경우와 코딩 능력을 1 증가시킨 경우를 고려하였다. 그러고 나서, 각 경우에 대한 정보를 2차원 방문 배열에 업데이트했다.

이 방식은 상당히 참신하고 독특했다.

 

🤩 3. 한 번 더 짚고 갈 점

참신한 아이디어가 바로 떠오르지 않는다면, 지금 떠오른 알고리즘보다 시간 효율성이 뛰어난 방법이 떠올지 않는다면 일단 내가 생각한 방식대로 문제를 해결해 보는 것이 좋다. 

이때 시간 효율성은 잠시 떠나 두는 것이 중요하다.