목록그리디 알고리즘 (2)

수학과의 좌충우돌 프로그래밍

[C++] BAEKJOON 1931회의실 배정

어느 회의실을 선택할지에 대해서 그리디 알고리즘 을 통해 접근합니다. 현재 순간에 최선의 선택지를 고르는 것으로 말이죠. 그렇다면 현재 순간의 최선이라면 어떤 희의를 골라야할까요? 여러 가지 경우를 생각할 수 있습니다. 시작 시간이 가장 빠른 회의, 회의시간이 가장 짧은 회의 등등 여러 경우가 있지만 각각은 반례가 존재하고 정답은 종료시간이 가장 빠른 회의입니다. 언제 시작하더라도 얼마나 회의를 하더라도 가장 빠르게 종료한다면 다음 회의를 진행하는데 있어서 유리합니다. https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net #include #include #includ..
알고리즘/C++ 2019. 9. 14. 16:55
[Algorithm] 그리디 알고리즘

그리디 알고리즘은 한국어로 탐욕 알고리즘 이라고도 하며 결정해야 하는 순간 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘을 말합니다. 이 방식의 한계점은 그 순간에는 최적일지도 모르지만 최종적으로는 답이 아닐 수 있는 경우가 많기 때문에 그리디 알고리즘을 사용한 경우, 최적이라는 걸 입증하는게 쉽지 않습니다. 그래도 입증만 한다면 구현하는건 다른 알고리즘에 비해 쉬운 편입니다. 문제를 풀면서 이해해보도록 하겠습니다. BAEKJOON 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. ..
알고리즘/이론 2019. 9. 14. 16:18
Prev 1 Next

티스토리툴바