그리디 (Greedy)
그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다. 그리디 알고리즘은 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수하다. 하지만 항상 최적의 해를 보장하지 못한다는 단점도 있다. 그래서 코딩 테스트에서 그리디 알고리즘을 사용하기 전에는 항상 그리디 알고리즘을 적용할 때의 논리 유무를 충분히 살펴야 한다.
그리디 알고리즘의 핵심 이론
그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 그리디 알고리즘은 다음과 같은 3단계를 반복하면서 문제를 해결한다.
그리디 알고리즘 수행 과정
1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.
[백준 11047번] 동전 0
https://www.acmicpc.net/problem/11047
전형적인 그리디 알고리즘 문제이다. 이 문제는 그리디 알고리즘으로 풀 수 있도록 뒤의 동전 가격 Ai가 앞에 나오는 동전 가격 Ai-1의 배수가 된다는 조건을 부여했다. 즉, 동전을 최소로 사용하여 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.
- 가격이 큰 동전부터 내림차순으로 K보다 가격이 작거나 같은 동전이 나올 때까지 탐색한다.
- 탐색을 멈춘 동전의 가격으로 K를 나눠 몫은 동전 개수에 더하고, 나머지는 K값으로 갱신한다.
- 과정 1~2를 나머지가 0이 될 때까지 반복한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] coins = new int[N];
for (int i = 0; i < N; i++)
coins[i] = Integer.parseInt(br.readLine());
int answer = 0;
for (int i = N-1; i >= 0; i--) {
if(coins[i] <= K) { // 현재 동전의 가치가 K보다 작거나 같으면 구성에 추가
answer += (K / coins[i]);
K = K % coins[i]; // K를 현재 동전을 사용하고 남은 금액으로 갱신
}
}
System.out.println(answer);
}
}
[백준 1715번] 카드 정렬하기
https://www.acmicpc.net/problem/1715
잘 생각하면 먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 미치는 것을 알 수 있다. 따라서 카드 묶음의 카드의 개수가 작은 순서대로 먼저 합치는 것이 전체 비교 횟수를 줄일 수 있는 방법이다. 현재 데이터 중 가장 작은 카드의 개수를 가진 묶음 2개를 뽑아야 하고, 이 2개를 기준으로 합친 새로운 카드 묶음을 다시 데이터에 넣고 정렬해야 한다. 즉, 데이터의 삽입, 삭제, 정렬이 자주 일어난다는 뜻이다. 따라서 이 문제는 우선순위 큐를 이용해야 한다.
- 현재 카드의 개수가 가장 작은 묶음 2개를 선택해 합친다.
- 합친 카드 묶음을 다시 전체 카드 묶음 속에 넣는다.
- 과정 1~2를 카드 묶음이 1개만 남을 때까지 반복한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 카드 묶음의 수 저장
PriorityQueue<Integer> cards = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
cards.add(sc.nextInt());
}
int sum = 0;
while(cards.size() > 1) {
int a = cards.remove();
int b = cards.remove();
sum += a + b;
cards.add(a+b);
}
System.out.println(sum);
}
}
[백준 1744번] 수 묶기
https://www.acmicpc.net/problem/1744
N의 최대 범위가 10,000이므로 시간 복잡도와 관련된 제약은 적은 문제이다. 가능한 한 큰 수들끼리 묶어야 결괏값이 커진다는 것을 알 수 있는데, 주어진 수열이 1, 2, 3, 4라면 1*4+2*3보다 1*2+3*4의 결괏값이 더 크기 때문이다. 또한 음수끼리 곱하면 양수로 변하는 성질을 추가로 고려해 문제를 풀어보겠다.
1. 수의 집합을 1보다 큰 수, 1, 0, 음수 이렇게 4가지 유형으로 나눠 저장한다.
2. 1보다 큰 수의 집합을 정렬해 최댓값부터 차례대로 곱한 후에 더한다. 원소의 개수가 홀수일 때 마지막 남은 수는 그대로 더한다.
3. 음수의 집합을 정렬해 최솟값부터 차례대로 곱한 후에 더한다. 원소의 개수가 홀수일 때 수열에 0이 있다면 1개 남는 음수를 0과 곱해 0을 만들고, 수열에 0이 없다면 그대로 더한다.
4. 과정 2~3에서 구한 값을 더하고, 그 값에 숫자 1의 개수를 더한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
PriorityQueue<Integer> negative = new PriorityQueue<>();
PriorityQueue<Integer> positive = new PriorityQueue<>(Collections.reverseOrder());
// 양수는 내림차순 정렬
int one = 0;
int zero = 0;
for (int i = 0; i < N; i++) { // 4개의 그룹으로 분리해 저장
int data = sc.nextInt();
if(data > 1) positive.add(data);
else if(data == 1) one++;
else if(data == 0) zero++;
else negative.add(data);
}
int sum = 0;
// 양수 처리
while(positive.size() > 1) {
int first = positive.remove();
int second = positive.remove();
sum += first * second;
}
if(!positive.isEmpty()) sum += positive.remove();
// 음수 처리
while(negative.size() > 1) {
int first = negative.remove();
int second = negative.remove();
sum += first * second;
}
if(!negative.isEmpty() && zero == 0) sum += negative.remove();
// 1 처리
sum += one;
System.out.println(sum);
}
}
[백준 1931번] 회의실 배정
https://www.acmicpc.net/problem/1931
문제에서는 1개의 회의실에 회의가 겹치지 않게 최대한 많은 회의를 배정해야 한다. 이때는 그리디 알고리즘을 적용해야 하는데, 현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는 데 유리하다. 그렇기 때문에 종료 시간이 빠른 순서대로 정렬해 겹치지 않는 회의실을 적절하게 선택하면 이 문제를 해결할 수 있다. 단, 종료 시간이 같을 때는 시작 시간을 기준으로 다시 한번 정렬한다.
나는 반대로 시작 시간 기준으로 정렬한 후 시작 시간이 같을 때 종료 시간으로 다시 정렬한 기준으로 풀려고 했다. 그렇게 하나 하나 다 비교해가며 제일 많은 회의가 가능할 때를 출력하려 했는데 이렇게 되니 이중, 삼중 루프를 사용해야 됐다. 자세한 설명은 내가 제일 좋아하는 아래 블로그 참고.
https://st-lab.tistory.com/145
[백준] 1931번 : 회의실배정 - JAVA [자바]
www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 그리디 알고리즘의 대표적인 문제 중 하나다. 알고리즘 [접근 방법] 위와 같이 시간표를 최대
st-lab.tistory.com
이차원 배열을 이용해 두 번째 차원의 크기를 2로 정하고 첫 번째는 시작 시점, 두 번째는 종료 시점으로 정한 것 & 익명 객체를 사용해 배열 정렬을 재정의한 것을 잘 보고 기억하자. 나는 따로 클래스를 만들었는데 그럴 필요 없었다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
// time[i][0] : 시작 시간
// time[i][1] : 종료 시간
int[][] time = new int[N][2];
for (int i = 0; i < N; i++) {
time[i][0] = sc.nextInt();
time[i][1] = sc.nextInt();
}
Arrays.sort(time, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
// 종료 시간이 같을 경우 시작 시간 빠른순 정렬
if(o1[1] == o2[1]) return o1[0] - o2[0];
// 종료 시간 빠른 순으로 정렬
return o1[1] - o2[1];
}
});
int answer = 0;
int end = -1;
for (int i = 0; i < N; i++) {
if(end <= time[i][0]) { // 겹치지 않는 다음 회의가 나온 경우
end = time[i][1]; // 종료 시간 업데이트
answer++;
}
}
System.out.println(answer);
}
}
[백준 1541번] 잃어버린 괄호
https://www.acmicpc.net/problem/1541
그리디의 관점에서 생각하면 쉽게 풀 수 있는 문제이다. 가장 작은 최솟값을 만들기 위해서는 가능한 한 큰 수를 빼야 한다. 수식이 더하기와 빼기 연산만으로 이뤄져 있기 때문에 더하기에 해당하는 부분에 괄호를 쳐서 먼저 모두 계산한 후 빼기를 실행하면 문제가 해결된다.
1. 가장 먼저 더하기 연산을 실행한다.
2. 가장 앞에 있는 값에서 더하기 연산으로 나온 결괏값들을 모두 뺀다.
이 문제의 핵심은 split() 함수이다. 사용법을 자세히 봐두자.
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
String[] arr = s.split("-");
int answer = 0;
for (int i = 0, n = arr.length; i < n; i++) {
int temp = sum(arr[i]);
if(i == 0)
answer += temp; // 가장 앞에 있는 값만 더함
else
answer -= temp; // 뒷부분은 더한 값들을 뺌
}
System.out.println(answer);
}
static int sum(String str) { // 나뉜 그룹의 더하기 연산 수행 함수
int sum = 0;
String[] tmp = str.split("\\+");
for (String t : tmp) {
sum += Integer.parseInt(t);
}
return sum;
}
}
[참고자료]
- 알고리즘 코딩 테스트 자바편
'알고리즘 > Do it! 알고리즘 코딩 테스트' 카테고리의 다른 글
| 정수론 - 오일러 피 (0) | 2024.05.30 |
|---|---|
| 정수론 - 소수 구하기 (1) | 2024.05.29 |
| 이진 탐색 (Binary Search) (0) | 2024.05.25 |
| 너비 우선 탐색 (BFS) (0) | 2024.05.24 |
| 깊이 우선 탐색(DFS) (0) | 2024.05.23 |
