I. 그리디알고리즘 정의
그리디 알고리즘은 '현재 상태에서 볼 수있는 선택지' 중 '최선의 선택'을 하는 알고리즘이다 (전체 선택지 중
항상 최적해를 구하지 못하는것이 한계이다. 그래서 선택시 늘 유의해야한다
인공신경망 구성시 local minimum과 global minimum 차이에서 최적해 문제를 이해하기 수월 할 수있다
II. 그리디 이론
1. 들어가며
3단계를 반복하면서 해결한다
2. 수행과정
(1) 해선택
현재 상태에서 가장 최선이라고 생각하는 해를 선택한다 (부분의 best)
(2) 적절성 검사
현재 선택한 해가 전체문제 '제약조건'에서 벗어나지 않는지 검사
(3) 해 검사
현재 선택한 해 집합이 '전체 문제 해결'할 수 있는지 검사한다.
전체문제를 해결할 수 없다면 처음으로 돌아가 반복한다.
II. 그리디(bianry serach) - 문제 1
[ 백준 11047 ]
1. 문제설명
2. 문제풀이
(1) 문제분석
- 전형적인 그리디 문제이다
- 그리디 알고리즘의 한계인 반례가 있을 수 있다. 이를 막기위해서 배수조건을 두었다
- 그때 당시의 최선인 "진의" 로서는 금액이 큰 동전부터 먼저 넣으면된다
(2) 손으로 풀기
- 블로그에서 생략
(3) 슈도코드 코드 작성
- 블로그에서 생략
(4) 코드 구현
1)
package datastructure6;
import java.io.*;
import java.util.*;
public class P11047 {
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 + 1];
//동전의 가격
for(int i = 1 ; i < N + 1 ; i++){
st = new StringTokenizer(br.readLine());
A[i] = Integer.parseInt(st.nextToken());
}
//오름차순 정렬 ( 필요없을수도?)
//왜냐하면 큰금액부터 나누기위한것으로 오름차순 정렬로 한다.
Arrays.sort(A);
int count = 0;
// 등호표시 때문문에 loop에 빠짐
while(K > 0){
// 같은 동전여러개라고 생각해서 조건에 따라 증감식을 달리 해야한다고 생각해서 while문을 씀
if(K > A[N]){ // 금액이 동전보다 클 때
//K 위치에 따라서 0으로 나와버림
int coin = K / A[N] ;
count += coin; // 동전갯수
K %= A[N]; //동전 뺀 후 금액
N -- ;
}
else { //금액이 동전보다 작을 때
N --; // 동전 금액 줄이기
}
}
System.out.println(count);
}
}
//10 4200
//1
//5
//10
//50
//100
//500
//1000
//5000
//10000
//50000
2)
무언가 백준코딩에서 에러가 발생해서 for문형식으로 했다
무언가 배열사이즈 때문에 추가로 입력을 받아야하는것이 오류가 발생한 원인으로 추정된다.
그래서 다시 조정해서 아래와같이 만들었다.
package datastructure6;
import java.io.*;
import java.util.*;
public class P11047 {
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++){
st = new StringTokenizer(br.readLine());
A[i] = Integer.parseInt(st.nextToken());
}
//오름차순 정렬 ( 필요없을수도?)
Arrays.sort(A);
int count = 0;
// 등호표시 때문문에 loop에 빠짐
// while(K > 0){
// // 같은 동전여러개라고 생각해서 조건에 따라 증감식을 달리 해야한다고 생각해서 while문을 씀
//
// if(K > A[N]){ // 금액이 동전보다 클 때
//
// //K 위치에 따라서 0으로 나와버림
// int coin = K / A[N] ;
// count += coin; // 동전갯수
// K %= A[N]; //동전 뺀 후 금액
// N -- ;
// }
// else { //금액이 동전보다 작을 때
// N --; // 동전 금액 줄이기
// }
// }
for(int i = N - 1 ; i >= 0 ; i --){
if(A[i] <= K){
count += (K / A[i]);
K = K % A[i] ;
}
}
System.out.print(count);
}
}
//10 4200
//1
//5
//10
//50
//100
//500
//1000
//5000
//10000
//50000
4. 보충 및 회고
(1) 보충
(1) 그리디는 그 당시에 최선이기 때문에 가장 큰값부터 넣어주자!
(2) 회고 : 문제풀이과정에서 어떻게 접근하려고했는지 (접근방법) + 어려움이 있었는데 해결했다.
1)
역으로 한다는 생각으로 바로 while을 했는데 for문도 가능하다는것을 생각해내게 되었다.
II. 그리디(bianry serach) - 문제 1
[ 백준 1715 ]
1. 문제설명
2. 문제풀이
(1) 문제분석
- 카드가 작은순서대로 먼저 합쳐서 줄이는 방법!
- 데이터 삽입 삭제 정렬 자주 일어남 -> 우선순위 큐 이용!
(2) 손으로 풀기
꺼내고 -> 연산하고 -> 자동정렬 -> 삽입
-> 꺼내고 -> 연산하고 -> 자동정렬 -> 삽입
-> 꺼내고 -> 연산하고 -> 자동정렬 -> 삽입
-> 꺼내고 -> 연산하고 -> 자동정렬 -> 삽입
-> 1이 되면 종료
(3) 슈도코드 코드 작성
- 블로그에서 생략
(4) 코드 구현
1)
package datastructure6;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class P1715 {
public static void main(String[] args) throws IOException {
//당시에 최선!
//카드묶음 수 입력을 받는다
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int N = Integer.parseInt(st.nextToken());
// //묶음 수 만큼 배열을 만들고, 배열 수만큼 각각에 크기를 입력받는다
// ArrayList <Integer> list = new ArrayList<Integer>();
// //반복문으로 배열의 끝 까지 반복을 한다
// for(int i = 1 ; i < N + 1 ; i++){
// st = new StringTokenizer(bf.readLine());
// int M = Integer.parseInt(st.nextToken());
// list.add(M);
// }
// System.out.println(list);
//
// int total = list.get(0) + list.get(1);
// int tmp = 0;
//
// //0번째 배열에서 1~끝까지 배열 중의 합 중 최소의 합이 있는 인덱스를 구한다
// for(int i = 1 ; i < list.size() ; i ++){
// tmp = total;
// tmp += list.get(i);
//
// //최소합이 있는 총합을 넣어준다
//
// //총합이 임시값보다 크면
// if(total > tmp){
// //임시 값이 최솟값으로서 total 에 넣어준다.
// total = tmp;
// //합한 숫자가 있는 인덱스 배열에서 제거한다
// list.remove(i);
// System.out.println(list);
//
// //총합이 임시값보다 작으면
// } else {
// //현재 총합이 최소이다.
// }
// }
// System.out.println(total);
// //반복
//우선순위 큐 선언
PriorityQueue<Integer> pq = new PriorityQueue<>();
//반복문으로 값 대입
for(int i = 0 ; i < N ; i++){
st = new StringTokenizer(bf.readLine());
int M = Integer.parseInt(st.nextToken());
pq.add(M);
}
int x = 0;
int y = 0;
int sum = 0;
//반복문으로 큐 사이즈가 1이면 반복종료
while (pq.size() != 1){
//큐에서 꺼내면서 x,y에 리턴
x = pq.remove();
y = pq.remove();
//우선순위가 높은 즉 값이 낮은것을 더하고, sum에 대입
sum += (x+y);
//큐에 누적해서 추가
pq.add((x+y));
}
System.out.println(sum);
}
}4. 보충 및 회고
(1) 보충
1) 우선순위 큐
Heap으로 구현하는데, FIFO방식 아니라 우선순위로 함
최대힙 최소힙으로 대별됨
(2) 회고 : 문제풀이과정에서 어떻게 접근하려고했는지 (접근방법) + 어려움이 있었는데 해결했다.
1)
지난번에 arrary list를 생각했는데 실시간으로 정렬을 어떻게 해야할지 고민했었다.
그런데, 우선순위 큐를 이용하면 해결된다는 점이 흥미롭다.
'배움 __IL > 자료구조&알고리즘' 카테고리의 다른 글
| 알고리즘 3줄 정리 [합병정렬, 퀵정렬] (0) | 2023.12.26 |
|---|---|
| 동적계획법 : 동적계획법 이론과 문제 (0) | 2023.04.02 |
| 탐색 : 이진탐색 이론과 문제 (0) | 2023.03.26 |
| 탐색 : BFS 이론과 문제 (0) | 2023.03.25 |
| 탐색 : DFS 이론과 문제 (0) | 2023.03.25 |