알고리즘/그리디알고리즘(Greedy Algorithm)
-
[백준 10610] - [그리디알고리즘] - 30 (JAVA)알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 12. 27. 16:24
문제 링크 : https://www.acmicpc.net/problem/10610 이 문제는 그리디 알고리즘 문제 중에서 어려운 편에 속하는 문제이다. 문제 자체에 오해 할 수 있는 요소가 존재해서 다들 잘못 이해 하고 접근하다가 계속 틀리다는 결과를 받는거 같다. N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 입력값 은 최대 10^5 의 숫자라고 하는게 100000 까지 입력을 받는게 아니라 자리수가 10^5개라는 말이었다. 대부분의 사람들도 100000 까지만 입력 받는걸로 이해하고 문제를 접근해서 고생을 한 거 같다. 정수형 타입인 int 나 실수형 타입인 long 이나 10^5개의 자리수를 입력 받을 수 있는 자료형은 없다. 그럼 어떻게 문제를 풀어야 할..
-
[백준 5585] - [그리디알고리즘] - 거스름돈 (JAVA)알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 12. 27. 14:46
문제 링크 : https://www.acmicpc.net/problem/5585 이문제는 어렵지 않은 그리디 알고리즘 문제이다. 그리디 알고리즘 이란 탐욕적 알고리즘으로 모든 경우의 수를 다 구하면 된다. 거스름돈을 구하는 경우는 아주 쉬운 예제 인데 접근 법은 남은 잔액에서 금액이 큰 동전부터 지급 가능한 개수를 구해나가면 된다. 예제로 380원이 물건 값이 나왔고 1000엔을 받았을때 620원을 거스름돈으로 지불해야 한다. 지불 할 수 있는 동전은 500, 100, 50, 10, 5, 1 엔 총 6가지의 동전이 존재한다. 최소의 개수로 거스름돈을 지불 하고자 한다면 금액이 큰 동전 위주로 지불해주면 되기 때문에 금액이 큰 500엔 부터 줄 수 있는 경우의 수를 구한다. 1) 500엔 으로 지불 가능한..
-
[백준-4307]-[그리디알고리즘]-개미알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 19:08
문제링크 : https://www.acmicpc.net/problem/4307 이문제는 그림으로 보면서 풀면 이해가 제일 쉬울거 같다. 길이 10의 막대기가 있고 개미 3마리가 있다.개미들의 위치는 2, 6, 7에 있다. 개미1 개미2 개미3 1(지나면 끝) 2 3 4 5 6 7 8 9 10 (닿으면 끝) 여기서 무시해야될 조건이 있다. 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다. 위의 조건은 무시하고 각 개미가 떨어지는 시간의 최소와 최대를 구해보면 최소 최대 개미12 8 개미24 6 개미33 7 각 개미의 최소 시간중 제일 큰 값은 4, 최대 시간의 제일 큰 값은 8 주어진 예제의 원하는 값과 같다.각 개미들이 만나는 상황은 신경 쓸 이유가 없다는 뜻이다. 즉 이문제를 푸는 방법은..
-
[백준-2217]-[그리디알고리즘]-로프알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 18:54
문제링크 : https://www.acmicpc.net/problem/2217 이문제는 병렬로 연결된 로프가 버틸 수 있는 최대 중량이 얼마나 되는지 물어보는 문제이다. 로프가 한개일 때는 로프가 버틸 수 있는 한계가 최대 중량이다. 그럼 로프가 두개일 때는? 로프의 최대중량이 작은 로프의 힘 * 2 가 로프가 두개일때 최대 중량이다. 왜그럴까?? 문제에 다음 조건이 존재하기 때문이다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 중량이 20 일때 로프 두개를 사용하면 한 로프당 걸리는 중량은 10 이다. 최대중량이 10, 12 의 로프 두개가 있을때 최대 중량이 12인 로프가 아무리 10보다 더 들 수 있어도 그 이상의 무게를..
-
[백준-11399]-[그리디알고리즘]-ATM알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 18:36
문제 링크 : https://www.acmicpc.net/problem/11399 이문제는 아주 쉽게 계산했다. 최선과 최악의 경우의 수만 설명하면 어떻게 풀지 감이 올것이다.5 3 1 4 3 2위와 같이 입력이 되고 각 사람별 인출하는 시간이 3, 1, 4, 3, 2 라고 한다. 1번 사람은 3분 2번 사람은 1분 3번 사람은 4분 4번 사람은 3분 5번 사람은 2분 i 번 사람이 인출하는데 걸리는 시간은 i - 1번 사람이 걸린 시간에 i 사람이 인출하는데 소요되는 시간이다. 아래에 최악과 최선의 순서를 보면 어떻게 풀어야 할지 감이 온다. 최악3번, 1번, 4번, 5번, 2번 순으로 인출을 한다.3번 사람은 4분1번 사람은 4 + 3 = 7분 4번 사람은 7 + 3 = 10분5번 사람은 10 + 2..
-
[백준-1931]-[그리디알고리즘]-회의실배정알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 17:09
문제링크 : https://www.acmicpc.net/problem/1931 이문제를 풀때 가장 햇갈리는 부분은 시작시간과 종료시간의 기준이라고 생각한다. 시작시간으로만 배정 하게 되면 아래와 같은 제약 사항이 발생한다. 1 2 3 4 5 6 7 8 9 시작시간을 기준으로 시작시간이 2인 회의를 배정 하게되면 하나의 회의만 가능하다. 또 회의시간이 짧은것으로 배정을 하게 되면 아래와 같은 제약 사항이 발생한다. 12 3 4 5 6 7 8 9 회의시간이 짧은것으로만 배정을 하게 되면 또다시 하나만 선택 되게 된다. 이렇게 반례가 나오게 되면 그리디 알고리즘을 풀 수가 없다. 이 문제를 푸는 방법은 종료시간을 오름차순으로 정렬하게 되면 쉽게 풀수가 있다. 11 1 4 3 5 0 6 5 7 3 8 5 9 6..
-
[백준-11047]-[그리디알고리즘]-동전 0알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 15:08
문제링크 : https://www.acmicpc.net/problem/11047 이문제는 그리디 알고리즘로 풀면 된다. 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 입력은 위에 처럼 들어오는데 위에는 동전의 수 N, N개의 동전들에서 i개의 최소 조합으로 만들어야 하는 금액 K 이다. 입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 위의 입력에서 마지막줄에 조건을 볼 수 있다.N개의 동전의 가치 Ai가 오름차순으로 주어진다는 것과 Ai는 Ai-1의 배수 것..