Greedy(5)
-
[알고리즘] 2457. 공주님의 정원
0. 문제 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 1. 문제 이해 Greedy 정렬 회의실 배정(Activity-Selection) 문제는 아닌 것 같다. 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ2457 { sta..
2024.03.05 -
[알고리즘] 1183. 동전 자판기 (하)
0. 문제 JUNGOL code_blocks 코드 보기 www.jungol.co.kr 1. 문제 이해 그리디 - 동전자판기 변형 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class JOL1183 { static int W, allMoney, useCnt; static int[] cnt, ret; static final int[] coins = { 500, 100, 50, 10, 5, 1}; public static void main(String[] args) throws Exception { BufferedReader br = new Buffere..
2024.02.19 -
[알고리즘] 1828. 냉장고
0. 문제 JUNGOL code_blocks 코드 보기 www.jungol.co.kr 1. 문제 이해 그리디 알고리즘 - Activity-Selection Problem 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class JOL1828 { static int N; static Thing[] arr; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamRead..
2024.02.19 -
[알고리즘] 1931. 회의실 배정
0. 문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 1. 문제 이해 그리디 알고리즘 - Activity-Selection Problem 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; public class BOJ1931 { private static class Meeting implements Comparable { int start, end; ..
2024.02.18 -
[Java] Greedy algorithm
1. Greedy algorithm 문제 상황 : 최적해를 구하기 위해서 사용되는 근사적인 방법. (보통 최대 또는 최소를 구한다.) 원리 : 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 한계 : 각 선택 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었을 때, 그것이 반드시 최적이라고 보장할 수 없다. : 대부분의 그리디 알고리즘은 몇몇 단순하고 제한된 문제에 적용된다. 필수 조건 : 원문제의 최적해 = 탐욕적 선택 속성 + 최적 부분 구조 : 탐욕적 선택이 최적해로 이어진다는 것을 증명해야 한다. (탐욕적 선택 속성) : 하나의 선택을 풀면 하나의 하위 문제가 ..
2024.02.18