그리디6 CSES PS - Towers (그리디, sorting) https://cses.fi/problemset/task/1073 sorting and searching으로 분류된 것으로 볼때, 무작위 크기를 순서대로 multiset에 넣으면서 처리하는 것에 주목하라는 의미인 듯 하다. 큐브를 이용해서 타워를 쌓을 것이다. (큰 큐브 위에 작은 큐브를 올리거나, 새로운 타워의 기반으로 사용하거나) n개의 큐브의 크기가 주어질 때, 모든 큐브를 사용해서 만들 수 있는 타워의 최소개수를 구해라. (반드시 입력 순서대로 처리해야 한다.) i번째 큐브를 이용해서 타워를 쌓을 땐, 그보다 약간 큰 큐브 위에 두는 게 최적이다. int main() { FAST; int n; cin >> n; multiset st; while (n--) { int a; cin >> a; auto.. 2020. 1. 13. 그리디 1. 그리디로 항상 최적해를 구할 수 있다면, 그리디는 dp보다 훨씬 빠르다. (그리디로 풀리면 보통 dp로도 풀린다) 2. 시공간 제약으로 인해 최적해를 찾는 것이 극히 제한되는 경우, 근사해를 찾아준다. ps에선 1번 용도로만 사용된다. 근사해 찾기는 조합탐색이나 메타휴리스틱을 사용한다. 탐욕적 선택 속성(greedy choice property) : dp처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있는 속성 최적 부분 구조(optimal substructure) : dp처럼 부분 문제의 최적해에서 전체 문제의 최적해를 만들수 있는지 ->대부분 자명해서 증명할 필요가 없는 경우가 많다. 하지만 예외 존재 알고리즘이 위 두 속성을 만족하는지 검증해야 한다. 1. 활동.. 2019. 12. 18. 이전 1 2 다음
