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

오늘은 그리디 알고리즘을 공부해보는 시간을 가져봅시다 

 

그리디 알고리즘이란

Greedy(탐욕) + Algorithm, 탐욕 알고리즘이라고도 합니다.

 

왜 탐욕 알고리즘이라 불리는 걸까요?

그 이유는 탐욕 알고리즘의 특성을 살펴보면 알 수 있는데요.

 

탐욕 알고리즘은 여러 가능성 중 가장 최선의 선택을 찾는 알고리즘입니다. 

최선의 기준에 따라 가장 적합한 경로, 최적해를 찾아내는데

여기서 최선의 기준이 Max 혹은 Min이 됩니다. 

 

 

문제의 종류와 목적에 따라 판단 기준이 다르겠지만,

각 단계에서 어떤 값을 최소화하거나 최대화하도록 선택하는 것이

그리디 알고리즘의 핵심이라 볼 수 있는데요. 

최소화 문제, 최대화 문제는 그리디 알고리즘이 동작하는 북극성이라 생각하면 된답니다. 

 

이 과정에서 그리디 알고리즘의 이름이 Greedy(탐욕)인 이유가 나타나는데, 문제를 부분으로 나누어 해결할 때 나중을 생각하지 않고 당장 눈 앞에 보이는 가장 좋은 선택을 합니다. 

 

최소, 최대화 문제로 예시를 들어볼까요? 

최소화 문제 해결→ 최종적인 결과=최소화. 각 단계에서 가장 작은 값을 가지는 것을 선택한다.
최대화 문제 해결 → 최종적인 결과=최대화. 각 단계에서 가장 큰 값을 가지는 것을 선택한다.

 

몇 번을 선택하실 건가요? 저라면 최종적인 거리가 가장 짧은 2번을 선택할겁니다.

하지만 그리디 알고리즘은 1단계에서 가장 짧은 경로를 갖고있는 1번을 선택하겠지요.

 

그리디 알고리즘은 거시적 관점보단 미시적 관점을 갖고있으며,

전체적인 숲의 형상을 보기보단 당장 타파해야할 최적의 나무를 바라봅니다.

 

“지금 당장 좋은거 선택해!”, “딱 그것만 생각해!”

→ 선택한 결과의 나중을 생각하지 않고 지금 눈 앞에 보이는 가장 좋은 선택을 한답니다.

그래서 “탐욕” 알고리즘이라는 이름이 붙은거죠 🙂

 

따라서 그리디 알고리즘으로 문제에서 최적의 답을 끌어낼 수 있으려면 요구되는 조건이 두 가지 있는데요.

첫번째는 “탐욕적 선택 속성(Greedy Choice Property)“

탐욕적 선택이 항상 최적해를 보장해야한다는 조건입니다. 쉽게 풀어보면, 그 문제에 있어서 탐욕적인 선택이 가장 최선의 방법이어야 한다는거죠. 한 가지만 고려하여 풀어나가는 선택이 최선의 답을 도출해낼 수 있는 선택이어야한다는겁니다.

 

두번째는 “최적 부분 구조(Potimal Substructure Property)”

문제를 부분으로 나누어보았을 때, 각 단계에서 만족하는 최고 선택이 최종 문제에서의 최적 답을 출력해낼 수 있는 구조여야합니다.

 

예시를 들어볼까요. 아까와 같은 항공기 편 문제입니다.

여기서는 교착로?교환로? 가 분리되어 운영되고 있고,
단계마다 그리디 알고리즘이 선택할 수 있다.
가장 빠른 경로를 찾고자 하는 그리디는, 1→2→3 을 선택하게 될 것이고
이는 최종적으로 살펴보았을 때 최적해에 부합한다.
풀어보자면, 해당 부분(1),(2) 에서 만족하는 최선의 선택이
전체 문제에서도 최적의 답을 뽑아내는데 만족하는 선택이었다.

 

위 두 조건은, 그리디 알고리즘으로 최적해를 도출해낼 수 있는 조건입니다. 반대로 위 두 조건에 문제에 성립하지 않는다면, 그리디 알고리즘 최적해를 도출해내는 도구가 될 수 없다는 말이죠.

그리디 알고리즘은 근사 알고리즘으로서도 유용하게 사용됩니다. 항상 최적의 결과를 도출하지 못하지만, 어느 정보 최적에 근사한 값을 빠르게 도출할 수 있기 때문이죠.

그렇다보니 그리디 알고리즘으로 최적해를 도출해낼 수 있는가?

활용 여부를 문제에서 명확히 판단할 수 있는 것이 중요합니다.

 

그럼, 그리디 알고리즘의 문제 해결 과정을 살펴보고, 간단히 문제를 풀어볼까요?

 

그리디 알고리즘의 문제 해결 절차는,

• 선택 절차(Selection Procedure) - 현재 상태에서 최적의 해답을 선택합니다
• 적절성 검사(Feasibility Check) - 선택된 해가 문제의 조건을 만족하는지 검사합니다
• 해답 검사(Solution Check) - 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다. 

 

그럼 해결 절차를 활용해 그리디 문제를 풀어볼까요? 

*백준, 1744번 수 묶기 문제를 활용하였습니다

수열의 최대 합을 구하는 문제입니다. 단, 수열의 각 수를 묶었을 때의 경우를 고려합니다.
수열의 모든 수는 단 한 번만 묶거나, 아니면 묶지 않아야하며, 위치에 상관없이 묶을 수 있지만 자기 자신을 묶지는 못합니다. 어떤 수를 *으로 묶게되면, 수열의합을 구할 때 묶은 수는 서로 곱한 후 더해야합니다.

 

 

자 그럼 우리에게 수열 = { 0, 1, 5, -3, -4, 2, 12, -23 }; 이 주어졌다고 가정해봅시다.

우선 수의 종류에는 양수, 음수, 0이 존재하며,

양수는 양수끼리, 음수는 음수 혹은 0과 묶였을 때 최대 합을 얻어낼 수 있을겁니다

 

 

선택 절차

• 양수와 음수를 분리해야할 것입니다. 이때, 0은 따로 처리합니다
  → (양수와 묶이게 되면 손해를, 음수와 묶이게 되면 경우에 따라 이익을 도출하기 때문입니다)
  
  
• 양수 배열은 내림차순으로, 음수는 오름차순으로 정렬합니다

 

• 예외를 처리합니다
  • 1은 곱해지는 것보다 더해지는 것이 최대 합 값에 기여합니다. 따라서 수를 묶을 때, 묶는 수에 1이 포함되어 있거나 묶고 남은 수가 1일 경우 수열에 더하는 방식으로 처리합니다.
  • 0은 음수를 초기화 시킬 수 있습니다. 다만 가장 큰 마이너스 수는 서로 곱하여 최대값을 만들고, 남은 수를 초기화 시켜 음수를 없애는 것이 가장 좋겠죠?

 

 

적절성 검사

• 최선의 선택을 위해 세운 조건들이 적절한지 검사합니다.
  → 음수는 두 개씩 곱할 떄, 결과가 양수가 되고 값이 커지는 것이 적절합니다. 따라서 남는 음수가 있고 0이 있다면, 그 음수를 0과 곱해 결과적으로 무시되게 하는 것이 손실을 최소화 하는 적절한 방법입니다.
  → 양수 중 1과 다른 양수를 곱하는 것보다 더하는 것이 항상 더 큰 값을 제공합니다. 1을 더하는 것이 항상 더 큰 결과를 가져오기 때문에 적절합니다.

 

 

해답 검사

#define _CRT_SECURE_NO_WARNINGS
#define size 8
#include<stdio.h>
#include<stdlib.h>

int compare_asc(const void* a, const void* b);
int compare_desc(const void* b, const void* a); //내림차순 정렬 

int main() {

	int arr[size] = { 0, 1, 2, -3, -4, 5, 12, -23 };
	int Ncnt = 0; //음수 카운트
	int Pcnt = 0; //양수 카운트
	int* negative = NULL; // 음수 배열
	int* positive = NULL; //양수 배열
	int zero = 0; //0

	//수열값에 양수랑 음수가 어떤 비율로 들어가있을지 모르니, 동적할당 
	negative = (int*)malloc(size * sizeof(int));
	positive = (int*)malloc(size * sizeof(int));

	if (negative == NULL || positive == NULL) { //실패할 경우
		printf("동적 할당 실패");
		return -1;
	}

	//양수랑 음수 분리시켜주는 부분
	for (int i = 0; i < size; i++) {
		if (arr[i] < 0)
			negative[Ncnt++] = arr[i];
		else if (arr[i] > 0)
			positive[Pcnt++] = arr[i];
		else
			zero++;
	}

	//정렬함수. 양수는 내림차순으로, 음수는 오름차순으로 정렬시켜준다. 
	qsort(positive, Pcnt, sizeof(int), compare_desc);
	qsort(negative, Ncnt, sizeof(int), compare_asc);


	int sum1 = 0;
	int sum2 = 0;

	//양수 처리
	for (int i = 0; i < Pcnt - 1; i += 2) { // (first * second) 묶어주는 과정

		//두 수 중 하나가 1인 경우 -> 곱하기 대신 더하기 변경
		if (positive[i] == 1 || positive[i + 1] == 1) {
			sum1 += positive[i] + positive[i + 1];
		}
		//그 외는 멀쩡하게 곱하기 수행 
		else
			sum1 += positive[i] * positive[i + 1];
	}
	if (Pcnt % 2 == 1)
		sum2 += positive[Pcnt - 1]; ///남는 하나가 있을 경우, 그냥 더해주기

	//음수처리 
	for (int i = 0; i < Ncnt - 1; i += 2) {
		sum2 += negative[i] * negative[i + 1];
	}
	if (Ncnt % 2 == 1) {
		if (zero != 0)
			sum2 += negative[Ncnt - 1] * 0; //0이 존재할 경우+남는 음수 1개가 있을 경우 -> 0* 외톨이 음수
		else
			sum2 += negative[Ncnt - 1];
	}

	int sum3 = sum1 + sum2;

	free(negative);
	free(positive);

	printf("%d", sum3);
}

int compare_asc(const void* a, const void* b) {
	return (*(int*)a - *(int*)b);
}
int compare_desc(const void* a, const void* b) {
	return(*(int*)b - *(int*)a);
}

최종적으로 sum1+sum2을 합하여 최종 합을 계산합니다.

최종 합은 주어진 배열을 그리디 방식으로 최적화하여 묶었을 때의 최대 합입니다.

이 문제는 그리디 알고리즘의 특성을 따른 문제로, 각 단계에서 최적을 선택하여 전체 문제의 최적해를 구합니다

 

---

이렇게 그리디 알고리즘에 대해 살펴보았습니다

공부하는 단계라 미숙한 부분이 존재할지도 모릅니다

그 점 감안하고 봐주시면 정말 감사할 것 같고,

내용에 대한 피드백 감사히 받겠습니다 😊