[TIL] 그리디 (BOJ 1700 멀티탭 스케줄링)

Hyeon·2022년 10월 18일

그리디 백준

TIL

목록 보기

7/8

-

그리디 문제를 풀고나서 스터디를 하던 중,
문제를 보고 "그리디로 풀 수 있겠다" 고 판단하기 위해서는
어떤 접근이 있어야 할지 이야기 하다가 나온 생각을 기록하기 위해 적어둔다.

1.

그리디 알고리즘은,
최적 부분 구조(Optimal Substructure)를 가지는 문제에서
최적화를 위해 DP로 풀 수 있지만, 더 간단하고 효율적인 알고리즘으로
충분히 풀 수 있는 경우에 적용할 수 있는 '방법' 이다.

각 단계에서 최선의 선택이
항상 전체적인 최적해로 안내할것이라는 바람으로
부분적인 최적의 선택을 하는 것이다.

2.

활동 선택 문제가 최적 부분 구조를 갖는것과,
그리디 선택이 가능한 이유에 대한 증명 자체가 이해는 되나
"이런 문제가 그리디 문제구나"라는것이 와닿지는 않았다.

📍 그리디는 정렬을 해야하는 문제인가?

맨 처음 몇몇 문제(회의실 배정, 신입 사원 등)를 풀면서
그리디로 접근 가능한 문제들의 공통점이라고 느낀것은 다음과 같다.

그리디하게 풀 수 있다는 것 자체가
문제의 각 요소나 선택에 어떤 명확한 우선순위가 존재한다는 뜻이니까,
그 우선순위를 정의한 뒤에 그것에 맞게 정렬해주는 문제구나!

회의실에 예약된 회의 일정을 스케줄에 넣기 위해서는 명확한 우선순위가 존재했다.
신입사원은 특정 점수로 정렬된 상태에서, 정렬 상태를 깨는 사원을 탈락 시키는 문제였다.

1. 우선 순위의 판단
2. 1을 기준으로 정렬

뭔가 간단한 두가지 키워드로 정리될 수 있을것 같았다.

그러다가 이 문제를 만났다.
BOJ 1700 멀티탭 스케줄링

3.

처음 문제를 보고 각 전기용품의 우선순위를 판단하려 했다.

그전에 풀었던 문제들을 바탕으로 생각해보건데,
1 ~ k 라고 이름붙여진 이 전기용품들은
입력된 사용 순서에 따라 어떤 우선순위를 가지겠구나!

라고 생각했다.

그래서 생각해본 3가지 판단 기준은 이렇다.
❓ 각 물건의 사용 횟수
❓ 맨 마지막에 사용되는 물건
❓ 맨 처음 사용되는 물건

처음에 물건 사용 횟수를 가지고 고민해보다가,
한 물건이 처음 사용된 순번과
그 물건이 마지막으로 사용된 순번을 가지고 뭔가 판단해 줄 수 있을것만 같았다.

시작과 끝이 있으니, 활동 선택 문제와 같이 여러 선분(또는 점)들이 그려지고
거기서 어떤 정렬 기준을 정해주어야 한다고 생각했지만,
임의의 순서로 조금만 반례를 만들어보아도 아니라는걸 금방 알 수 있었다.

애초에, 한정된 공간을 차지하는 시간을 시작과 끝만을 가지고 판단해 줄 수 없었다.

4.

그래도 아직 정렬에 대한 미련은 버리지 못했다.

처음에는 단순하게 사용이 빨리 끝나는 전기용품부터 종료될테니까
멀티탭을 힙(heap)으로 구현하자는 생각을 했다.

그런데 힙을 쓴다고 생각하니 문제가 다른 관점으로 보였다.

힙을 쓰는 이유는
힙을 push, pop 하는 과정에서 우선순위가 다시 정렬될 필요가 있고,
이를 짧은 시간( $O(\log n)$ )안에 유지시켜주기 위해서이다.

5. 정답

그러면 매 순서마다 우선순위가 바뀌는건가?

사실 여기까지 생각하고 나서, 도무지 더 떠오르지 않아
질문 게시판에 의도치않게 스포일러된 아이디어들을 참고했다.

생각 자체는 매우 간단하다.

멀티탭에 꽂힌 물건들 중,
이후 사용이 가장 먼 순서에 있는 물건을 뽑아준다.

왜 그럴까?
나는 이런 문제를 다시 볼 때 그리디로 생각할 수 있을까?

6. 이유

📍위 문제 멀티탭 스케줄링에서

멀티탭에 꽂혀있는 애들 중에 가장 뽑기 좋은 녀석은 누구일까?
당연하게도, 이후에 사용할 일이 없는 녀석이다.
그리고 이"이후에 사용할 일이 없는 제품을 뽑는것"이 최선의 선택이다.

그러면 제일 뽑지 말아야 할 제품은 누구일까?
당장 다음 순서에 사용해야 할 녀석이다.
멀티탭에 2번 전기용품이 꽂혀있는데,
다음 사용 순서가 2번인 경우에
2번을 뽑아서 다시 2번을 꽂는 (뽑았다 다시 꽂는)행동이 가장 최악이다.
그래서 "당장 다음 순서에 사용해야 할 제품을 뽑는것"이 최악의 선택이다.

우리는 지금 멀티탭에서 전기용품을 뽑는 선택 중에
최선과 최악을 알았다.

"이후에 사용할 일이 없는 녀석"의 다음 순번은 $\infin$ 번째 이후이다.
"당장 다음 순서에 사용해야 할 녀석"의 다음 순번은 $0$ 번째 이후 이다.

📍그러면, 최선의 선택에 가장 가까운 선택은 뭘까?

최악이랑 가장 먼 제품
그러니까, "다음 순번이 가장 먼 녀석" 이다.

멀티탭에 꽂혀있는 제품들 각각의 다음 순번이 어떻게 되는지 알아야 한다.
그리고 그 중 가장 먼 순번을 가진 제품을 뽑는다.
그러면, 그 상황(멀티탭에 꽂힌 제품들)에서의 가장 최선의 선택(코드 뽑기)을 할 수 있다.

[ 전체 코드 ]

import sys
from collections import defaultdict, deque


n, k = map(int, sys.stdin.readline().split())       # n: 멀티탭 구멍 수, k: 전체 사용 횟수 (A의 길이)
A = list(map(int, sys.stdin.readline().split()))    # A: 가전의 사용 순서 (길이 = k, 1 <= 가전 번호 <= k)


usage_order = defaultdict(deque)                    # 각 전기용품 번호를 index로 하고, 남은 사용 순(A에서의 index)를 deque([])로 저장한다.
for i in range(len(A)):
    usage_order[A[i]].append(i)
################ 예시 ################
# input:
# 2 5
# 1 2 3 2 1
#
# usage_order:
# usage_order[1] == deque([0, 4])
# usage_order[2] == deque([1, 3])
# usage_order[3] == deque([2])
#####################################


ans = 0
multitap = []
for a in A:
    usage_order[a].popleft()

    # 이미 멀티탭에 꽂힌 물건인 경우
    if a in multitap:
        continue
    # 그 외, 멀티탭에 공간이 남은 경우
    elif len(multitap) < n:
        multitap.append(a)
    # 멀티탭에 꽂힌 물건도 아니고, 멀티탭에 공간도 없는 경우
    else:
        # 멀티탭에 꽂힌 물건 중, 다음 사용이 가장 늦는 물건을 뽑는다.
        max_order_idx = -1
        target = -1
        for j in range(len(multitap)):
            if usage_order[multitap[j]]:
                if max_order_idx < usage_order[multitap[j]][0]:
                    max_order_idx = usage_order[multitap[j]][0]
                    target = j
            else:   # 남은 사용 순서가 없는 물건(이제 사용 안하는 물건)은 바로 뽑아도 됨
                target = j
                break
        multitap[target] = a
        ans += 1

sys.stdout.write(f'{ans}')