[Algorithm/Greedy Algorithm] 그리디 알고리즘

최율·2022년 11월 23일

Algorithm

목록 보기

4/5

🤑 욕심쟁이 알고리즘

인간은 지금 당장 직면한 문제를 해결하는데 아주 특화되어 있다.
단, 미래의 일은 해결해내기를 아주 귀찮아하고 잘 하지도 못한다.

위 인용문은 필자가 즐겨 듣는 모 재테크 유튜버의 생각이다.
사람은 지금 당장의 기분이 중요하며(뭐, 동물이니까 당연한거 아닐까!) 지금 당장 직면한 문제는 빠르게 착수하여 해결해내기 때문에 일반적인 사람들은 소비를 줄이기 힘들다는게 말의 골자다.

그런 인간의 특성을 잘 반영시킨 알고리즘이 바로 욕심쟁이 알고리즘이다.

💡아이디어

전체적인 입장을 보지 않고 현재 순간 최선을 취한다.
그리고 매 단계마다 각 단계에서 최선이라고 판단되는 선택을 취한다.

장점

구현이 쉽다! (최고의 장점!)
생각해내기도 쉽다!

한계

구한 정답이 최적의 정답이라는 것은 보장할 수 없다.
따라서, 구한 정답이 최적의 정답이라는 것은 증명이 필요하다.

장단점이 아주 확연한 알고리즘임을 알 수 있다.
게다가 “현재 취할 수 있는 최선의 선택을 취한다.” 라는 점에 선조 프로그래머들이 취했는지 다음과 같은 기본 형태를 정의하였다. (사실 로직이 아주 간단하기에 설계할 수 있었겠지만 말이다)

기본 형태

예시 문제

이집트 나눗셈 문제

유리수 p/q가 주어졌을 때, 분자가 1인 분수들의 합으로 p/q를 표현하시오.

예) 5/6 = 1/2 + 1/3, 3/4 = 1/2 + 1/4

해법 1

n을 2부터 1씩 더해나간다.
1/n과 p/q 를 비교하여 결과에 따라 다음과 같은 행동을 취한다.
- 1/n이 더 크다면 n에 1을 더해준다.
- p/q가 더 크다면 p/q에 1/n을 빼준다.
만약 p/q가 0이 되면 문제가 풀린 것이니 종료한다.

해법1 방식은 브루트 포스 방식의 성격이 강하다.

그러기 때문에 분모의 값이 큰 경우 비효율적인 접근 방식이 된다.

해법 2

주어진 수 p/q에 대해서, 이 수의 역수 q/p의 가우스 값(같거나 큰 가장 작은 정수)을 찾는다.
1/gauss(q/p) 를 p/q에서 뺀다. 이 과정을 0이 될 때까지 반복한다.

예시)

5/6에 대해서, $gauss(q/p)=2, \space 5/6 - 1/2 = 1/3$

1/3에 대해서, $gauss(q/p) = 3, \space 1/3 - 1/3 = 0$

해법 2 - 코드

import math

def gauss(a, b):
    if (a % b == 0):
        return a // b
    else:
        return a // b + 1

p, q = map(int, input().split())
cnt = 0

while (p != 0):
    n = gauss(q, p)
    l = math.lcm(q, n)
    least = [l // q, l // n]
    p = p * least[0] - 1 * least[1]
    q *= least[0]
    cnt += 1

print(cnt)

회의실 배정 문제

한 개의 회의실이 있는데, n개의 회의 일정이 있고 이 회의실을 이용하여 회의한다.
각 회의 i에 대해서 시작 시간 $S_i$ 와 끝 시간 $F_i$ 가 주어진다.
각 회의가 겹치지 않게 하면서 가장 많은 횟수의 회의를 할 수 있도록 일정을 구하는 프로그램을 작성하라

입력

첫 줄에는 회의의 수 n

둘째 줄부터 n+1 줄 까지 두 정수 $S_i$ 와 $F_i$

출력

잡은 회의를 차례대로 출력 (둘 이상의 답이 있을 수 있다)

접근 방법

가장 많은 횟수의 회의를 진행하여야 하니 회의 시간이 짧은 것들을 우선적으로 확보한다.
- 반례가 발생한다.

다른 회의와 가장 적게 겹치는 회의부터 확보한다.
- 반례가 발생한다. 각 회의의 상단에 적힌 숫자는 겹치는 회의 개수를 의미.

정답: 가장 빨리 끝나는 회의부터 배정해나간다.

증명

모든 회의를 끝나는 시간에 따라 정렬해서 {1 , … , n} 을 얻습니다.
그렇다면 정답은 1을 포함하거나 포함하지 않거나 둘 중 하나입니다.

정답을 포함하지 않는다면..

1번 회의와 겹치지 않는 경우 → 1번 회의를 정답에 배정할 수 있으므로 모순입니다.
1번 회의와 겹치는 경우 → 1번 회의와 겹치는 회의를 빼고, 1번 회의를 넣게 되도, 회의의 수는 변함이 없습니다.
- 이 경우 때문에 둘 이상의 답이 존재할 수 있게 됩니다.

정답을 포함한다면…

정답에 1이 포함되어 있기 때문에 증명이 됩니다.

구현

class meeting:
    def __init__(self, s, f):
        self.start = s
        self.finish = f

    def to_string(self):
        return "({}, {})".format(self.start, self.finish)

n = int(input())
l = []
res = []
for _ in range(n):
    s, f = map(int, input().split())
    l.append(meeting(s, f))

# 일단 sort합니다. 편의상 reverse까지 해줍니다.
l.sort(key=lambda it: it.finish, reverse=True)
res.append(l.pop())
i = 0

while len(l) > 0:
    candi = l.pop()
    last = res[i]
    if (candi.start < last.finish):
        # 회의가 서로 겹치는 경우
        continue
    else:
        # 회의가 서로 겹치지 않는 경우
        res.append(candi)
        i += 1

for e in res:
    print(e.to_string(), end=' ')