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

---

[Challenger] Maximum Profit in Job Scheduling

[Maximum Profit in Job Scheduling]

접근 과정

• 문제를 이해하는 데에는 수월했으나, 어떻게 접근해야할지 펜을 들기까지의 시간이 오래 걸렸던 것 같다.
• 이 문제를 풀면서 이전에 풀어보았던 두 문제가 생각났고, 결과적으론 두 번째로 언급할 문제를 살짝 비틀어서 풀 수 있게 됐다. 이 두 문제의 주요 접근 과정에 대한 스포일러가 포함되어 있으니 주의해 주세요!!!

BOJ 1931. 회의실 배정

[BOJ 1931. 회의실 배정]

• 정말 유명한 그리디 문제인데, (스포) 회의가 끝나는 시간을 기준으로 정렬을 하고 나면 최대한 많은 회의를 할 수 있게 된다.
  • 매 순간 가장 빨리 끝나는 회의를 선택하는 것이 결국 최적해가 되는 그리디 문제이다.
• 이 문제가 가장 먼저 떠올랐다. 달리 다른 생각이 떠오르지 않아서 일단 주어진 startTime, endTime, profit을 묶어서 끝나는 시간을 기준으로 정렬을 해 보았는데,
  • 아무리 생각해 보아도 이 문제는 그리디로 풀 수 없겠다는 생각이 들었다. 회의실 배정 문제에서 각 회의에 가중치가 포함된 느낌? 이라, 매 순간 가장 빨리 끝나는 job을 선택하는 것이 최적해로 이어짐을 보장할 수 없다.
  • 아주 쉽게 반례를 떠올릴 수 있다. endTime이 빠른 순으로 정렬해서 그리디하게 최대한 많은 job을 선택했을 때, endTime이 느린 job이 endTime이 빠른 job을 포기해도 될 만큼 profit이 높을 수 있다.
  • 따라서 최적 부분 구조를 갖지 못하므로 그리디로 접근할 수는 없다. 하지만 순간순간 optimal한 선택을 기록해 놓고(memoization), 계속해서 갱신해나가는 DP를 떠올릴 수 있었다.

BOJ 15486. 퇴사 2

[BOJ 15486. 퇴사 2]

• DP를 떠올리고 나니 이 문제를 풀었던 기억이 스쳐지나갔다. 주어진 기간(시간) 내에 최대한의 이익을 위해 겹치지 않는 작업들을 그 작업의 수익에 따라 적절하게 선택하여 이익을 극대화하는 문제이다.
• startTime 또는 endTime을 정렬해 주고 나면(고정해 주고 나면), 이 문제와 완전히 유사한 구조가 되어버린다. (스포) 이 문제에서는 1일, 2일, 3일과 같이 $i+T_i$ 로 기간을 다루어 갱신을 했지만,
  • 오늘의 문제에서는 현재 작업이 끝난 이후에 시작하는(그 작업의 끝나는 시간보다 크거나 같은) 가장 빠른 첫 작업을 찾아서 갱신을 하거나(startTime을 기준으로 정렬했을 때), 현재 작업이 시작되기 이전 가장 나중의 작업을 찾아서 갱신을 하면 된다(endTime을 기준으로 정렬했을 때).
• 그렇다면 startTime과, endTime중 어떤 걸 기준으로 정렬해야 할까? 위에서 잠깐 언급했지만 구현만 다를 뿐 상관이 없다.
  1. 작업을 역순으로 순회하는 경우를 생각해 보자.
     • $dp[i]$를 $i$번째 작업부터 마지막 작업까지 고려했을 때의 최대 이익이라고 하자.
     • 각 단계에서 현재 작업을 선택하거나, 선택하지 않는 두 가지 옵션 중 최댓값만을 선택하면 된다. 점화식은 다음과 같이 나타낼 수 있다.
       $dp[i] = \max(dp[i+1], profit[i]+dp[next])$
     • 이를 위해 startTime을 기준으로 정렬하고, 그 작업이 끝나는 시간 이후의 첫 작업을 찾는다. 이 때, $O(n)$으로 탐색하는 것이 아닌, startTime이 정렬되어있다는 점을 생각하면 이분 탐색을 이용하여 $O(\lg n)$으로 아주 빠르게 그 작업을 찾을 수 있게 된다.
       • 현재 작업의 종료 시간 이후의 첫 작업을 찾기 위해 Lower bound를 이용한다.
  2. 작업을 순방향으로 순회하는 경우를 생각해 보자.
     • $dp[i]$를 처음 작업부터 $i$번째 작업까지 고려했을 때의 최대 이익이라고 하자.
     • 각 단계에서 현재 작업을 선택하거나, 선택하지 않는 두 가지 옵션 중 최댓값만을 선택하면 된다. 점화식은 다음과 같이 나타낼 수 있다.
       $dp[i] = \max(dp[i-1], profit[i] + dp[prev])$
     • 이를 위해 endTime을 기준으로 정렬하고, 현재 작업의 startTime 이전에 끝나는 마지막 작업을 찾는다. 이 때, $O(n)$으로 탐색하는 것이 아닌, endTime이 정렬되어있다는 점을 생각하면 이분 탐색을 이용하여 $O(\lg n)$으로 아주 빠르게 그 작업을 찾을 수 있게 된다.
       • 현재 작업의 시작 시간 이전의 마지막 작업을 찾기 위해 Upper bound를 이용한다.
  • 여기서, DP table에 아무것도 선택하지 않은 상태인 [0]을 추가로 포함시켜 주면 경계 조건을 깔끔하게 처리할 수 있게 된다.
  • 위 두 방법은 DP의 ‘최적 부분 구조’와, ‘반복되는 부분 문제’의 특성을 아주 잘 활용할 수 있다.

Solution 1-1. 역방향 순회 $O(2n \lg n)$

def bs_lb(a, v):
    lo, hi = 0, len(a)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if a[mid][0] < v:
            lo = mid+1
        else:
            hi = mid-1
    
    return lo

def jobScheduling(startTime, endTime, profit):
    schedules = sorted(zip(startTime, endTime, profit), key=lambda x: x[0])
    n = len(schedules)

    dp = [0]*(n+1)
    for i in range(n-1, -1, -1):
        s, e, p = schedules[i]
        nxt = bs_lb(schedules, e)
        dp[i] = max(dp[i+1], p + dp[nxt])
        
    return dp[0]

Solution 1-2. 순방향 순회 $O(2n \lg n)$

def bs_ub(a, v):
    lo, hi = 0, len(a)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if a[mid][1] <= v:
            lo = mid+1
        else:
            hi = mid-1
    
    return lo

def jobScheduling(startTime, endTime, profit):
    schedules = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    n = len(schedules)

    dp = [0]*(n+1)
    for i in range(1, n+1):
        s, e, p = schedules[i-1]
        prev = bs_ub(schedules, s)
        dp[i] = max(dp[i-1], p + dp[prev])
        
    return dp[n]

---

Memo

• Greedy vs DP에 대한 감을 마침내(?) 제대로 정립할 수 있게 된 문제인 것 같다. 그동안도 어렴풋이 알고는 있었지만 이 문제를 통해 뭔가 피부로 느낀듯한 느낌이다. 라이브 세션이 큰 도움이 되었다!
• 문제를 풀어나간 흐름이 정말 큰 도움이 됐다. Greedy, DP, Sort, Binary Search까지… 꼭 다시 곱씹으면서 풀어봐야겠다는 생각이 드는 문제였다.