오늘은 스케줄링과 관련한 문제를 가져왔습니다. 스케줄링과 관련한 문제는 시간관리와 이익 최대화라는 중요한 개념을 반영하고 있어서, 효율적인 알고리즘을 설계하는 능력을 시험하는 데 아주 적합한 문제입니다.
저는 이 문제를 봤을 때, 백준의 '강의실배정' 문제가 생각났습니다. 문제 푸는 방식은 다르긴 하더라도, 이러한 시간 스케줄링 문제에는 항상 'heapq' 를 사용해서 접근하는 듯 했습니다.
해당 문제는 여러 개의 작업이 주어지고, 각 작업은 '시작시간', '종료시간' , '이익' 리스트로 구성됩니다. 목표는 겹치지 않는 작업들을 선택하여 얻을 수 있는 최대 수익을 계산하는 것 입니다. 즉, 이 문제의 핵심은 모든 가능한 작업 조합 중에서 최적의 조합을 찾는 것이죠.
단순한 브루트포스 알고리즘으로 풀기에는 최대 이익을 구하는 문제에서는 시간초과가 날 수도 있고 잘못된 답으로 결론날 수도 있기 때문에 뭔가 DP 를 활용하는 것 같기도 합니다.
이 문제를 해결하기 위해, 먼저 작업들을 '시작 시간'에 따라 정렬해야 합니다. 이렇게 하면, 각 작업을 순차적으로 고려할 수 있기 때문입니다. 그 후, 각 작업에 대해 현재까지의 최대 수익을 계산하는데, 이 과정에서 중요한 것은 이미 고려된 작업들 중에서 현재 작업과 겹치지 않으면서 최대 수익을 제공하는 작업을 효율적으로 찾는 것입니다. 이를 위해, 저는 heap 자료구조를 사용했습니다.
※ 그럼 왜 heap 자료구조를 사용했는지 설명하겠습니다.
1. 효율적인 최소/최대 관리 → heap 은 최소값(or 최대값)에 빠르게 접근할 수 있도록 설계된 자료구조입니다. 해당 문제에서의 제한 조건을 보면, 각 작업의 수는 '최대 5* 10^4' 까지의 범위를 허용하고 있습니다. 따라서, 각 작업의 시작 시간 이전에 끝나는 작업들 중 최대 수익을 쉽게 찾을 때, 시간복잡도를 고려해야 합니다. heap 을 사용하면, 이러한 작업을 O(logN) 시간 안에 찾을 수 있습니다.
2. 동적 업데이트 → 작업들을 순회하면서, 새로운 작업을 힙에 추가하거나, 더 이상 고려하지 않아도 되는 작업을 힙에서 제거할 수 있어야 합니다. heap 은 이러한 동적인 추가 및 제거 작업을 'O(log N)' 시간 안에 수행할 수 있습니다.
3. 시간 복잡도 최적화 → 이 문제를 해결하는 데 있어서, 작업들을 정렬한 후 각 작업을 한 번씩만 처리하면 됩니다. heap을 사용하면, 각 작업에 대해 이전 작업들을 효율적으로 관리하면서 전체적인 시간 복잡도를 O(N logN) 으로 유지할 수 있습니다.
즉, heap 자료구조는 이런 유형의 문제에서 계산하는 과정을 효율적으로 만들어 줍니다. heap 을 사용함으로써, 각 작업에 대한 최적의 결정을 빠르게 내릴 수 있으므로, 전체적인 알고리즘 효율성을 높이는 장점이 있는 것이죠.
그럼 코드를 살펴보면서, 풀이를 설명하겠습니다.
class Solution(object):
def jobScheduling(self, startTime, endTime, profit):
n = len(startTime) # 작업의 총 개수
# 각 작업을 [시작시간, 끝나는 시간, 수익] 형태로 저장 -- zip 함수를 써도 OK
jobs = []
for i in range(n):
jobs.append([startTime[i],endTime[i],profit[i]])
# 작업을 시작 시간에 따라 정렬 - 순차적으로 작업을 순회하기 위함.
jobs = sorted(jobs,key=lambda x:x[0])
# 힙 초기화 및 최대 수익 변수 설정
queue = []
current, max_profit = 0,0
# 모든 작업 순회
for s,e,p in jobs:
# 현재 작업의 시작 시간 이전에 끝나는 작업들을 heap 에서 제거
while queue and queue[0][0] <= s:
et , temp = heapq.heappop(queue)
current = max(current,temp)
# 현재 작업을 heap 에 추가
heapq.heappush(queue,(e,current+p))
# 최대 수익 업데이트
max_profit = max(max_profit,current+p)
return max_profit
1. 작업 초기화 및 정렬
jobs = []
for i in range(n):
jobs.append([startTime[i], endTime[i], profit[i]])
jobs = sorted(jobs, key=lambda x: x[0])
→ 여기서는 각 작업을 '[시작시간, 종료시간, 수익]' 형태로 jobs 리스트에 추가합니다.
→ sorted() 함수를 사용해서 각 작업들을 시작시간(startTime) 에 따라 정렬합니다.
(※ 이 때, lambda 함수를 사용하여 x[0](startTime 원소)를 기준으로 정렬합니다.)
각 배열을 하나로 묶고 정렬한 이유는 각 작업들을 순차적으로 탐색하기 위함입니다. 이 때, 각 작업에 대한 profit 정보도 함께 저장한 이유는 각 작업들을 할지 말지 비교해가면서 최대 수익을 비교해야 하기 때문입니다.
2. 힙 초기화 및 최대 수익 계산
queue = []
current, max_profit = 0, 0
for s, e, p in jobs:
while queue and queue[0][0] <= s:
et, temp = heapq.heappop(queue)
current = max(current, temp)
heapq.heappush(queue, (e, current + p))
max_profit = max(max_profit, current + p)
→ 'queue' 는 힙 자료구조로 사용되는데, 각 작업의 종료시간과 그 시점에서의 누적수익을 저장합니다.
→ 'for' 루프는 모든 작업을 순회합니다.
→ 'while' 루프는 현재 작업의 시작시간(s) 이전에 끝나는 작업들을 힙에서 제거하고, 'current'(힙에서 현재까지 고려된 작업들 중에서 가장 높은 수익) 을 업데이트 합니다.
(※ 힙에서 작업을 제거할 때, 현재 작업의 시작시간 이전에 끝나는 모든 작업을 고려해야 합니다. 이는 겹치지 않는 작업들만 고려하기 위함입니다.)
→ heapq.heappush() 를 사용하여 현재 작업을 heap 에 추가합니다. 이 때, 현재 작업의 종료시간과 새로운 누적수익을 저장합니다.
→ 'max_profit' 은 현재까지 계산된 최대 수익을 저장합니다.
(※ 최대 수익을 계산할 때, 힙에 있는 모든 요소를 고려해야 합니다. 물론, 마지막 작업이 반드시 최대수익을 제공하는 것은 아닙니다.)
※ 그럼 current 와 max_profit 의 차이가 정확히 뭘까요?
여기서, 'current' 는 while 루프에서 heap에 있는 작업을 제거할 때마다 업데이트 됩니다. 이는 "현재 작업의 시작시간 이전에 끝나는 작업들 중 최대 수익" 을 의미합니다.
즉, 'current' 는 특정 시점에서 가능한 최대수익을 나타내고, 이는 다음 작업의 수익 계산에 사용됩니다. 긴 작업을 고려할 때, 현재까지의 최대수익('current')을 업데이트하고, 이를 바탕으로 새로운 작업의 수익을 추가하여 힙에 저장하는 원리입니다.
'max_profit' 은 "지금까지 고려된 모든 작업들을 통해 얻을 수 있는 최대 수익" 을 나타냅니다. 각 작업을 처리할 때마다 업데이트 되며, 새로운 작업이 추가될 때마다 해당 작업을 포함하여 얻을 수 있는 최대수익('current + p')과 현재의 'max_profit' 을 비교하여 더 큰 값을 'max_profit'으로 설정합니다.
최종적으로, max_profit 은 모든 작업을 고려한 후 얻을 수 있는 최대수익을 나타내는 것이죠.
→ 즉, 'current' 는 현재작업 시점에서 가능한 최대수익을 나타내는 반면, 'max_profit' 은 지금까지 고려된 모든 작업들을 통해 얻을 수 있는 최대수익을 나타내는 것입니다. 'current'는 계속해서 업데이트되며 각 작업의 수익계산에 영향을 미치고, 'max_profit'은 최종 결과값으로, 모든 작업을 고려한 후의 최대 수익을 나타냅니다.
종합적으로 코드의 효율성을 따져봅시다.
class Solution(object):
def jobScheduling(self, startTime, endTime, profit):
n = len(startTime)
jobs = []
for i in range(n):
jobs.append([startTime[i],endTime[i],profit[i]])
jobs = sorted(jobs,key=lambda x:x[0])
queue = []
current, max_profit = 0,0
for s,e,p in jobs:
while queue and queue[0][0] <= s:
et , temp = heapq.heappop(queue)
current = max(current,temp)
heapq.heappush(queue,(e,current+p))
max_profit = max(max_profit,current+p)
return max_profit
최종 코드는 각 작업을 한 번씩만 처리하며, 힙을 사용하여 최대 수익을 효율적으로 관리하고 있습니다.
전체적인 시간 복잡도는 O(n * logn) 입니다. (여기서 'n'은 작업의 수입니다.)
이 코드의 시간 복잡도를 분석하기 위해, 각 주요 부분을 살펴보겠습니다.
1. 정렬 (sorted(jobs,key=lambda x:x[0]))
→ 이 부분은 O(n log n) 시간 복잡도를 가집니다. 여기서 n은 jobs 리스트의 길이입니다. 파이썬의 정렬 알고리즘은 팀소트(Timsort)를 사용하는데, 이는 평균 및 최악의 경우 O(n log n)의 시간 복잡도를 가집니다.
2. 루프 (for s,e,p in jobs)
→ 이 루프는 jobs 리스트의 모든 요소를 한 번씩 순회합니다. 따라서 이 부분의 시간 복잡도는 O(n)입니다
3. 내부 루프 (while queue and queue[0][0] <= s)
→ 이 루프는 최악의 경우 각 작업마다 한 번씩 실행될 수 있습니다. 그러나, 각 작업은 한 번만 큐에서 제거될 수 있으므로, 전체 작업에 대해 O(n)의 시간 복잡도를 가집니다
4. 힙 연산 (heapq.heappop(queue) 및 heapq.heappush(queue,(e,current+p)))
→ 힙 연산은 O(log n)의 시간 복잡도를 가집니다. 이는 큐에 요소를 추가하거나 제거할 때마다 발생합니다. 최악의 경우, 모든 작업에 대해 이러한 연산이 수행될 수 있으므로, 전체적으로 O(n log n)의 시간 복잡도를 가집니다.
종합적으로, 이 코드의 시간 복잡도는 각 부분의 시간 복잡도를 합한 것으로, 가장 큰 시간 복잡도를 가지는 부분이 전체 시간 복잡도를 결정합니다. 따라서, 이 코드의 전체 시간 복잡도는 O(n log n)입니다. 여기서, 정렬 부분과 힙 연산 부분이 주요 시간 소모 요소입니다.
시간복잡도가 O(nlogn) 인 것을 동의하시나요? 이런 의문이 남으실 수 있습니다.
근데 for문이 O(n) 이고 그 내부에 있는 while 문이 O(n) 이니까 결국 O(n^2) 이 되고 while문 내부에 또 heap 연산에 의해 O(logn) 이니까 종합적으로 O(n^2 * logn) 이 되는 것 아니에요? 왜 for문과 while문이 중첩문인데, O(n) 으로 해석되는건가요?
충분히 가질 수 있는 의문입니다. 하지만, for 루프와 while 루프의 상호작용을 자세히 다시 살펴볼 필요가 있습니다.
1. for 루프 (for s,e,p in jobs)
: 이 루프는 jobs 리스트의 모든 요소를 한 번씩 순회합니다. 따라서 이 부분의 시간 복잡도는 O(n)입니다.
2. while 루프 (while queue and queue[0][0] <= s)
: 이 루프는 각 작업에 대해 큐에서 작업을 제거합니다. 중요한 점은, 각 작업이 큐에 한 번만 들어가고 한 번만 나온다는 것입니다. 즉, 전체 작업에 대해 while 루프는 총 n번의 작업을 수행합니다. 이는 각 작업에 대해 평균적으로 O(1)의 시간이 소요된다는 것을 의미합니다.
3. 힙 연산 (heapq.heappop(queue) 및 heapq.heappush(queue,(e,current+p)))
: 이 연산들은 O(log n)의 시간 복잡도를 가집니다.
for 루프 내부의 while 루프가 각 반복마다 O(n)의 시간을 소모하는 것처럼 보일 수 있지만, 전체적으로 보면 각 작업은 큐에서 한 번만 처리됩니다. 따라서, while 루프는 전체적으로 O(n)의 시간을 소모합니다.
→ 이는 for 루프와 while 루프가 독립적으로 O(n)의 시간을 소모하는 것이 아니라, 함께 작동하여 전체적으로 O(n)의 시간을 소모한다는 것을 의미합니다. 결론적으로, 이 코드의 전체 시간 복잡도는 O(n log n)입니다. 이는 정렬 부분과 힙 연산 부분이 주요 시간 소모 요소이며, for와 while 루프의 조합이 전체적으로 O(n)의 시간을 소모하기 때문입니다.
이렇게, O(n*logn) 시간복잡도로 이 문제를 시간초과없이 잘 해결할 수 있습니다.
이상으로 정렬, heapq와 관련한 1235. Maximum Profit in Job Scheduling 문제를 정리해봤습니다.
연관된 문제로 1751. Maximum Number of Events That Can Be Attended II 가 있으니 풀어보시면 좋습니다.
Maximum Number of Events That Can Be Attended II - LeetCode
Can you solve this real interview question? Maximum Number of Events That Can Be Attended II - You are given an array of events where events[i] = [startDayi, endDayi, valuei]. The ith event starts at startDayi and ends at endDayi, and if you attend this ev
leetcode.com