2022 KAKAO TECH INTERNSHIP | 코딩 테스트 공부

문제를 읽으면서 그리디 알고리즘의 냄새가 났다. 

주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단 시간을 구하는 문제이다. 

 

해결해야하는 문제는 (초기 알고력, 초기 코딩력) 상태에서 시작해 (목표 알고력, 목표 코딩력) 상태에 도달하는 최단시간을 구하는 문제이다.

 

이때, 목표 알고력을 넘는 알고력이나 목표 코딩력을 넘는 코딩력은 구현 방법에 따라 시간초과나 세그먼트 폴트와 같이 예상치 못한 런타임 오류를 일으킬 수 있다고 한다.(해설)

 

이 문제는 2차원 동적계획법 DP로 풀이가 가능하다. DP를 아래와 같이 정의한다. 

 

dp[i[j]: 알고력 i , 코딩력 j 상태에 도달하는데 필요한 최단 시간

 

이렇게 DP배열을 정의하면 문제에서 요구하는 답은 dp[목표 알고력][목표 코딩력]이다. dp[초기 알고력][초기 코딩력] = 0으로 기저 사례를 잡고 나머지 DP 배열의 값은 무한 (적당히 큰 값)으로 초기화한 후 다음과 같은 방법으로 DP 배열을 업데이트 한다.

 

- 알고리즘을 공부하여 알고력을 1 높이는 경우: dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)

- 코딩을 공부하여 코딩력을 1 높이는 경우: dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)

- 문제 하나를 선택하여 알고력과 코딩력을 모두 높이는 경우: dp[i+alp_rwd][j+cop_rwd] = min(dp[i+alp_rwd][j+cop_rwd], dp[i][j]+cost) (단, i >= alp_req이고 j >= cop_req)

 

초기 알고력 <= i <= 목표 알고력, 초기 코딩력 <= j <= 목표 코딩력인 모든 (i, j)에 대해서 dp[i][j] 값을 업데이트 해야하므로, 시간 복잡도는 O(목표 알고력 * 목표 코딩력 * problems 배열의 길이)가 된다. 

 

이 방법 이외에도 그래프로 모델링하여 최단 거리를 찾는 문제 (다익스트라)로 바꾸어 해결하는 풀이도 존재한다고 한다.