[Python] 2022 KAKAO TECH INTERNSHIP : 코딩 테스트 공부 / DP(Dynamic Programming: 동적 계획법)

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

DP(Dynamic Programming: 동적 계획법)

정의

DP, 즉 다이나믹 프로그래밍은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제 해결 패러다임으로 볼 수 있다.
큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다고 하여 '기억하며 풀기'라고 불리기도 한다.

DP를 쓰는 이유

일반적인 재귀 방식 또한 DP와 매우 유사하지만 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 차이점이 있다.
값을 저장해두고 재사용 한다면 불필요한 계산을 반복할 필요가 없어 시간복잡도를 줄일 수 있다.
O(n^2) -> O(f(n))으로 개선(다항식 수준으로, 문제에 따라 다름.)

문제 풀이

이 문제는 DP(Dynamic Programming: 동적 계획법)을 이용해서 풀어야 한다.

1. 작은 문제들을 저장할 배열을 초기화한다

• 최단시간을 찾아야 하기 때문에 배열의 값은 양의 무한대로 지정.

2. 문제에서 최대 필요 alp와 cop를 변수에 넣어준다.
   2-1. 처음부터 주어진 alp와 cop가 최대 필요 alp & cop보다 클 수도 있기 때문에 비교해준다.

3. 주어진 alp, cop를 시작으로 최대 필요 alp, cop까지 for문을 돌린다.
   3-1. alp나 cop가 부족할 경우 1씩 추가해주고, dp 값과 비교하여 더 작은 값을 dp에 넣어준다.
   3-2. 문제를 풀 수 있을 경우 문제를 풀고, dp 값과 비교하여 더 작은 값을 dp에 넣어준다.

4. dp[최대 필요 alp][최대 필요 cop] 값을 return 해준다.

답

def solution(alp, cop, problems):
    max_alp, max_cop = 0, 0
    # 문제 풀이 2번
    for a,b,c,d,e in problems:
        max_alp = max(max_alp, a)
        max_cop = max(max_cop, b)
    INF = float('inf')
    dp = [[INF] * (max_cop + 1) for _ in range(max_alp + 1)] # 문제 풀이 1번
    # 문제 풀이 2-1번
    alp = min(alp, max_alp)
    cop = min(cop, max_cop)
    dp[alp][cop] = 0
    # 문제 풀이 3번
    for i in range(alp, max_alp+1):
        for j in range(cop, max_cop+1):
        	# 문제 풀이 3-1번
            if i < max_alp:
                dp[i+1][j] = min(dp[i][j] + 1, dp[i+1][j])
            if j < max_cop:
                dp[i][j+1] = min(dp[i][j] + 1, dp[i][j+1])
            # 문제 풀이 3-2번  
            for a,b,c,d,e in problems:
                if i >= a and j >= b:
                    next_alp, next_cop = min(max_alp, i+c), min(max_cop, j+d)
                    dp[next_alp][next_cop] = min(dp[next_alp][next_cop], dp[i][j] + e)
    # 문제 풀이 4번
    return dp[max_alp][max_cop]