전체 글 (70) 썸네일형 리스트형 백준 회의실 배정 성공(1931) 그리디를 이용한 방배정 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 간단하게 빨리 끝나는 회의실 순으로 최적의 해를 구하면 된다. 그리고 빨리 시작하는 회의실을 잡아야하는데 그게 예시로 5-10, 10-10 두개의 회의를 사용해야하기 때문에...? 저게 말이되나... 일단 그렇다 package greedy; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Pri.. 백준 동전 0(11047) 그리디 문제를 하나 풀어본다. https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 가장 간단한 그리디 알고리즘 문제이다 현재 상황에서 최적의 상태를 체크해서 코인 개수를 구하고 나머지로 계속 반복하면 된다. package greedy; import java.io.*; import java.util.StringTokenizer; public class Q11047 { public sta.. 그리디 알고리즘 그리디 알고리즘 그리디 알고리즘이란 최적화 문제를 해결하는 알고리즘, 각 단계에서 지금 당장 최적의 선택을 계속해서 내려가면서 최종적으로 전체적으로 최적해를 찾아내는 방식이다. 예를 들어 최소 스패닝 트리, 최단 경로, 배낭 문제 등에 적용 할 수 있다. 다음과 같은 구조를 같습니다. 1. 해의 후보 중에 하나를 선택합니다. 2. 선택한 후보가 문제의 제약 조건에 부합하는지 확인합니다. 3. 부합한다면, 선택한 후보를 정답에 추가하고, 문제의 제약 조건을 수정합니다. 4. 제약 조건을 만족할때까지 1-3단계를 반복합니다. 각 단계에세 지금 당장의 최적인 선택을 하기에, 전체적인 최적해를 찾기 위해선 이러한 선택이 계속 이루어져야 합니다. 하지만, 항상 최적의 해를 보장하지 않습니다. 대표적인 문제로는 동.. 이전 1 ··· 18 19 20 21 22 23 24 다음
