728x90
728x90
그리디 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법
코딩테스트에서의 그리디 유형 - 창의력, 문제를 풀기 위한 최소한의 아이디어 떠올릴 수 있는 능력 요구
특정 문제 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만 선택해도 풀 수 있을 지 파악!
( 코테에서 어떤 문제가 바로 유형을 파악하기 어려우면 그리디 의심!
만약 그리디 해결방법 찾을 수 없다면, 다이나믹이나 그래프 알고리즘으로 해결할 수 있는지 고민)
그리디 알고리즘은 기준에 따라 좋은 것을 선택하므로, 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해준다. -> 대체로 정렬 알고리즘 사용하면 됨! 짝꿍 :)
간단한 예시 - 거스름돈)
n=1260 # 총 거스름돈
count=0
# 큰 단위인 500원 부터 처리!
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 큰 동전부터 거슬러 줄 수 있는 갯수 들 sum 구하기
n %= coin # 총 거스름돈은 거슬러 주고 남은 금액으로 갱신
'이것이 취업을 위한 코딩테스트다 python -나동빈' 책과 유튜브 강의를 보고 공부한 내용입니다.
728x90
728x90
'Algorithm > 이론' 카테고리의 다른 글
[파이썬] '최단경로' 개념 및 예제 (0) | 2021.02.09 |
---|---|
[파이썬] '다이나믹 프로그래밍' 개념 및 예제 (0) | 2021.01.06 |
[파이썬] '정렬' 개념 및 예제 (0) | 2021.01.06 |
[파이썬] 'DFS/BFS' 개념 및 예제 (0) | 2021.01.06 |
댓글