그리디
-
그리디 알고리즘공부/알고리즘 2021. 5. 29. 14:16
그리디 알고리즘이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법->매순간 가장 좋아보이는 것을 선택, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형 ex)가장 큰 순서대로, 가장 작은 순서대로 *다익스트라 알고리즘은 그리디 알고리즘이면서 암기가 필요한 알고리즘 그리디 알고리즘의 정당성 모든 문제에 적용할 수 있는 것은 아님->탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을때 사용! 대표적 그리디 알고리즘 문제 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔,..