그리디 알고리즘

froajnzd·2024년 1월 5일

algorithm

목록 보기

2/11

탐욕 알고리즘이라고도 말하는데, 이 단어에서도 유추할 수 있듯이 '욕심쟁이'의 성격을 띈다고 보아도 된다

각 경우의 수를 찾아나서는 과정마다 가장 최적이라고 생각되는 것을 선택하는 방식을 사용해 최종적인 해답으로 도달하는 알고리즘이다.

한 순간 순간마다 'local 최적'의 값을 선택한다고 볼 수 있지만, 최종적인 해에 도착하였을 때 그 '최종 해'가 'global 최적'의 값이라는 보장이 없다 (global 최적인 경우가 있기도 하다. 무조건 없다고도 보장 못한다는 뜻!)

그렇기에 우리는 이 Greedy Algorithm을 local(지역적인) 최적을 찾아가는 과정이 결국 global(전역적인) 최적을 찾아가는 문제에 적용할 수 있다.

📕 Greedy Algorithm을 사용해야하는 문제의 조건

Greedy Choice Property (탐욕스런 선택)
: 앞의 선택이 이후의 선택에 영향을 주지 않음
Optimal Substructure (최적 부분 구조)
: 문제에 대한 최적해가 부분문제에 대해서도 최적해임

이 두 가지 조건을 만족하는 문제.

💡 Greedy Algorithm의 장점

계산 속도가 빠르다

📝 Greedy Algorithm을 응용한 알고리즘

다익스트라 알고리즘
허프만 코드
Kruskal Algorithm (크루스칼 알고리즘)
Prim's Algorithm (프림 알고리즘)

🎁 Greedy Algorithm을 사용하는 문제의 예

결정 트리 학습(Decision Tree Learning)
활동 선택 문제(Activity selection problem)
거스름돈 문제
: 동전들이 배수관계가 성립할 때 한정. 대부분의 화폐는 1,5,10,25,50 등 딱 떨어지는 수를 갖기에 그리디로 해결됨
제약조건이 많은 대부분의 문제
: '대부분의'라는 단어에 유의. 아닌 경우도 있기 마련.

#### c.f. Greedy Algorithm을 사용하면 안되는 문제의 예 - 휴리스틱 알고리즘 - 외판원 순회 문제(TSP: Traveling Salesperson Problem) - 배낭 문제(Knapsack Problem)
### 🏃‍ 예시 문제 1

<BAEKJOON: 실버 4> 설탕 배달

해답

가장 최적의 해(5인 설탕 봉지를 최대로 하는 것)에서 시작하여
두 봉지에 들어있는 설탕양의 합이 N이 될 때까지
5인 설탕봉지를 하나씩 줄여가며 찾는다

N = int(<input())
bigBag = N // 5
smallBag = (N-5*bigBag) // 3
while bigBag * 5 + smallBag * 3 != N and bigBag >= 0:
    bigBag -= 1
    smallBag = (N-5*bigBag) // 3
if bigBag < 0:
    print(-1)
else:
    print(bigBag+smallBag)

🏃‍ 예시문제 2

<BAEKJOON: 실버 3> 병든 나이트

해답

병든 나이트는 위-오른쪽 또는 아래-오른쪽으로 밖에 가질 못한다는 것을 문제에서 알 수 있다.
1번 또는 4번 움직임으로 가는 것이 최대로 방문할 수 있는 것임을 알 수 있다.
조건에 4번 이상 움직인다면 4가지 움직임을 한 번 이상 써야 한다.

그렇다면, 경우를 크게 세 가지로 나눌 수 있는데
1) 세로 길이가 1이어서 아예 움직이지 못하는 경우
2) 세로 길이가 2여서 2번 또는 3번 움직임밖에 못사용하는 경우
3) 세로 길이가 3 이상인 경우
각각 계산해 주면 된다.
1)의 경우에는 나이트는 움직일 수 없기에 무조건 1이고
2)의 경우는 가로 길이에 따라 언제 4번의 이동 횟수 제약 없이 움직였을 때 방문 횟수가 얼마나 나오는지 파악하고
3)의 경우도 4번의 이동 횟수 제약 없는 경우를 파악하여 결과를 도출하면 된다.

N, M = map(int, input().split())
if N == 1:
    print(1)
elif N == 2: # 위아래로 1칸씩만 움직이는 것밖에 못 씀
    if M > 8:
        print(4)
    else:
        print((M-1) // 2 + 1)
elif M < 5: # 이동 횟수가 4번보다 적게 나오는 경우
    print(M)
elif M == 5:
    print(M-1)
else: # 이동 횟수가 4번 이상인 경우 -> 4가지 경우 사용 > 오른쪽으로 2칸가는 경우를 한번씩만 쓰기
    print(M-2)

🏃‍ 예시문제 3

<BAEKJOON: 실버 1> 신입 사원

문제 풀이

처음에 이해가 안됐던 부분이, 채용 기준이었는데

다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

여기서 지원자를 '모든 N명의 지원자'라고 생각했기에
1) 합격할 수 있는 사람은 'N-1명의 지원자' 중 한 명이라도 좋은 성적이 있다면 => (꼴등,꼴등)인 사람이 있지 않는 이상 N명이 합격할 수 있는 것이 아닌가?
: 이건 2번째 예시에 들어맞지 않음

2) 그렇다면 합격할 수 있는 사람은 'N-1명의 지원자' 모두에게 하나라도 좋은 성적이 있어야 함
: 예시 2번에서

3 6
7 3
4 2
1 4
5 7
2 5
6 1
여기서 자신을 제외한 모든 사람들보다 하나라도 좋은 평가를 받은 사람은
우선, 각 분야에서 1등들과, (4, 2)의 성적을 받은 사람이 있다

=> 어떻게 풀 것인가?

해답

n*n번의 반복문으로 한 지원자에 대해 다른 모든 지원자의 점수를 비교하는 방식으로 찾을 수 있지만, 이 방법은 시간복잡도가 O(N^2)으로 시간복잡도가 높다.

위의 예시2번에서 합격자를 찾은 과정을 보면 각 분야에서의 1등은 무조건적으로 합격자 반열에 오른다
그리고 서류 1등 참가자보다 면접 점수가 높고, 면접 1등 참가자보다 서류 점수가 높은 참가자가 있다면 이 참가자는 합격자 반열에 오를 수 있다.

이것을 생각한다면, 해당 문제를 쉽게 풀 수 있다.

sort를 통해 서류 1등을 찾는다; cnt++
서류 1등의 면접 점수를 저장해둔다
sort된 배열을 차례로 탐색하면서 면접 점수가 높은 사람을 찾는다
찾았다면, 그 다음으로 찾는 사람은 이전에 찾아진 사람보다 무조건 서류점수가 낮으므로 면접점수는 높아야 한다.
이전에 찾은 면접 점수를 기준으로 그 아래를 탐색해간다.

최악 시간복잡도 O(NlogN + N)

import sys
input = sys.stdin.readline
def employ():
    N = int(input())
    aplcnt = []
    for i in range(N):
        aplcnt.append(list(map(int, input().split())))
    aplcnt.sort()
    cnt = 1
    interview = aplcnt[0][1]
    for graded, gradei in aplcnt:
        if gradei < interview:
            interview = gradei
            cnt += 1
    print(cnt)

T = int(input())
for _ in range(T):
    employ()

💯 Greedy Algorithm 문제를 더 풀어보고 싶다면?

Hi I'm 열쯔엉

이전 포스트

위상정렬 알고리즘

다음 포스트