알고리즘 학습을 위해 백준 문제집을 풀어보고 기본기가 부족하다 생각되어 바킹독님의 강의를 학습하고 이를 글로 정리하기로하였습니다.
이전강의는 아직 정리하지않아서 완강을 한뒤 추후 복습을 하며 다시 글을 작성해볼계획입니다.
그리디
그리디 = 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘
= 관찰을 통해 탐색범위를 줄이는 알고리즘
현실적인 풀이 흐름
1.관찰을 통해 탐색 범위를 줄이는 방법을 고안한다
2.탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿음을 가진다
3.믿음을 가지고 구현한다
BOJ 11047번 동전:0
DP를 문제를풀경우 O(NK) 는 10억을 넘어서 틀림
증명을 통해 문제를 해결해야함
동전을 최소로 소모하면서 물건값을 지불하기위해선 가장 비싼 동전을 많이 사용해야한다
