그리디
나는야 욕심쟁이!
미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법
= 지역적으로는 최적의 선택이지만 최종적으로는 최적의 선택이라는 보장이 없음
🩵 그리디는 언제 써?
- 탐욕스런 선택 조건 (Greedy choice property): 앞의 선택이 이후의 선택에 영향을 주지 않는다
- 최적 부분 구조 조건 (Optimal substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다
위의 조건이 성립하지 않아도 그리디 알고리즘은 주로 계산 속도가 빠르기 때문에 근사 알고리즘으로 사용이 가능할 수 있다.
근사 알고리즘 (Approximation Algorithm): 최적화 문제에 대한 해의 근사값을 구하는 알고리즘으로, 가장 최적화되는 답을 구할 수는 없어도 비교적 빠른 시간 내에 어느 정도 보장된 근사해를 계산할 수 있다.
🩵 그리디 어떻게 써?
1. 바로 지금 최적의 해답을 선택한다!
2. 내가 선택한 해가 문제의 조건을 만족하나?
3. 원래의 문제가 해결되었는지 검사하고, 해결되지 않았으면 1로 돌아가자
선택절차 (Selection Procedure), 적절성 검사 (Feasibility Check), 해답 검사 (Solution Check)
🩵 매트로이드
매트로이드: 탐욕 알고리즘이 언제나 최적해를 찾아내는 특별한 구조
(예) 편의점에서 손님이 과자를 3150원어치 사고, 5000원을 냈을 때 최소한의 동전 개수로 잔돈을 거슬러줄 수 있는 방법은? 잔돈은 동전으로만 준다고 가정한다.
어떻게 거슬러 주어야 할까?
- 거스름돈은 총 1850원.
- 최대 동전 금액인 500원부터 최대 개수로 돌려준다
- 500원 3개 > 100원 3개 > 50원 1개
그리디를 적용하면?
- 선택 절차: 현재 가장 가치가 높은 동전을 우선적으로 선택한다
- 적절성 검사: 1단계에서 선택한 동전들의 합이 거슬러 줄 금액을 초과하는지 검사하고, 초과하면 마지막으로 선택한 동전을 삭제하고 더 작은 동전을 선택한다
- 해답 검사: 선택한 동전들의 합이 거슬러 줄 금액과 일치하는지 검사 & 부족하면 1번부터 반복
n = 1850
count = 0
coins = [500, 100, 50, 10]
for coin in coins:
count += n // coin
n %= coin
print(count)화폐의 종류가 K개일 때, 시간복잡도는 O(K)
🩵 그리디 연습문제
같이 빨리 해보긔: 12845
각자 풀어보긔:
- 1202 (보석 도둑)
- 14698 (전생술)
- 1461 (도서관)
투포인터
투포인터: 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
포인터가 두개!
🩵 투포인터는 언제 써?
전체 for loop을 돌리면 시간초과 나는 경우 등
🩵 투포인터는 어떻게 써?
start,end과 같은 포인터 2개를 준비한다 (또는left,right)- 시작할 때
start = end = 0이고,start <= end조건을 항상 만족한다 - 2개의 포인터는 현재 부분 배열의 시작과 끝을 가리킨다
start = end인 배열은 크기가 0인, 아무것도 포함하지 않은 배열이다
🩵 특정합을 갖는 부분 연속 수열 찾기
- 시작점과 끝점이 첫 원소의 인덱스를 가리킨다
- 현재 부분 합이 M과 같으면 카운트를 증가시킨다
- 현재 부분 합이 M보다 작으면 end를 1 증가시킨다
- 현재 부분 합이 M보다 크거나 같으면 start를 1 증가시킨다
- 모든 경우를 확인할 때까지 2-4번 과정 반복
🩵 투포인터 연습 문제
- 2470 (두 용액)
- 1806 (부분합)
- 1253 (좋다)
참조:
https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/
https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md
