그리디 알고리즘!
예전에 학교에서 알고리즘 시간에(최애 교수님 수업이었는데 공부를 안해서 씨쁠받음ㅎ) '그리디'알고리즘이라는 단어를 듣고 되게 이름 독특하네...라고 생각했다.
이름 값(?)하는 알고리즘이었달까....
그때 열심히 공부할걸이라는 생각이 들지만ㅋㅋ 다시 한 번 정독하면서 코테 준비를 해야겠다.
1. 그리디 알고리즘이란?
그리디(Greedy) 알고리즘?
- 현재 상황에서 당장 좋은 것을 선택하는 방법
- '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해 주는 경우가 많음.
단순 암기로, 푸는 방식을 안다고해서, 잘 풀리는 유형은 아니다.
문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이 중요!
2. 대표 예시
- 거스름돈 문제
시간복잡도 O(N) : 화폐 종류만큼 순회
n = 1260 # 거스름돈
cnt = 0
coins = [500, 100, 50, 10]
# 동전의 종류를 순회하면서 체크한다
for coin in coins:
cnt += n // coin
n %= coin # 나머지 거스름돈
print(cnt)3. 그리디 알고리즘이 가능한 이유?
2번 거스름돈 문제가 그리디로 풀릴 수 있는 이유는, 큰 단위의 동전이 항상 작은 단위 동전의 배수이기 때문이다.
→ 무슨 말이게?
500원은 100, 50, 10의 배수, 100원은 50, 10의 배수, 50원은 10의 배수.....
작은 단위의 동전들을 모으고 모으면 결국 큰 단위 동전이 되니, 거스름돈을 줄때 한 번에 크게 주는 것이 결국 동전을 적게 쓰게 되는 것!
공부출처: 이것이 취업을 위한 코딩테스트다 - 동빈나
