그리디 알고리즘의 핵심 이론
수행 과정
1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사.
전체 문제를 해결하지 못하면 1로 돌아가 과정 반복
백준 Greedy algorithm 문제
백준 11047
https://www.acmicpc.net/problem/11047
이 문제의 핵심 아이디어는 K를 만들 때 동전을 최대한 적게 사용해야하므로 값어치가 큰 동전부터 사용해줘야 함. > 제약조건으로 걸어주자.
package baekjoon;
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 A[] = new int [N];
for(int i = 0; i < N; i++) {
A[i] = Integer.parseInt(br.readLine());
}
int count = 0; //동전을 카운팅하는 변수.
//큰 동전부터 사용해야 필요한 동전 갯수를 줄일 수 있다.
for(int i = N-1; i >= 0; i--) {
if(A[i] <= K) {
count += (K / A[i]);
K = K % A[i];
}
}
System.out.println(count);
}
}
백준 1715
https://www.acmicpc.net/problem/1715
package baekjoon;
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());
PriorityQueue <Integer> pq = new PriorityQueue<>();
for(int i = 0; i < N; i++) {
pq.add(Integer.parseInt(br.readLine()));
}
int count = 0; //비교횟수
while(pq.size() > 1) {
int num1 = pq.poll();
int num2 = pq.poll();
count += num1 + num2;
pq.add(num1 + num2);
}
System.out.println(count);
}
}
백준 1744
https://www.acmicpc.net/problem/1744
양수, 음수 나눠서 pq에 저장
sum이 최대가 되려면 양수인 수들은 큰 수끼리 묶어야함> queue 내림차순 해주기
1은 왜 따로 뺐는가? > 예를들어, 1+2+(3*4) > (1*2)+(3*4) 이기 때문 >어떤 양수에 1을 곱하는 것보다 1을 더하는 것이 항상 더 큰 값을 가진다.
zero 처리를 고민했는데, 0은 어짜피 양수에 더하면 값의 변화가 없으니 음수 쪽에서 처리해주어야 함.
즉, 음수에 0을 곱해서 값을 최대한 크게 만드는 쪽으로.
만약 음수가 홀수개 있다면 두개씩 묶어서 양수 만들어주고 남은 하나의 음수는 sum에 더해주면 됨.
ex. -1 , -2, -4가 있다고 가정, (-1)+ (-2*-4)
package baekjoon;
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 oneCount = 0;
int zeroCount = 0;
PriorityQueue <Integer> pqPos = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue <Integer> pqNeg = new PriorityQueue<>();
for(int i = 0; i < N; i++) {
int curr = Integer.parseInt(br.readLine());
if(curr > 1) {
pqPos.add(curr);
}
else if(curr == 1) {
oneCount++;
}
else if (curr == 0) {
zeroCount++;
}
else {
pqNeg.add(curr);
}
}
int sum = 0;
while(pqPos.size() > 1) {
int dt1 = pqPos.poll();
int dt2 = pqPos.poll();
sum += (dt1 * dt2);
// pqPos.add(sum);
}
if(!pqPos.isEmpty()) sum += pqPos.poll();
while(pqNeg.size() > 1) {
int dt1 = pqNeg.poll();
int dt2 = pqNeg.poll();
sum += (dt1 * dt2);
// pqNeg.add(sum);
}
if(!pqNeg.isEmpty() && zeroCount == 0) sum += pqNeg.poll();
sum += oneCount;
System.out.println(sum);
}
}
백준 1541
https://www.acmicpc.net/problem/1541
체감상 뭔가.. 골드 문제보다 어려웠음
이 문제를 풀기 위한 핵심 키는 식의 연산 결과를 최소로 만들기 위해서는 가장 큰 수를 빼줘야한다는 것이다.
그렇다면 이 로직을 어떻게 구현할까? 다행이게도 주어진 연산자는 +와 - 단 두개이므로 -를 기준으로 식을 split 해준다. 이후 더하기를 해줘야하는 값들을 먼저 괄호처리하여 다 더해주고나서 마이너스 처리를 해주면 됨.
순조로운 듯 했으나......
sumFunc에서 에러 발생 Exception in thread "main" java.util.regex.PatternSyntaxException: Dangling meta character '+' near index 0
해결 방안> String tmp[] = s.split("+")를 String tmp[] = s.split("[+]")로 수정.
package baekjoon;
import java.io.*;
import java.util.*;
public class Main2 {
static int sumFunc(String s) {
int sum = 0;
String tmp[] = s.split("[+]");
for(int i = 0; i < tmp.length; i++) {
sum += Integer.parseInt(tmp[i]);
}
return sum;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int ans = 0;
//가장 작은 최솟값 > 가장 큰 값 빼
String[] strPos = str.split("[-]");
for(int i = 0; i < strPos.length; i++) {
int tmp = sumFunc(strPos[i]);
if(i == 0) ans += tmp;
else ans -= tmp;
}
System.out.println(ans);
}
}
'Algorithms > study log' 카테고리의 다른 글
[java] 다익스트라 알고리즘 (0) | 2024.02.01 |
---|---|
[백준 나무자르기] 이분탐색시 시작 혹은 끝 지점 설정하는 방법 (0) | 2024.01.17 |
[java] 이분탐색 (2) | 2024.01.12 |
[Algorithm] DFS, BFS (1) | 2023.12.22 |
[JAVA] 시뮬레이션,구현 (0) | 2023.12.01 |