금융공기업을 준비하면서 코딩테스트를 미루고 있었는데 더 이상 미룰 수 없다....
이번 하반기에는 주금공, 예결원, 은행 등 코테가 필수적인 기업들이 많아서 준비해 보려고 합니다.
일단 이번 하반기 14일을 되기까지 기초적인 알고리즘과 관련 문제를 프로그래머스에서 풀어보는 방식으로 진행하려고 합니다!
강의는 유튜브에 유명한 동빈나님 알고리즘 강의를 참고했습니다!
문제는 아래 tistory글을 참고해서 해보려고 합니다!
https://codingdodo.tistory.com/94
그리디 알고리즘이란?
가장 좋아 보이는 것을 '반복적'으로 수행하는 알고리즘이다.
이 알고리즘은 최적해를 보장하지는 않는다!
코테 풀이 시 그리디 알고리즘이 맞는 상황은?
가장 좋아 보이는 것을 반복적으로 수행하면 최적해가 나올 것 같은 상황!!
주요 예시 : 거스름돈 문제
문제 : 1260원을 거슬러 줘야 하는데 사용하는 최소의 동전 갯수는?
답 : 500원 2개 100원 2개 50원 1개 10원 6개
주의! 근데 왜 큰 단위부터 거슬러 주는 것이 최적의 해가 될 수 있을까?
그것은 주어진 동전들이 모두 서로 배수의 관계이기 때문!
서로 배수임으로 작은 단위의 동전을 사용해도 큰 동전으로 거슬러 줄 때와 다른 결과가 나올 수 없다.
'취준 > 코딩테스트' 카테고리의 다른 글
| [백준 14467] 소가 길을 건너간 이유 -구현 (0) | 2025.09.12 |
|---|---|
| [백준 1343] 폴리오미노 - 그리디 알고리즘 (1) | 2025.08.31 |
| [백준 2212] 센서 - 그리디 알고리즘 (1) | 2025.08.31 |