그리디 알고리즘

취업을 위해 코딩테스트 공부를 하게되었는데, 대학교 3학년때 알고리즘과 자료구조에서 배운 지식이 남아있지만 초심으로 돌아가 잊고있던 지식들까지 복기한다는 마음으로 한 권의 책을 골라 다시 코테공부를 시작하게 되었다.

그간의 코딩테스트 공부는 프로그래머스나 백준의 문제들을 푸는 방식으로 하였는데,
워낙 온라인에 나와있는 코딩문제는 다양하고 알맞은 문제를 선정하는 것에도 시간이 많이 걸린다는 단점으로,
책 한권을 차근차근 따라간 후 유사문제들을 백준과 프로그래머스로 풀 예정이다.

그리디, 구현, DFS/BFS, 정렬, 이진탐색, 다이나믹 프로그래밍, 최단경로, 그래프이론 순으로 공부를 할 것이며
이것은 그것의 첫장, 그리디이다.

여기서 말한 이 책이란
이것이 취업을 위한 코딩 테스트다 with 파이썬라는 책이다.

그리디란

그리디란 바로 탐욕이라는 뜻이다. 탐욕적으로 문제를 풀어나가는 것, 다시말해
"현재 상황에서 좋은 것을 고르는 것"이 기본 방법이다.

그리디 알고리즘의 예시

그리디 알고리즘의 대표적인 예시는 거스름돈이다.

거스름돈으로 거슬러 줄 돈을, 가장 큰 화폐부터 거슬러 주기 때문에, 다른 것은 고려하지 않아도 되는 것이다.

//거스름돈 코드
money = 1260 #money는 건네주는 돈

count = 0 #count는 거슬러주는 동전의 개수

coin_types = [500, 100, 50, 10] #큰 단위 화폐부터 차례대로 확인

for coin in coin_types:
    count += money //coin #해당 화폐로 거슬러줄 수 있는 동전 세기
    money %= coin

print(count)

해당 포스팅의 개념, 코드, 이미지는 밑 책을 바탕으로 작성되었습니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬