코드 플러스 중급 그리디 알고리즘

그리디 알고리즘 -결정해야 할때 그 순간 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘. -거스름돈 문제가 대표적인 문제지만, 모든 문제가 그런것은 아니다. -그리디 알고리즘은 증명이 어렵다 관련문제 : 11047번(동전 0) a[i]가 a[i-1]의 배수이므로 그리디 알고리즘을 사용하여도 문제가 없다. 다만 배수라는 조건이 없다면 다이나믹 프로그래밍을 통해서 해결하는 것이 옳다. cost[i]= cost[i-coint[k]]+1 1931번 (회의실 배정) 정렬하는 문제. 가장 빨리 끝나고 가장 빨리 시작하는 순서대로 정렬하면 편하다 11399번 (atm) 증명으로 가능 pf ) i번째 사람이 일을 보는데 시간을 p(i)라고 하면 i번째 사람이 기다려야 하는 시간은 시그마(1 각 자리수를 ..

2019.09.03