JAVA - 백준 [BAEK JOON]/그리디 알고리즘

www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 설명이 조금 복잡해보이나 원리만 이해하면 정말 쉬운 문제다. 알고리즘 [접근 방법] 문제 설명이 길어서 그렇지 내용 자체가 어려운 문제는 아니니 먼저 문제부터 이해하고 넘어가보자. 먼저 N개의 도시가 있고, 각 도시를 잇는 N-1개의 도로가 있다. 그리고 각 도시에는 주유소의 리터당 가격이 써져 있고, 각 도로에는 거리가 적혀져 있다. (1km당 1L 기름을 사용함) 문제에 있는 예시를 보면..

www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 이 번 문제 또한 그리 어렵지 않게 풀 수 있는 문제다. 문제만 잘 이해한다면 금방 이해할 수 있을 것이다. 알고리즘 [접근 방법] 위 문제에서 주어지는 예제는 다음과 같다. 55-50+40 그럼 여러분들은 아주 쉽게 괄호를 쳐서 '최솟값'을 다음과 같이 만들 수 있다. 55-(50+40) 그럼 정답은 -35가 된다. 다른 예시들을 보자. 30-70-20+40-10+100+30-35 가 있다고 생각해..

www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 이 또한 활동 선택 문제(Activity Selection Problem) 문제로 볼 수 있다. 조금만 이해하면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 앞서 포스팅 했던 문제인 회의실배정과 유사한 문제다. 문제를 잘 이해해야 하는 것이 '종료 시간'이 아니라 '대기 시간의 총합'을 구하는 문제라는 점. 즉, 어떻게 배치하던 총 걸리는 같더라도, 한 사람이 대기하는 시간은 달라질 수 있다. 상식적으로 대기시간을 줄이려면 앞 사..

www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 그리디 알고리즘의 대표적인 문제 중 하나다. 알고리즘 [접근 방법] 위와 같이 시간표를 최대한 많이 배정하거나 선택하는 문제를 '활동 선택 문제(Activity Selection problem)'라고 한다. 간단하게 설명하자면, 한 사람이 하나의 활동에 대해서만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제다. 위에서는 각 회의가 겹치지 않게 최대한 많은 회의를 배정하는 것으로 나와있다. 이러한 문제들의 특징은 '한 사람이 하나의 활동에 대해서만 작업할 수 있다'라는 점이다. 즉, 하나의 활동을 완..

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 문제 그리디 알고리즘의 첫 문제다. 사실 그리디 알고리즘이 무엇인지는 몰라도 쉽게 풀 수 있는 문제지만, 일단 그리디 알고리즘에 대해 알고가도록 하자. 알고리즘 [접근 방법] 1. 그리디 알고리즘 (Greedy Algorithm) 먼저 그리디 알고리즘이 뭔지 알아보자. 그리디 알고리즘이란, 말 그대로 greedy, 즉 탐욕 알고리즘이다. 왜 탐욕 ..