탐욕(Greedy) 알고리즘

그리디알고리즘이란?

단순 무식하게, 현재 상황에서 최선의 선택만을 하는 알고리즘이다.

그리디 알고리즘은 매 순간 최선의 선택만을 하므로,이후의 상황에 대해서는 전혀 고려하지 않는다

그리디 알고리즘은 모든 상황을 고려하는 것이 아니기 때문에 시간을 크게 절약할 수 있다.

그리디 알고리즘의 조건

그리디 알고리즘을 사용하기 위해서는 크게 2가지 조건을 만족해야 한다.

1. 탐욕스러운 선택 속성(Greedy Choice Property)

   현재의 선택이 이후의 선택에 영향을 주지 않아야 한다.

2. 최적 부분 구조(Optimal Substructure)

   전체 문제의 최적 해결 방안이 부분 문제의 최적 해결 방안이어야 한다.

그리디 알고리즘 문제

거스름돈 문제

큰 단위의 거스름돈이 작은 단위의 거스름돈의 배수가 될 때

이 문제에서 우리가 생각할 수 있는 것은 ‘가장 큰 단위의 돈부터 생각하자’ 입니다.

활동 선택 문제

이 문제는 시간표짜기, 회의실 시간 분배 문제와 비슷한 문제 유형에 해당합니다.

활동 선택 문제란, 한 강의실에서 여러개의 수업을 하려고 할 때

한번에 가장 많은 수업을 할 수 있는 경우를 고르는 것입니다. (수업 시작 시간, 수업 종료 시간)