그리디 알고리즘
Question 78: 주식을 사고팔기 가장 좋은 시점2
여러번의 거래로 낼 수 있는 최대 이익을 산출하라.
입력: [7,1,5,3,6,4]
출력: 7
내 풀이
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
result = []
for i in range(len(nums)-k+1):
result.append(max(nums[i:i+k]))
return result
결과
시간 초과 에러가 떴다.
풀이 1: 브루트 포스로 계산
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
result = []
for i in range(len(nums)-k+1):
result.append(max(nums[i:i+k]))
return result
중요 내용
- 앞에 nums가 입력값이 없을때 예외 처리하는 것을 제외하고 내 풀이 방법과 동일하게 풀이하였다.
- 책에서는 풀이가 704ms 만큼 소모되었다고 나왔는데 실제로 계산해보니 시간 초과 에러가 떴다.
풀이 2: 큐를 이용한 최적화
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
results = []
window = collections.deque()
current_max = float('-inf')
for i, v in enumerate(nums):
window.append(v)
if i < k - 1:
continue
# 새로 추가된 값이 기존 최대값보다 큰 경우 교체
if current_max == float('-inf'):
current_max = max(window)
elif v > current_max:
current_max = v
results.append(current_max)
# 최대값이 윈도우에서 빠지면 초기화
if current_max == window.popleft():
current_max = float('-inf')
return results
중요 내용
- 윈도우 변수를 만들고 윈도우의 최댓값과 윈도우를 이동하면서 새로 추가되는 값간의 크기를 비교한다.
- 풀이1과 마찬가지로 책에서는 풀이가 156ms 만큼 소모되었다고 나왔는데 실제로 계산해보니 시간 초과 에러가 떴다.
Question 79: 키에 따른 대기열 구성
여러 명의 사람들이 줄을 서 있다. 각각의 사람은 (h, k)의 두 정수 쌍을 갖는데, h는 그 사람의 키, k는 앞에 줄 서 있는 사람들 중 자신의 키 이상인 사람들의 수를 뜻한다. 이 값이 올바르도록 줄을 재정렬하는 알고리즘을 작성하라.
입력: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
출력: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
풀이 1: 우선순위 큐
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
heap = []
for person in people:
heapq.heappush(heap, (-person[0], person[1]))
print(heap)
result = []
while heap:
person = heapq.heappop(heap)
result.insert(person[1], [-person[0], person[1]])
return result
중요 내용
- 이 문제는 첫번째 값이 큰 순서대로 두번째 값의 인덱스로 삽입하는 방법으로 풀 수 있다.
- 첫번째 값이 큰 순서대로 리스트를 추출하는 방법은 최대 힙(max heap) 방법을 사용하면 된다. 그러나 파이썬의 heapq는 최소 힙(min heap)만 지원하므로 첫번째 값을 음수로 바꾼 후에 heappop을 적용해 다시 음수를 적용하는 방법으로 풀어야 한다.
- list.insert(index, value) 는 지정한 index에 value 값을 삽입한다.
Question 80: 태스크 스케줄러
A부터 Z로 표현된 태스크가 있다. 간 간격마다 cpu는 한번의 태스크만 진행할 수 있고, n번의 간격 내에는 동일한 태스크를 실행할 수 없다. 더이 상 태스크를 진행할 수 없는 경우 idle 상태가 된다. 모든 태스크를 실행하기 위한 최소 간격을 출력하라.
입력: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
출력: 8
풀이 1: 투 포인터, 슬라이딩 윈도우 이용
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
counter = collections.Counter(tasks)
result = 0
while True:
sub_count = 0
print(f'most_common:{counter.most_common(n+1)}')
# 개수 순 추출
for task, _ in counter.most_common(n + 1):
sub_count += 1
result += 1
print(f'sub_count: {sub_count}, result: {result}')
counter.subtract(task)
# 0 이하인 아이템을 목록에서 완전히 제거
counter += collections.Counter()
if not counter:
break
result += n - sub_count + 1
return result
중요 내용
- 문제를 이해하기 어려워서 print문을 추가하였다.
- n은 동일한 태스크 사이에 존재해야 하는 태스크의 개수이다.
- counter 함수에서 collection.Counter()을 더하면 0이하의 값을 삭제한다.
- most_common(n)에서 n은 counter 객체의 개수를 초과해도 정상적으로 작동한다.
Question 81: 주유소
원형으로 경로가 연결된 주유소 목록이 있다. 각 주유소는 gas[i] 만큼의 기름을 갖고 있으며, 다음 주유소로 이동하는데 cost[i]가 필요하다. 기름이 부족하면 이동할 수 없다고 할 때 모든 주유소를 방문할 수 있는 출발점의 인덱스를 출력하라.
입력: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
출력: 3
풀이 1: 모두 방문
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
for start in range(len(gas)):
fuel = 0
for i in range(start, len(gas) + start):
index = i % len(gas)
can_travel = True
if gas[index] + fuel < cost[index]:
can_travel = False
break
else:
fuel += gas[index] - cost[index]
if can_travel:
return start
return -1
중요 내용
- 주유소는 원형으로 연결되어 있으므로 인덱스 0에서 시작하지 않아도 모듈로 연산을 통해서 인덱스를 0부터 지정할 수 있다.
- 시작점을 바꿔가면서 모든 경로를 이동할 수 있는 연료가 있는지 확인한다.
풀이 2: 한 번 방문
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
# 모든 주유소 방문 가능 여부 판별
if sum(gas) < sum(cost):
return -1
start, fuel = 0, 0
for i in range(len(gas)):
# 출발점이 안되는 지점 판별
if gas[i] + fuel < cost[i]:
start = i + 1
fuel = 0
else:
fuel += gas[i] - cost[i]
return start
중요 내용
- 시작점은 반드시 존재하므로 gas > cost 인 지점이 반드시 존재한다. 따라서 해당점을 시작점으로 설정하고 모든 지점을 들를 수 있는 연료를 가지고 있는지 확인한다.
- 모든 지점을 방문하면서 성립되지 않는 경우는 출발점을 한 칸씩 뒤로 밀어낸다.
Question 82: 쿠키 부여
아이들에게 1개씩 쿠키를 나눠줘야 한다. 각 아이 child_i 마다 그리드 팩터 g_i를 갖고 있으며, 이는 아이가 만족하는 최소 쿠키의 크기를 말한다. 각 쿠키 cookie_j는 크기 s_j를 갖고 있으며, s_j >= g_i 이어야 아이가 만족하며 쿠키를 받는다. 최대 몇명의 아이들에게 쿠키를 줄 수 있는지 출력하라.
입력: g = [1,2,3], s = [1,1]
출력: 1
풀이 1: 그리디 알고리즘
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
child_i = cookie_j = 0
# 만족하지 못할 때까지 그리디 진행
while child_i < len(g) and cookie_j < len(s):
if s[cookie_j] >= g[child_i]:
child_i += 1
cookie_j += 1
return child_i
중요 내용
- 현재 가지고 있는 쿠키의 크기를 반복을 통해 각 아이가 원하는 최소 쿠키의 크기보다 큰지 점검한다.
풀이 2: 이진 검색
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
result = 0
for i in s:
index = bisect.bisect_right(g, i)
if index > result:
result += 1
return result
중요 내용
- 하나의 리스트를 순회하면서 다른 하나는 이진 검색으로 찾는데, 찾아낸 인덱스가 현재 부여한 아이들보다 클 경우는 더 줄 수 있다는 말이 되므로 줄 수 있는 아이들의 수를 1명 더 늘린다.
- bisect_right는 찾아낸 값의 다음 인덱스를 리턴한다.
Comments