개념
- 그리디, 탐욕법, 욕심쟁이 알고리즘
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 문제를 해결
- 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘
- 매 순간 가장 좋아보이는 것을 선택하며, 나중에 미칠 영향에 대해서는 고려하지 않음
그리디 알고리즘들
- 활동 선택 문제 (activity-selection problem)
- 여러개의 경쟁 활동이 주어졌을 때 겹치지 않고 시간을 선택해 스캐줄을 짜는 문제
- 최소 신장 트리 (minimun-spanning-tree)
- 그리디 방법의 고전적인 예
- 신장 트리 : 그래프 내의 모든 정점을 포함하는 트리
- 최소 신장 트리 : 간선의 가중치를 고려해 최소 비용의 신장 트리를 선택한 것
- 다익스트라 (Dijkstra)
- 한 개의 시작점으로 부터 가장 빠른 경로를 구하는 알고리즘
- 집합 감싸기 (set-covering)
- 전체 집합 U와 그 부분 집합 Si들을 원소로 갖는 집합 F가 있을 때, F의 원소인 Si들을 합집합하여 전체 집합 U와 같아지는 집합 Si들의 최소 갯수를 찾는 문제
- 휴리스틱 (heuristics)
- 불충분한 시간이나 정보로 인하여 합리적 판단을 할 수 없거나, 체계적이면서 합리적인 판단을 굳지 필요로 하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편 추론법
- 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하는 방법
- 매트로이드 (matroid)
- 그리디 알고리즘이 최적해를 가려낼 수 있는 경우인지를 판별할 수 있게 해주는 수학적 공간
- 어떤 문제의 공간이 매트로이드 구조이면, 이 문제의 그리디 알고리즘이 최적해를 도출해 낼 수 있음
- 단, 최적해를 갖는 모든 그리디 알고리즘이 매트로이드 구조를 띄는 것음 아님
- 허프만 코드 (huffman code)
- 문자열 데이터를 효율적으로 압축하는데 사용되는 그리디 알고리즘
- 압축하고고자 하는 문자열에서 자주 등장하는 문자는 짧은 비트로 표현하고 거의 등장하지 않는 문자는 긴 비트로 표현 (가변 길이 코드)
- 트리 형태로 빈도수에 따라 자주 등장하는 문자는 짧은 탐색으로 찾을 수 있게 처리
그리디 알고리즘을 만드는 단계
- 하나의 선택을 할 경우 풀어야 할 부분 문제도 하나만 남도록 최적화 문제를 변경한다.
- 그리디한 선택이 언제나 안전하도록 원래 문제의 최적해들 중에서 그리디한 선택을 하는 것이 반드시 존재함을 증명한다.
- 그리디한 선택을 했을 때, 그리디한 선택과 남아 있는 부분 문제에 대한 최적해와 결합하면 원래 문제에 대한 최적해를 얻음을 보여 최적 부분 구조를 가진다는 것을 보인다.
그리디한 선택 특성
선택을 할 때, 부분 문제들의 결과를 고려하지 않고, 현재 고려중인 문제에서 최적으로 보이는 선택을 취함
→ 동적 계획법에서는 단계마다 선택을 할 때, 부분 문제의 해에 의존함
→ 상향식 접근으로, 작은 부분 문제에서 큰 문제로 풀어나가는 방법을 취함 (메모이제이션을 통한 하향식 접근)
하향식 방법으로 진행
- 주어진 문제를 더 작은 문제로 만드는 선택을 함
최적 부분 구조 (optimal substructure)
어떤 문제에 대한 최적해가 그 문제의 부분 문제에 대한 최적해를 포함한 형태
그리디와 동적 계획법(DP)
그리디와 동적 계획법은 모두 최적 부분 구조를 이용하므로 다음 두가지의 문제가 발생할 수 있음
- 그리디 해법으로 충분히 풀릴 수 있는 문제를 동적 계획법으로 해결하려 하는 문제
- 동적 계획법으로 풀어야 할 문제를 그리디로 잘못 적용하는 문제
→ 그리디 방법으로 풀 수 없는 많은 중복되는 부분 문제를 갖는 경우 동적 계획법을 이용해 풀어야 함
코딩테스트에서의 그리디
- 코딩테스트 수준에서는 다른 알고리즘과 비교해 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형
- 보통 그리디 유형 문제는 창의력을 통해 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구
- 그리디는 매우 다양한 문제 유형이 있어 단순 암기로 항상 잘 풀 수 있는 유형이 아님
- 많은 유형을 접해보고 해결할 수 있는 아이디어를 빠르게 떠오를 수 있게 하는 것이 중요
- 좋은 것을 선택할 기준으로 정렬과 함께 짝을 이뤄 출제되는 경우가 많음
- 바로 문제 유형을 파악할 수 없는 문제라면 그리디 알고리즘을 의심해 보고, 그리디로도 해결법이 나오지 않는다면 다이나믹 프로그래밍이나 그래프를 이용해야 할 수 있음.
문제
거스름돈
음식점 카운터에서 손님에게 N원을 거슬러 줘야할 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 거스름돈으로 사용할 동전은 500원, 100원, 50원, 10원이 무한히 존재하며, 거스름돈 N은 항상 10의 배수다.
문제 해설
가장 큰 화폐 단위부터 가능한 갯수를 채워 거슬러 준다.
- 시간 복잡도
- O(k) : k는 화폐의 종류
코드
coins = [500, 100, 50, 10]
N = int(input())
cnt = 0
for i in coins:
cnt += N // i
N %= i
print(cnt)
<aside> 💡 화폐단위가 서로 배수 관계에 있으므로 탐욕적으로 접근했을 때 가능한 것이다. 그렇지 않다면 하위 화폐를 다수 쓰는게 더 적은 개수를 사용할 수도 있을 것이다. 이렇게 아이디어를 떠올리고 그것이 정당한지 검토할 수 있어야 답을 도출 할 수 있다
</aside>
큰수의 법까지
주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙 단, 배열의 특정 인덱스에 해당하는 수가 연속해서 k번 초과해서 더할 수 없음
문제 해설
가장 큰 수와 두번 째로 큰 수만을 더하면 되는 문제
가장 큰 수를 K번 더하고 두번 째 큰 수를 1번 더함을 반복해 M번을 더함
→ (큰 수) * k + (작은 수) 가 M // (k+1) 번 반복됨을 이용해 더 효율적으로 계산이 가능함
코드
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
# 입력받은 수를 내림차순 정렬한 리스트 생성
li = sorted(list(map(int, input().split())), reverse=True)
# 규칙적으로 반복되는 횟수만큼 곱해주고, 나머지는 가장 큰 수의 횟수로 계산
print((li[0] * k + li[1]) * (m // (k + 1)) + (li[0] * (m % (k + 1))))
숫자카드게임
행열이 N*M인 숫자 카드 중에서 행에서 가장 낮은 숫자 중에 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임
문제 해설
각 행마다 가장 작은 수를 찾고 그 중에서 가장 큰 수를 찾으면 되는 간단한 게임
min(), max() 함수를 이용하면 간단하게 구할 수 있음
코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split()) # n:행 / mㅣ열
minList = [] # 행에서 가장 작은 수를 담는 리스트
for i in range(n):
row = list(map(int, input().split())) # 행 입력
minList.append(min(row)) # 행에서 가장 작은 수 담기
print(max(minList)) # 가장 작은 수들 중 가장 큰 수 출력
1이 될 때까지
어떤 수 N이 주어졌을 때 다음 두 과정 중 하나를 반복해 1이 될 때 까지 과정을 몇 번 반복했는지 구하는 문제
- N에서 1을 뺌
- N을 K로 나눔
문제 해설
나눗셈을 했을 경우 N을 크게 줄일 수 있으므로 최대한 많이 나누게 하는 문제. N이 K로 나누어 떨어질 때까지 1씩 빼주고 나누어 떨어지면 나누면서 횟 수를 카운트 하는 것은 N이 1이 될 때 까지 반복.
1씩 빼주는 과정을 N이 K로 나누어 떨어질 때 까지 반복하므로 N을 K로 나눈 나머지를 카운트에 더해주고 N에서 한번에 빼주면 반복 횟수를 줄일 수 있음
코드
import sys
input = sys.stdin.readline
# 최대한 많이 나누기
n, k = map(int, input().split())
result = 0
while n != 1: # n이 1이 될 때까지 반복
if n % k == 0: # k가 n의 배수이면
n = int(n / k) # 나누기
result += 1 # 카운트
else:
result += n % k # n이 k에 나누어 떨어질 때까지 한번에 카운트
n -= (n % k) #한번에 빼기
print(result)
백준 문제