그리디(Greedy) 알고리즘이란?
그리디 알고리즘은 탐욕 알고리즘이라고도 불린다. 여러 경우 중 하나를 결정해야 할 때마다, 현재 상황에서 최적이라고 생각되는 경우를 선택하여 정답를 구하는 알고리즘이다. 그리디 알고리즘은 현재의 선택이 나중에 미칠 영향을 고려하지 않기 때문에, 항상 최적해를 보장하는 건 아니다. 그래서 그리디는 주로 근사치 추정에 활용된다.
알고리즘 문제를 풀 때, 그리디로 풀 수 있는지 여부를 빠르게 판단하는 것이 중요하다. 보통 그리디 알고리즘 문제의 경우 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준이 제시되어 있다.
그리디 알고리즘의 정당성
그리디 알고리즘이 이 문제의 최적해를 보장하는가?를 판단하는 기준은 다음과 같다.
- 탐욕적 선택 속성(greedy choice property)
- 탐욕적 선택이 항상 최적해를 보장해야한다.
- 최적 부분 구조(potimal substructure property)
- 하나의 선택을 하면 풀어야 할 하위 문제가 남아야 한다. (Top-down 방식)
💡대표적인 그리디 알고리즘 종류
| 알고리즘 | 목적 | 설명 | |
|---|---|---|---|
| Prim | N개의 노드에 대한 최소 신장 트리(MST)를 찾는다. | 서브트리를 확장하면서 MST를 찾는다. | 그래프 |
| Kruskal | 위와 동일 | 사이클이 없는 서브 그래프는 확장하면서 MST를 찾는다. | 그래프 |
| Dijkstra | 주어진 정점에서 다른 정점들에 대한 최단 경로를 찾는다. | 주어진 정점에서 가장 가까운 정점을 찾고, 그 다음을 정점을 반복해서 찾는다. | 그래프 |
| Huffman tree & code | 문서의 압축을 위해 문자들의 빈도수에 따라 코드 값을 부여한다. | 출현 빈도가 낮은 문자부터 선택해서 이진 트리를 완성하고 코드 값을 부여한다. | 문자열 |
🎈Greedy(탐욕 기법) vs DP(동적 계획법)
| Greedy | DP |
|---|---|
| 매 단계에서 가장 좋게 보이는 것을 선택한다. → 지역 최적 선택(local optimal choice) | 매 단계의 선택은 해결한 하위 문제의 해를 기반으로 한다. |
| 하위 문제를 풀기 전에 (탐욕적) 선택이 먼저 이루어진다. | 하위 문제가 우선 해결 된다. |
| Top-down 방식 | Bottom-up 방식 |
| 일반적으로 빠르고 간결하다. | 좀 더 느리고 복잡하다. |
대표 문제 1
문제의 point > 최대 몇 대의 화물차가 도크를 이용할 수 있는지를 출력하시오.
for tc in range(1, int(input())+1):
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
arr.sort(key = lambda x: x[1]) # 작업 종료 시간을 기준으로 정렬
ed = arr[0][1] # 선택 작업의 종료 지점
cnt = 1 # 도크를 사용한 화물차의 개수
for i in range(1,N):
if arr[i][0] >= ed:
cnt += 1
ed = arr[i][1]
print(f'#{tc} {cnt}')대표 문제 2
문제의 point > 최소 개수로 거슬러 주기 위하여 각 종류의 화폐가 몇 개씩 필요한지 출력하여라.
for tc in range(1, int(input())+1):
money = int(input())
coin = [50000,10000,5000,1000,500,100,50,10]
result = [0]*8
for i in range(8): # 가장 큰 금액의 화폐부터 몫을 저장해줌
if money >= coin[i]:
result[i] += money//coin[i]
money = money%coin[i]
print(f'#{tc}')
print(*result)대표 문제 3
def isbabygin(lst): # 베이비진을 확인하는 함수
flag = False
for i in range(len(lst)):
if lst[i] == 3: # 같은 카드 세 장이면
flag = True
break
if i < len(lst)-2:
if lst[i]>=1 and lst[i+1]>=1 and lst[i+2]>=1: # 연속된 카드 세 장이면
flag = True
break
return flag
for tc in range(1, int(input())+1):
arr = list(map(int, input().split()))
bst1, bst2 = [0]*10, [0]*10 # 플레이어 1, 2의 0 ~ 9 카드 개수를 저장
flag = 0
for i in range(12):
if i%2 == 0:
bst1[arr[i]] += 1
if isbabygin(bst1):
flag = 1
break
else:
bst2[arr[i]] += 1
if isbabygin(bst2):
flag = 2
break
print(f'#{tc} {flag}')🎈추가 문제
연봉 200억의 소녀, 콩순이 개발자 성공 신화