[코테 직전 유형 정리] - 그리디

다양한 종류의 문제가 존재하는 유형이다.

 

---

유형 1. 구간 내 최소 개수 사용하기

특정 구간 내에서 몇 개를 설치해야 전체를 커버할 수 있느냐 ~ 이런 유형의 문제이다.

풀이 방법만 알면 되게 쉽게 풀 수 있다.

1. 진출 시점 (끝점) 기준으로 오름차순 정렬
2. 반복문 순회하며 현재 진입시점이 이전 진출 시점보다 작으면 넘어가고, 현재 진입시점이 이전 진출 시점보다 크면 갱신하는 방식

 

아래 두 문제가 굉장히 유사한 문제다.

• 단속 카메라

https://school.programmers.co.kr/learn/courses/30/lessons/42884

def solution(routes):
    answer = 1 # 시작지점에 1개
    routes = sorted(routes, key=lambda x: (x[1], x[0]))
    
    # 초기 진출 시점
    prev_max_point = routes[0][1]    
    
    # 순회하면서
    for idx in range(1, len(routes)):
    	# 현재 진입 시점이 이전 진출 시점보다 클 경우 - 커버가 안됨
        if routes[idx][0] > prev_max_point:
            answer += 1
            prev_max_point = routes[idx][1]
        
    
    return answer

 

 

• 요격 시스템

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

def solution(targets):
    answer = 1
    targets = sorted(targets, key=lambda x: (x[1], x[0]))
    # print(targets)
    
    prev_end_point = targets[0][1]
    
    for i in range(1, len(targets)):
        # print("## 현재 시작 구간", targets[i][0], "## 이전 최대 끝 구간", prev_end_point)
        if targets[i][0] >= prev_end_point:
            answer += 1
            prev_end_point = targets[i][1]
            
    
    return answer

 

---

 

유형 2. 최대값 만들기

미래를 알고 있기 때문에, 거꾸로 순회하면서 최대로 만드는 전략을 사용하면 된다.

• 주식

https://www.acmicpc.net/problem/11501

• 가장 마지막 날부터 거꾸로 탐색하면서,
• 현재까지의 최대 주가(max_price) 를 기억합니다.
• 매 날의 주가가 max_price보다 작다면, 그 날 사서 max_price에 판다고 가정하고 이익을 계산합니다.
• 총 이익을 누적하여 출력합니다.

 

import sys

def solve():
    T = int(sys.stdin.readline())  # 테스트 케이스 수 입력

    for _ in range(T):
        N = int(sys.stdin.readline())  # 각 테스트 케이스의 날 수
        prices = list(map(int, sys.stdin.readline().split()))  # 날 별 주가 리스트

        max_price = 0     # 현재까지의 최대 주가 (미래 기준)
        profit = 0        # 누적 이익

        # 주가 리스트를 뒤에서부터 탐색 (미래부터 현재로)
        for price in reversed(prices):
            if price > max_price:
                # 더 비싼 날이 있으면, 그날을 기준으로 팔기 위해 max_price 갱신
                max_price = price
            else:
                # 현재 주가가 max_price보다 낮으면, 지금 사서 max_price에 판다고 가정
                profit += max_price - price

        print(profit)  # 해당 테스트케이스의 최대 이익 출력

# 함수 실행
solve()

 

---

 

유형 3. 문자열 탐색

문자열을 바꾸기 위해서 드는 비용 (e.g. 커서의 이동 위치 등) 을 그리디하게 탐색하는 문제.

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

 

def up_down(target):
    return min(abs(ord(target) - ord('A')), abs(ord('Z') - ord(target) + 1))

def solution(name):
    # 알파벳 변경 횟수, 커서 변경 횟수
    spell_move = 0; cursor_move = len(name) - 1 # 최대 이동 거리

    for idx, ch in enumerate(name):
        # 상하이동부터
        spell_move += up_down(ch)

        # 해당 인덱스 다음부터 연속된 A 문자열 찾기
        next_idx = idx + 1
        while next_idx < len(name) and name[next_idx] == 'A':
            next_idx += 1
        
        # next_idx : 연속된 A 문자열의 오른쪽 끝 인덱스
        # 정방향, 역방향 순회 거리 중 최소값 비교
        distance = min(idx, len(name) - next_idx)
        
        # 실제 이동 거리 계산 (순방향 VS 역방향 거리 계산)
        print(name, ch)
        print((cursor_move, idx + len(name) - next_idx + distance))
        
        cursor_move = min(cursor_move, idx + len(name) - next_idx + distance)

    answer = spell_move + cursor_move
    
    return answer

 

---

유형 4. 우선순위 큐 활용 문제

• 무지의 먹방 라이브

https://school.programmers.co.kr/learn/courses/30/lessons/42891

프로그래머스

 

그림처럼 정렬이 보장되어야 효율성 테스트를 통과할 수 있는 문제다.

따라서 항상 최소값을 뽑을 수 있도록, heapq를 결합하여 그리디를 사용한다.

 

import heapq

def solution(food_times, k):
    # 애초에 먹을 음식 안남으면 -1 반환
    if k >= sum(food_times):
        return -1
    
    food_list = []
    length = len(food_times) # 남은 음식 개수

    for i in range(length):
		    # (남은 시간, 음식 번호)
		    # 최소 힙을 통한 음식 시간 정렬
        heapq.heappush(food_list, [food_times[i], i+1])
    
    time = 0
    
    # 블럭 단위로 뺄만큼 K가 남았다면 -> 묶음 단위로 빼주기
    while (food_list[0][0] - time) * length < k:
        k -= (food_list[0][0] - time) * length
        time += food_list[0][0] - time
        length -= 1
        heapq.heappop(food_list)
		
		# 최종적으로 K초에 몇 번째 음식이 오는지 구하기
    result = sorted(food_list, key = lambda x: x[1])
    answer = result[k % length][1]

    return answer