[Algorithm] 프로그래머스 - 코딩테스트 연습 (Python)

 

몇 주 전에 기업 입사를 위한 코딩테스트를 응시한 적이 있다.

총 3문제 중 2문제는 금방 풀어서 1 문제만 풀면 되는 상황이었다.

 

혼자 올솔에 대한 행복회로를 돌리면서 한 문제를 계속 고민했는데,

아무리 생각해도 DP인데 DP에 대한 풀이가 익숙지 못해서 결국 풀지 못했다ㅠ

그래서 시험이 끝나고 최대한 비슷한 문제를 열심히 찾았고

이 문제가 비슷한 것 같아서 한 번 풀어보는 김에 블로그에 정리해보려고 한다.

 

 

📕 1. 문제

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

프로그래머스

 

문제에 대해 간단히 설명하면,

모든 문제를 풀 수 있을 만큼 '코딩력'과 '알고력'을 쌓는데 걸리는 '최단 시간'을 구하는 문제이다.

 

2022 카카오 인턴십 코딩테스트에 출제된 문제인 만큼,

문제의 퀄리티도 괜찮고 난이도도 상당히 높기 때문에 풀어보기에 좋은 문제인 것 같다.

 

 

📕 2. 풀이 과정

 

1. 알고력과 코딩력의 최댓값 찾기

문제에서는 모든 문제를 풀 수 있는 '알고력'과 '코딩력'에 도달하는 최소 시간을 구해야 하기 때문에,

알고력과 코딩력의 최댓값을 구해야 한다.

그래서 문제들을 순환하며 max_alp_req과 max_cop_req 값을 갱신해주었다.

 

 

 

 

2. dp 테이블 생성하기

 

알고력과 코딩력을 행과 열로 하는 2차원 DP 테이블을 만들었다.

이후 적절히 큰 값인 1000으로 채워주고,

dp [0][0] 은 0으로 초기화해 주었다.

dp테이블에서dp [i][j]는 알고력 i, 코딩력 j에 도달할 수 있는 최단시간을 의미한다. 

 

 

 

 

3. dp 테이블을 순환하며, 최솟값 갱신하기

 

이후 테이블을 순환하며,

1초 동안 알고력을 1 증가시키는 경우,

1초 동안 코딩력을 1 증가시키는 경우,

문제를 풀어서 알고력과 코딩력을 증가시키는 경우를 비교하며

테이블의 최단시간을 갱신해 주면 된다.

이후 위에서 구한 문제를 모두 풀 수 있는 코딩력, 알고력을 토대로 정답을 구하면 된다.

 

 

이제 DP에 대해 감은 생겨서

어떤 문제가 DP이고 아닌지 문제를 보면 느낌은 오는데

여전히 테이블을 구현하는 건 익숙하지 않아서 어렵다.

그렇지만 뭐 이것도 하다 보면 늘 것 같아서 앞으로도 열심히 해봐야겠다.

 

📕 3. 정답 코드

def solution(alp, cop, problems):
    max_alp_req, max_cop_req = 0,0  
    for problem in problems:
        max_alp_req = max(max_alp_req, problem[0])
        max_cop_req = max(max_cop_req, problem[1])
    
    dp = [[1000] * (max_cop_req+1) for _ in range(max_alp_req+1)]
    alp = min(alp, max_alp_req)
    cop = min(cop, max_cop_req)
    dp[alp][cop] = 0  # dp[i][j] : 알고력 i, 코딩력 j에 도달 할 수 있는 최단시간
    
    for i in range(alp, max_alp_req+1):
        for j in range(cop, max_cop_req+1):
            # 1초 동안 알고력 1 증가
            if i < max_alp_req:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            # 1초 동안 코딩력 1 증가
            if j < max_cop_req:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
            # 문제를 풀어서 알고력, 코딩력 증가
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                if i >= alp_req and j >= cop_req:
                    new_alp = min(i+alp_rwd, max_alp_req)  
                    new_cop = min(j+cop_rwd, max_cop_req)
                    dp[new_alp][new_cop] = min(dp[new_alp][new_cop], dp[i][j] + cost)
    return dp[max_alp_req][max_cop_req]