GREEDY
-
[Baekjoon Online Judge] 1946번: 신입 사원문제 풀이/Baekjoon Online Judge 2020. 12. 27. 20:18
1946번: 신입 사원 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 처음 이 문제를 접했을 때 이해하는데 조금 시간이 걸렸다. 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선별한다는 원칙이 잘 이해가 되지 않았다. 예시를 들어보면, 서류심사 순위 면접시험 순위 3 2 1 4 4 1 2 3 5 5 각각의 지원자의 서류심사 성적 순위와 면접시험 성적 순위가 위 표와 같은 경우, 서류심사를 기준으로 우선 정렬하였다. 서류심사 순위 면접시험 순위 1 4 2 3 3 2 4 1 5 5 정렬..
-
[Baekjoon Online Judge] 2217번: 로프문제 풀이/Baekjoon Online Judge 2020. 12. 26. 14:04
2217번: 로프 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net n개의 로프를 활용해서 가장 무거운 중량을 구하는 문제이다. 여기서 고려해야 하는 요구사항은 k개의 로프를 사용하여 중량 w인 물체를 들어올리면, 각각의 로프는 모두 고르게 w/k 만큼 중량이 걸리게 된다. 각각의 로프는 자신이 버틸 수 있는 중량 이상을 버틸 수 없다. 마지막으로 로프는 전부 사용하지 않아도 된다. 로프를 전부 사용하지 않아도 되기 때문에 로프를 중량 내림차순으로 정렬시킨다. 버틸 수 있는 무게가 큰 순서부터 로프를 ..
-
[Baekjoon Online Judge] 5585번: 거스름돈문제 풀이/Baekjoon Online Judge 2020. 12. 26. 13:52
5585번: 거스름돈 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 물건 금액을 입력 받아 거스름돈의 동전 개수를 반환해주는 간단한 문제였다. 소비자가 내는 지폐를 1000으로 한정하였기 때문에 1000 - money로 간단하게 거스름 돈을 계산하고, 가장 큰 동전 값 부터 나누어 동전의 개수를 계산하였다. import java.io.*; public class Baekjoon5585 { public static void main(String[] args) throws IOExcepti..
-
[Baekjoon Online Judge] 1931번: 회의실배정문제 풀이/Baekjoon Online Judge 2020. 12. 25. 17:45
1931번: 회의실배정 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net public class Baekjoon1931 { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(bufferedReader.readLine());..
-
[Baekjoon Online Judge] 11047번: 동전 0문제 풀이/Baekjoon Online Judge 2020. 12. 25. 17:43
11047번: 동전 0 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 import java.io.*; public class Baekjoon11047 { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter buff..
-
[Baekjoon Online Judge] 2839번: 설탕 배달문제 풀이/Baekjoon Online Judge 2020. 12. 23. 18:01
2839번: 설탕 배달 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net import java.io.*; public class Baekjoon2839 { public static int count(int weight) { int length = weight / 3; for (int i = 0; i
-
Greedy Algorithm문제 풀이/알고리즘, 자료구조 2020. 12. 23. 16:26
Greedy Algorithm greedy 탐욕스러운, 말 그대로 현재 시점에서 가장 이익되는 것을 쫓아간다. 필자가 학교에서 경로를 선택하는 매 순간마다 가장 짧은 경로를 찾아서 집을 간다고 가정하자. 버스와 지하철 노선 혹은 보행도로 등 무수한 경로에서 가장 짧은 경로를 찾아서 집으로 다가갈 것이다. 집으로 가는 길을 너무 나도 많고, 현재 가고 있는 길이 집까지 가는 가장 빠른 경로라는 것을 보장할 수 없다. 그리디 알고리즘은 결과적으로 가장 빠른 경로를 찾는 것이 아닌, 현재 시점에서 가장 빠른 경로를 찾는 방법이기 때문이다. 눈 앞의 이익만 우선 추구하는 알고리즘을 총칭한다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 그렇기 때문에 최적해를 보장하지 못한다. 그리디 알고리즘의 목표는 최적해..