6장 그리디
Updated:
그리디 알고리즘
그리디(Greedy)알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.
그리디 알고리즘의 핵심 이론
그리디 알고리즘은 다음과 같은 3가지 단계를 반복하면서 문제를 해결한다.
- 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
- 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
- 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.
문제 032 동전 개수의 최솟값 구하기
시간 제한: 1초, 난이도: 실버4, 11047번
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(bf.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] coin = new int[N];
for (int i = 0; i < N; i++) {
coin[i] = Integer.parseInt(bf.readLine());
}
int result = 0;
for (int i = N - 1; i >= 0; i--) {
if (coin[i] <= K) {
result += (K / coin[i]);
K = K % coin[i];
}
}
bw.write(result + "\n");
bw.flush();
bw.close();
}
}
동전을 최소로 사용하기 위하여 coin 배열을 역순서 대로, 즉 큰 동전 부터 순서대로 동전을 사용하였다.
문제 033 카드 정렬하기
시간 제한: 2초, 난이도: 골드4, 1715번
풀이
import java.io.*;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(bf.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
int temp = Integer.parseInt(bf.readLine());
pq.offer(temp);
}
int data1 = 0;
int data2 = 0;
int sum = 0;
while (pq.size() > 1) {
data1 = pq.poll();
data2 = pq.poll();
sum += data1 + data2;
pq.offer(data1 + data2);
}
bw.write(sum + "\n");
bw.flush();
bw.close();
}
}
문제 034 수를 묶어서 최대값 만들기
시간 제한: 2초, 난이도: 골드4, 1744번
풀이
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(bf.readLine());
ArrayList<Integer> pos = new ArrayList<>();
ArrayList<Integer> neg = new ArrayList<>();
for (int i = 0; i < N; i++) {
int temp = Integer.parseInt(bf.readLine());
if (temp > 0) {
pos.add(temp);
} else {
neg.add(temp);
}
}
Collections.sort(pos, Collections.reverseOrder());
Collections.sort(neg);
// 양수 배열 계산
long posSum = 0;
boolean pS = false;
int pData = 0;
if (!pos.isEmpty()) {
int brInx = 0; // 1이 나오면 멈추기 위해
boolean br = false;
for (int i = 0; i < pos.size(); i++) {
if (pos.get(i) == 1) {
if (pS) {
posSum += pData;
}
brInx = i;
br = true;
break;
}
if (pS == false) {
pData = pos.get(i);
pS = true;
} else if (pS) {
posSum += pData * pos.get(i);
pS = false;
}
if (pS && i == pos.size() - 1) {
posSum += pData;
}
}
if (br) {
posSum += (pos.size() - brInx);
} // 1은 더해주어야 하므로 1이 존재하면 해당 연산
}
// 음수 배열 계산
long negSum = 0;
boolean nS = false;
int nData = 0;
if (!neg.isEmpty()) {
for (int i = 0; i < neg.size(); i++) {
if (nS == false) {
nData = neg.get(i);
nS = true;
} else if (nS) {
negSum += nData * neg.get(i);
nS = false;
}
if (nS && i == neg.size() - 1) {
negSum += nData;
}
}
}
long sum = posSum + negSum;
bw.write(sum + "\n");
bw.flush();
bw.close();
}
}
문제 035 회의실 배정
시간 제한: 2초, 난이도: 실버1, 1931번
풀이
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(bf.readLine());
int[][] useTime = new int[N][2];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(bf.readLine());
useTime[i][0] = Integer.parseInt(st.nextToken());
useTime[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(useTime, Comparator.comparingInt((int[] o) -> o[1]).thenComparingInt(o -> o[0]));
// 두번째 숫자 기준으로 오름차순, thenCompartingInt 이후의 내용은 두번째 숫자가 같으면 첫번째 숫자를 기준으로 정렬
int eTime = 0;
int count = 0;
for (int i = 0; i < N; i++) {
if (useTime[i][0] >= eTime) {
eTime = useTime[i][1];
count++;
}
}
System.out.println(count);
}
}
Java에서 2차원 배열을 정렬할 때 다음과 같이 할 수 있다.
Arrays.sort(useTime, Comparator.comparingInt((int[] o) -> o[0]));
// 첫번째 숫자를 기준으로 오름차순
Arrays.sort(useTime, Comparator.comparingInt((int[] o) -> o[0]).reversed());
// 첫번째 숫자를 기준으로 내림차순
Arrays.sort(useTime, Comparator.comparingInt((int[] o) -> o[1]))
// 두번째 숫자 기준으로 오름차순
Arrays.sort(useTime, Comparator.comparingInt((int[] o) -> o[1]).reversed())
// 두번째 숫자 기준으로 내림차순
만약 위 문제와 같이 하나의 원소가 같으면 다른 원소를 기준으로 정렬하고 싶으면 다음과 같이 하면된다.
Arrays.sort(useTime, Comparator.comparingInt((int[] o) -> o[1]).thenComparingInt(o -> o[0]));
문제 036 잃어버린 괄호
시간 제한: 2초, 난이도: 실버2, 1541번
풀이
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String st = bf.readLine();
String[] spSt = st.split("");
Queue<String> qu = new LinkedList<>();
String tempInteger = "";
for (int i = 0; i < spSt.length; i++) {
if (!spSt[i].equals("+") && !spSt[i].equals("-")) {
tempInteger += spSt[i];
} else if (spSt[i].equals("+") || spSt[i].equals("-")) {
qu.offer(tempInteger);
qu.offer(spSt[i]);
tempInteger = "";
}
if (i == spSt.length - 1) {
qu.offer(tempInteger);
}
}
int sum = 0;
int willAddedInt = 0;
sum += Integer.parseInt(qu.poll());
while (!qu.isEmpty()) {
String temp = qu.poll();
if (temp.equals("-")) {
while (!qu.peek().equals("-")) {
if (!qu.peek().equals("+")) {
willAddedInt += Integer.parseInt(qu.poll());
if (qu.isEmpty()) {
break;
}
} else {
qu.poll();
}
}
sum -= willAddedInt;
willAddedInt = 0;
} else if (temp.equals("+")) {
sum += Integer.parseInt(qu.poll());
}
}
bw.write(sum + "\n");
bw.flush();
bw.close();
}
}
댓글남기기