Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 코딩 테스트 공부

[코딩 테스트 공부]

접근 과정

• 오늘의 문제는 주제를 보지 않고 풀어보았다.

그리디?

• 가장 처음 들었던 생각은 그리디가 아닐까 싶었다.
• 하지만 풀 수 있는 problems에 대하여 cost당 각 문제를 풀 때 얻게 되는 alp_rwd, cop_rwd 가 높은 순으로 그리디하게 풀어나간다고 했을 때
  • 당연하지만, 풀 수 있는 문제들이 있을 때 문제를 푸는 게 항상 이득이 아니다. $alp_{rwd}, cop_{rwd} \ge 0$이기 때문에 공부로 alp, cop를 올리는 게 더 좋은 상황을 고려해주어야 한다.
  • 단순히 $\max(1, \frac{alp_{rwd}+cop_{rwd}}{cost})$로 계산해서도 안 된다. 단위 시간당 능력치를 올릴 수 있는 것이 아니고 cost 전체를 들여야 능력치를 얻을 수 있다.
  • 모든 문제를 풀 수 있게 되는 alp, cop에 근접해갈 경우 cost당 얻는 능력치가 높은 순이 아닌 경사하강법과 유사한 느낌으로 cost가 상대적으로 덜 들면서 필요한 만큼만 능력치를 얻는 게 이득인 경우 또한 고려해주어야 한다.
  • 현재 상황에서 $alp_{rwd}$가 높은 문제를 골라야 최적의 선택일지, $cop_{rwd}$가 높은 문제를 골라야 최적의 선택일지 불분명하다.
  • 이는 현재의 선택이 전체 최적해로 이어짐을 보장하지 않는다는 것을 의미한다. (최적 부분 구조를 만족하지 않는다.)

DP

• 그리디가 아니라는 생각이 들 때 쯤 Coin DP, 0-1 Knapsack DP가 떠올랐다. 돌아보니 핵심적인 아이디어는 Coin DP였고, 이를 구체화할 수 있던 건 0-1 knapsack DP인 것 같다.

Coin DP

• problems를 순회하면서 현재의 alp, cop로 풀 수 있는 문제들의 alp_rwd, cop_rwd를 $rwd = [(alp_{rwd}, cop_{rwd})]$ 꼴로 저장해 놓는다. 이는 Coin DP 문제에서 현재 금액보다 작은 단위의 동전들에 대해 dp table을 갱신하는 것과 유사하다.
• 모든 문제를 풀 수 있게 되는 알고력과 코딩력을 구해놓는다. 이를 $alp_{goal}, cop_{goal}$이라 하자. 초기 alp, cop부터 시작해서 모든 rwd에 대해 고려하면서 다음으로 풀 수 있는 문제들까지 걸리는 시간을 계산한다.
  • 여기서 발생한 문제는 “다음으로” 라는 생각이 불분명했다. (이 쯤에서 또 혼자 함정에 빠진 것이다,,,) 그리디가 안되는 이유와 유사하다. alp_req 또는 cop_req를 오름차순으로 정렬해서도 안 되고(cost를 고려해주어야 함), … 아무튼 이 또한 현재의 선택이 전체 최적해로 이어짐을 보장하지 않는다.
  • 이 때쯤 일단 한 번에 계산하려고 하지 말고 나이브하게 가능한 모든 경우에 대해 생각해보아야 겠다는 생각이 들었는데, 0-1 knapsack DP 가 떠올랐다.

0-1 Knapsack DP

• 문제를 푸는 데에 있어서 직접적인 역할을 한 건 아니고, 그냥 knapsack DP table의 구조만 본따서 dp table을 설계할 수 있었다.

풀이

• $dp[i][j]$를 초기 알고력 $alp$, 초기 코딩력 $cop$에서 시작하여 알고력 $i$, 코딩력 $j$을 얻기까지의 최단시간이라고 하자.

• $dp$의 크기는 모든 문제들을 풀 수 있는 알고력과 코딩력의 값으로 잡았다. 이는 $\max(alp_{req}, alp)+1 \times \max(cop_{req}, cop)+1$ 이다.

• 먼저, 문제풀이로 알고력 또는 코딩력을 높이는 것이 아닌 시간당 1씩 증가하는 알고리즘 공부 또는 코딩 공부만 하는 상황으로 $dp[i][j]$를 초기화할 수 있다.

  $dp[i][j] = \max(i-alp, 0)+\max(j-cop, 0)$
  • 이 때, 초기 알고력 $alp$가 $i$보다 크거나 초기 코딩력 $cop$가 $j$보다 클 경우 해당 공부를 하지 않아도 $i$ 또는 $j$를 얻은 상황이라고 볼 수 있으므로, 이 때는 해당 값을 $0$으로 생각한다.

• 초기 알고력 $alp$, 초기 코딩력 $cop$에서 시작하여, 공부하는 것으로 알고력 $i$, 코딩력 $j$를 얻기까지의 최단시간을 계속해서 갱신한다. python에서, 이는 다음과 같은 점화식으로 나타낼 수 있다.

  $dp[i][j] = \min(dp[i][j], dp[i-1][j]+1, dp[i][j-1]+1)$
  • 초기 알고력 또는 초기 코딩력이 0일 경우 $i-1$ 또는 $j-1$이 $-1$이 되어 정상적인 값으로 갱신되지 않을 수 있음이 우려될 수 있는데, dp table의 형태가 왼쪽에서 오른쪽으로, 위에서 아래로 단조증가하는 형태를 갖기 때문에 문제되지 않는다.

• 그리고, 그 때의 알고력 $i$, 코딩력 $j$로 풀 수 있는 모든 문제들에 대해 풀면서 얻은 알고력($i+alp_{rwd})$과 코딩력($j+cop_{rwd})$을 얻기까지 걸린 시간을 갱신해준다.

  • 이 때, $i + alp_{rwd}$가 dp table의 범위를 넘어설 수 있으므로, $\min(i+alp_{rwd}, alp_{goal})$로 설정하고, 같은 이유로 $j+cop_{rwd}$ 또한 $\min(j+cop_{rwd}, cop_{goal})$로 설정한다. 이를 각각 $ni$, $nj$라 하자. 이는 다음 점화식으로 나타낼 수 있다.

    $dp[ni][nj] = \min(dp[ni][nj], dp[i][j]+cost)$

Solution 1. DP $O(M_{alp} \cdot M_{cop} \cdot |P|)$

def solution(alp, cop, problems):
    alp_goal = max(max(p[0] for p in problems), alp)
    cop_goal = max(max(p[1] for p in problems), cop)
    
    dp = [[max(i-alp, 0)+max(j-cop, 0) for j in range(cop_goal+1)] for i in range(alp_goal+1)]

    for i in range(alp, alp_goal+1):
        for j in range(cop, cop_goal+1):
            dp[i][j] = min(dp[i][j], dp[i-1][j]+1, dp[i][j-1]+1)
            for ri, rj, di, dj, cost in problems:
                if i >= ri and j >= rj:
                    ni, nj = min(i+di, alp_goal), min(j+dj, cop_goal)
                    dp[ni][nj] = min(dp[ni][nj], dp[i][j]+cost)

    return dp[-1][-1]

Solution 2. DP using Dictionary

from heapq import heappop, heappush

def solution(alp, cop, problems):
    mx_alp, mx_cop = alp, cop
    for p in problems:
        if p[0] > mx_alp: mx_alp = p[0]
        if p[1] > mx_cop: mx_cop = p[1]
    
    dp = {}
    dp[(alp, cop)] = 0

    heap = [(0, alp, cop)]

    while heap:
        t, i, j = heappop(heap)
        if i >= mx_alp and j >= mx_cop: return t
        if dp.get((i, j), float('inf')) < t: continue

        for ri, rj, di, dj, cost in problems:
            if i >= ri and j >= rj:
                ni = min(i+di, mx_alp)
                nj = min(j+dj, mx_cop)
                nt = t+cost
                if dp.get((ni, nj), float('inf')) > nt:
                    dp[(ni, nj)] = nt
                    heappush(heap, (nt, ni, nj))
        
        if i < mx_alp:
            ni = i+1
            nt = t+1
            if dp.get((ni, j), float('inf')) > nt:
                dp[(ni, j)] = nt
                heappush(heap, (nt, ni, j))
        
        if j < mx_cop:
            nj = j+1
            nt = t+1
            if dp.get((i, nj), float('inf')) > nt:
                dp[(i, nj)] = nt
                heappush(heap, (nt, i, nj))
    
    return dp[(mx_alp, mx_cop)]

• 시간복잡도 계산을 정확히 어떻게 해야할 지 모르겠어서 코드만 올리고 포스팅을 미뤘었다. 먼저 동작 과정에 대해 설명하고, 시간복잡도 계산 부분은 조금 더 미루겠다.
• $M_{alp}$, $M_{cop}$를 구하는 과정은 사실 Solution 1. 과 같다. 단지 반복문 한 번으로 바꿨을 뿐이다.
• $dp$의 정의도 Solution 1. 과 같다. $dp[(i, j)]$를 초기 알고력 $alp$, 초기 코딩력 $cop$에서 시작하여 알고력 $i$, 코딩력 $j$을 얻기까지의 최단시간이라고 하자.
• 그리고, 우선순위 큐에는 $(t, i, j)$ 형태로 push한다. 여기에서 $t$는 해당 알고력 $i$, 코딩력 $j$를 얻기까지 걸린 시간을 의미하고, python의 heap은 첫 번째 원소의 값을 가장 먼저 고려하여 그 값이 가장 작은 원소가 맨 앞에 오도록 관리한다.
  • 여기에서, 가장 작은 $t$값을 가진 상태를 먼저 꺼내어 처리하는 이유는 그 상태를 기반으로 나아가 다른 상태에 대해 더 작은 $t$값으로 갱신할 여지가 높기 때문이다. 이 부분이 heap을 이용하는 주된 이유이며,
  • 같은 상태 $(i, j)$에 대하여 이미 heap에 여러 $t$가 push되어있다더라도, if dp.get((i, j), float('inf')) < t: continue 구문을 통해 아래의 구문들을 실행하지 않게 되기 때문에 이 또한 주요 최적화 포인트이다. 이 구문이 실행될 때마다 $O(\lg (|P|+2))$의 시간복잡도가 save되는 셈이다.

---

Memo

• Dijkstra로도 풀 수 있다고 한다. 아직 몰라서… 공부한 뒤 꼭 다시 풀어보아야 겠다.

---

99클럽 3기 회고 를 내일중으로 작성하려고 한다.

혹시나 이 글을 봐주시는 분이 계시다면, 그동안 정말 감사했습니다 🥹😊