탐욕법(Greedy Algorithm)

Wonjun·2023년 7월 20일
algoring studygreedy알고리즘 문제해결 전략종만북탐욕법
0

알고리즘 스터디 - 알문해전

목록 보기
3/3
post-thumbnail

탐욕법, 그리디 알고리즘

  • 모든 선택지를 고려해보고 그 중 전체 답이 가장 좋은 것을 찾는 완전 탐색이나 동적 계획법과는 달리, 그리디 알고리즘은 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다.
  • 그러니까, 그리디 알고리즘은 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법인데, 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다.

그래서 그리디 알고리즘은 많은 경우 최적해를 찾지 못한다.

그리디 알고리즘이 사용되는 경우는 크게 두 가지로 나뉜다.

  1. 그리디 알고리즘을 사용해도 항상 최적해를 구할 수 있는 문제의 경우, 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다.

  2. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면 최적해 대신 적당히 괜찮은 답(근사 해)을 찾는 것으로 타협할 수 있다. 이럴 때 그리디 알고리즘은 최적은 아니지만 임의의 답보다는 좋은 답을 구하는 용도로 유용하다.

주로 1.에 해당하는 문제가 많이 출제되고, 2.가 나왔다 하더라도 그리디 알고리즘보다는 조합 탐색이나 메타 휴리스틱 알고리즘들이 더 좋은 답을 주는 경우가 많다고 한다.

그리디 알고리즘을 이용해서 해결할 문제는 상당히 제한되어 있다는 의미로 받아들이면 좋을 것 같다.

그리디 알고리즘을 사용하면 최적해가 나올 수 있는 문제에만 적용하는 것이 좋다.

어떤 문제에 그리디 알고리즘을 적용해서 해결해야겠다고 생각했으면 두 가지 속성을 고려해야 한다. 이 책에서는 이를 그리디 알고리즘의 정당성 증명이라 한다. 증명이라 해서 너무 복잡하게 생각할 필요는 없는 듯하다. 직관적으로 떠올릴 수도 있고, 수식으로써 표현할 수도 있는데 그건 자유다. 대회도 아니고 코테할 때 증명까지 하고 있진 않을 듯?

  • 그리디 알고리즘의 정당성의 증명

그리디 알고리즘의 정당성 증명은 많은 경우 일정한 패턴을 가진다. 이 증명 패턴은 탐욕적인 알고리즘이 항상 최적해를 찾아낼 수 있다는 것을 두 가지의 속성을 증명함으로써 보인다.

  1. 탐욕적 선택 속성

    처음으로 증명해야 할 속성은 동적 계획법처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있다는 것이다. 이 속성을 탐욕적 선택 속성이라고 부른다.
    어떤 알고리즘에 이 속성이 성립할 경우, 각 단계에서 탐욕적으로 내리는 선택은 항상 최적해로 가는 길 중 하나이다. 따라서 탐욕적인 선택을 해서 손해를 볼 일이 없다는 것을 알 수 있다.
  1. 최적 부분 구조

    부분 문제의 탐욕적 선택이 항상 최적의 답을 줄 수 있다고 전체 문제의 최적해를 구할 수 있는 것은 아니다. 항상 최적의 선택만을 내려서 전체 문제의 최적해를 얻을 수 있음을 보여야 한다.
  • 탐욕적 알고리즘 설계 요약
  1. 문제의 답을 만드는 과정을 여러 조각으로 나눈다. (매우 중요)
  2. 각 조각마다 어떤 우선순위로 선택을 내려야 할지 그리디 알고리즘을 구상한다. 이에 대한 직관을 얻기 위해서는 예제 입력이나 그 외의 작은 입력을 직접 손으로 풀어보는 것이 효율적이다.
  3. 구상한 방법을 사용해서 동작할 것 같으면 두 가지 속성을 증명해 보인다.
    a) 탐욕적 선택 속성: 항상 각 단계에서 우리가 선택한 답을 포함하는 최적해가 존재함을 보이면 된다.
    b) 최적 부분 구조: 각 단계에서 항상 최적의 선택만을 했을 때 전체 최적해를 구할 수 있는지 여부를 증명한다. 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보여야 한다.

  • 정리하자면, 그리디 알고리즘으로 문제를 풀기 위해서는 그리디 알고리즘을 구상하고, 탐욕적 선택 속성과 최적 부분 구조를 증명한 뒤, 구현하면 된다.

  • 그리디 알고리즘으로 최적해를 찾을 수 있는 많은 문제들은 동적 계획법으로도 풀 수가 있다. 그리디 알고리즘으로 최적해를 찾을 수 있다는 말은 부분 문제 한 단계만을 고려해도 답을 찾을 수 있다는 의미이다. 모든 단계를 고려하는 동적 계획법의 풀이가 틀릴 이유가 없다. 그럼에도 불구하고 그리디 알고리즘을 사용하는 이유는 동적 계획법에 필요한 메모리나 시간이 과도하게 크기 때문이다.

애매하다... 여기까지는 이론적인 부분이고 실제 문제에 적용하면서 감을 잡아보자.

예제

  • 출전 순서 정하기 (문제 ID: MATCHORDER, 난이도: 하)

  • 그리디 알고리즘 구상

    • 맨 앞 경기부터 한 명씩 출전할 한국 선수를 정한다. 상대방 선수보다 레이팅이 같거나 높은 한국 선수가 있는 경우 그중 레이팅이 가장 낮은 선수를 상대방 선수와 매칭시킨다. 만약 상대방 선수가 한국팀의 모든 선수보다 레이팅이 높다면 남은 선수 중 가장 레이팅이 낮은 선수와 경기시킨다.

  • 탐욕적 선택 속성 증명

    • 어차피 질 경기라면 가장 레이팅 낮은 선수를 내보내서 지는 것이 이득이고, 이길 수 있는 경기라도 레이팅이 높은 선수는 가능한 한 아껴두는 것이 좋다.

  • 최적 부분 구조 증명

    • 첫 번째 경기에 나갈 선수를 선택하고 나면 남은 선수들을 경기에 배정하는 부분 문제가 발생한다. 이 때 남은 경기에서도 당연히 최다승을 얻는 것이 좋으니 최적 부분 구조도 자명하게 성립한다.

완전탐색으로 접근 가능 -> 시간복잡도: n!
DP로 접근 가능 -> 시간복잡도: O(n * 2^n)

🖥️ 정답

  • Python (직접 구현)
C = int(input())

for _ in range(C):
    win = 0
    member = int(input())
    ru = list(map(int, input().split()))
    kr = list(map(int, input().split()))

    ru.sort(reverse=True)   # 내림차순, 레이팅이 높은 순서대로 정렬
    kr.sort()   # 오름차순, 레이팅이 낮은 순서대로 정렬

    for i in range(member):
        if ru[i] > kr[-1]:
            continue
        else:   # 한국 선수의 레이팅이 같거나 클 경우 승리
            kr.pop()
            win += 1

    print(win)
  • C++ (algospot에서 가장 빠른 답안 가져옴)
#include <iostream>
#include <algorithm>
using namespace std;

#define endl "\n";
int N;
int Russia[100];
int Korea[100];
bool check[100] = { false, };

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int C;
	cin >> C;
	while (C--) {

		cin >> N;
		for (int i = 0; i < N; i++) {
			cin >> Russia[i];
		}
		for (int i = 0; i < N; i++) {
			cin >> Korea[i];
		}

		for (int i = 0; i < N; i++) {
			check[i] = 0;
		}

		sort(Russia, Russia + N);
		sort(Korea, Korea + N);
		int score = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (check[j] == false && Korea[j] >= Russia[i]) {
					score++;
					check[j] = true;
					break;
				}
			}
		}
		cout << score << endl;
	}
	return 0;
}

🤔 풀어보기 + 생각해보기

  • 시간 및 메모리 제한
프로그램은 10초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.
  • 입력
입력의 첫 줄에는 테스트 케이스의 수 C(C<=300)가 주어집니다. 
각 테스트 케이스는 세 줄로 구성됩니다. 
첫 줄에는 도시락의 수 n(1<=n<=10000)이 주어집니다. 
두 번째 줄에는 n개의 정수로 각 도시락을 데우는 데 걸리는 시간이 주어지며, 
세 번째 줄에는 역시 n개의 정수로 각 도시락을 먹는 데 걸리는 시간이 주어집니다.
  • 출력
각 테스트 케이스마다 한 줄에 점심을 먹는 데 걸리는 최소 시간을 출력합니다. 이 값은 항상 2^31보다 작습니다.
  • 예제 입력
2
3
2 2 2
2 2 2
3
1 2 3
1 2 1
  • 예제 출력
8
7

마무리

  • DP와 분할 정복의 경우, 모든 상황을 고려해 최적해를 도출하지만, 그리디 알고리즘의 경우 모든 상황을 고려하지 않고 최적해를 도출해낸다.

✏️ HOMEWORK

문자열 합치기 (문제 ID: STRJOIN, 난이도: 중)

  • 풀이

    예제 분석을 통한 그리디 직관 얻기
    문자열: 3 1 3 4 1
    문자열의 길이 1과 1을 먼저 연결
    1 + 1 = 2
    문자열의 길이 3과 3을 연결
    3 + 3 = 6
    문자열의 길이 2와 6을 연결
    2 + 6 = 8
    문자열의 길이 8과 4를 연결
    8 + 4 = 12
    따라서 총 비용은 26

    문자열: 1 1 1 1 1 1 1 2
    문자열의 길이 1과 1을 연결
    1 + 1 = 2
    문자열의 길이 1과 1을 연결
    1 + 1 = 2
    문자열의 길이 1과 1을 연결
    1 + 1 = 2
    문자열의 길이 1과 2를 연결
    1 + 2 = 3
    문자열의 길이 2와 2를 연결
    2 + 2 = 4
    문자열의 길이 2와 3을 연결
    2 + 3 = 5
    문자열의 길이 4와 5를 연결
    4 + 5 = 9
    따라서 총 비용은 27

    문자열을 합칠때마다 합쳐지는 문자열들의 총 길이가 전체 비용에 더해진다.
    그러므로 가장 짧은 두 문자열부터 합쳐나가야 가장 적은 비용으로 전체 문자열들을 합칠 수 있을 것이다.

    즉, 가장 짧은 문자열은 우선순위가 가장 높다고 볼 수 있다. 따라서 BST 기반의 heap을 사용하면 효율적으로 문제를 해결할 수 있을 것이라 생각했다. heap의 삽입과 삭제의 시간복잡도는 O(logN)이기 때문이다.

  • 정답 코드

# STRJOIN
import heapq as hq  # priority queue

def greedy(heap_queue):
    total = 0
    while len(heap_queue) > 1:  # heap_queue의 길이가 1이면 문자열을 다 합친 것
        a = hq.heappop(heap_queue)
        b = hq.heappop(heap_queue)  
        hq.heappush(heap_queue, a + b)  # 가장 짧은 두 문자열을 합친다
        total += a + b
    return total

c = int(input())

for _ in range(c):
    n = int(input())
    str_list = list(map(int, input().split()))
    hq.heapify(str_list)
    cost = greedy(str_list)
    print(cost)
profile
Wonjun
성장 = 학습 + 적용 + 회고
이전 포스트

동적 계획법 테크닉

0개의 댓글