팀원: 현빈, 현지, 유진
문제출처: https://www.acmicpc.net/problem/2720
언어: java
Level: 브론즈3
알고리즘 유형: 그리디 알고리즘
*** 목차 ***
<문제>
<선행지식>
탐욕 알고리즘 또는 그리디 알고리즘(greedy algorithm)은 최적의 해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.
탐욕 알고리즘이 잘 작동하는 문제에 두가지 조건이 있는데 우선 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.
이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.
⭐️즉 의도에 맞는 최적의 해를 구하는 것이 그디리 알고리즘입니다
💡그리디 알고리즘의 수행단계
- 문제의 최적해 구조를 결정합니다.
- 문제의 구조에 맞게 선택 절차를 정의합니다 : 선택 절차(Selection Procedure)
선택 절차: “현재 상태”에서 “최적의 선택”을 한다. - 선택 절차에 따라 선택을 수행합니다.
- 선택된 해가 문제의 조건을 만족하는지 검사합니다 : 적절성 검사(Feasibility Check)
적절성 검사: “선택한 해”가 “문제의 조건”을 만족하는가? - 조건을 만족하지 않으면 해당 해를 제외합니다.
- 모든 선택이 완료되면 해답을 검사합니다 : 해답 검사(Solution Check)
해답 검사: “최종 선택”이 “문제의 조건”을 만족시키는가? - 조건을 만족하지 않으면 해답으로 인정되지 않습니다.
예제
1. 최소 동전으로 거슬러 주기
coin_list에 있는 최소한의 동전 value값 거슬러 주기
2. 최대 곱 구하기
여럿이서 카드 게임을 하고 있는데, 각 플레이어는 3장의 카드를 들고 있다.
첫번째 플레이어의 경우는 1, 6, 5의 카드를 들고 있고, 두번째 플레이어의 경우 4, 2, 3의 카드를 들고 있다.
플레이어들끼리 카드를 한장씩 냈을 때, 낸 카드의 곱의 최대값을 구하라
3.익중이네 밴드부는 매주 수요일 오후 6시에 합주를 하는데요. 멤버들이 너무 상습적으로 늦어서,
1분에 1달러씩 내야 하는 벌금 제도를 도입했습니다.
그런데 마침 익중이와 친구 넷이 놀다가 또 지각할 위기입니다. 아직 악보도 출력해 놓지 않은 상황이죠.
어차피 같이 놀다 늦은 것이니 벌금을 다섯 명이서 똑같이 나눠 내기로 하고, 벌금을 가능한 적게 내는 방법을 고민해 보기로 합니다.
다섯 사람이 각각 출력해야 하는 페이지 수는 3장, 1장, 4장, 3장, 2장입니다.
프린터는 한 대밖에 없고, 1장을 출력하기 위해서는 1분이 걸립니다.
현재 순서대로 출력한다면,
첫 번째 사람: 3분 지각
두 번째 사람: (3) + 1분 지각
세 번째 사람: (3 + 1) + 4분 지각
네 번째 사람: (3 + 1 + 4) + 3분 지각
다섯 번째 사람: (3 + 1 + 4 + 3 )+ 2분 지각 총 39달러
지각 비용이 적은 순서로 지각 벌금을 낸다면 가장 적은 지각 비용을 낼 것
4.이번 학기 코드잇 대학교의 수업 리스트가 나왔습니다.
리스트에 담겨있는 튜플들은 각각 하나의 수업을 나타냅니다.
각 튜플의 0번째 항목은 해당 수업의 시작 교시, 그리고 1 번 항목은 해당 수업이 끝나는 교시입니다.
예를 들어서 0번 인덱스에 있는 튜플값은 (4, 7)이니까, 해당 수업은 4교시에 시작해서 7교시에 끝나는 거죠.
(2, 5)를 듣는다고 가정합시다. (4, 7) 수업은 (2, 5)가 끝나기 전에 시작하기 때문에,
두 수업은 같이 들을 수 없습니다. 반면, 수업 (1, 3)과 (4, 7)은 시간이 겹치지 않기 때문에 동시에 들을 수 있습니다.
(단, (2, 5), (5, 7)과 같이 5교시에 끝나는 수업과 5교시에 시작하는 수업은 서로 같이 듣지 못한다고 가정합니다)
열정이 불타오르는 신입생 지웅이는 최대한 많은 수업을 들을 수 있는 수업 조합을 찾아주는 함수 작성하려고 합니다.
Goal
🌟 key point
- 거스름돈의 액수가 주어지면 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개수 구하기.
- 입력받는 동전의 단위는 센트(cent)로 계산 → (원래 동전단위*100)
- 쿼터: 25¢, 다임: 10¢, 니켈: 5¢, 페니: 1¢
- 손님이 받는 동전의 개수는 최소 갯수로만 주기.
- ex) 거스름돈 124¢ → “4쿼터(25¢), 2다임(10¢), 0니켈(5¢), 4페니(1¢)” 최소동전 갯수
- 위 그림과 같이 거스름돈을 각각 쿼터(25¢), 다임(10¢), 니켈(5¢), 페니(1¢)로 나눈 몫이 출력되는 최소 동전의 갯수
- 거스름돈: ‘C’, 동전 단위 값: ‘coin’일 경우
- C / coin(쿼터의 값 25) = 거슬러 준 쿼터의 최소 동전 갯수,
남은 거스름돈 잔액(임의의 변수 q 지정) - q / coin(다임의 값 10) = 거슬러 준 다임의 최소 동전 갯수,
남은 거스름돈 잔액(임의의 변수 d 지정) - d / coin(니켈의 값 5) = 거슬러 준 니켈의 최소 동전 갯수,
남은 거스름돈 잔액(임의의 변수 n 지정) - n / coin(페니의 값 1) = 거슬러 준 페니의 최소 동전 갯수,
남은 거스름돈 잔액(임의의 변수 p 지정) == 0
- C / coin(쿼터의 값 25) = 거슬러 준 쿼터의 최소 동전 갯수,
- 결과값으로 최소 동전을 거슬러 줌으로써 가장 효율적인 경우의 값을 도출한다.
Main
“Code review”
<현지>
스캐너 ,for문 , List를 사용한 코드
배열을 선언, 중첩된 for문 사용 코드 작성
package study;
import java.util.*;
public class Main {
public static <t> void main(String[] args) {
Scanner sc = new Scanner(System.in);스캐너에서 입력받기
//System.out.println("테스트 케이스 갯수");
int t = sc.nextInt();//스캐너에서 입력받은 값을 정수 선언
List<Integer> list = new ArrayList<Integer>(t);
//테스트 갯수에 따라서 배열의 길이가 변화하므로 List로 작성,길이는 t
while(t>0){ //테스트갯수는 양수
Scanner dl = new Scanner(System.in);
//System.out.println(t+"개의 예시 입력하기");
for(int i=0;i<t;i++) {
list.add(i,dl.nextInt()); //입력받은 값을 list에 추가
}
break;
}
int coin[] = {25,10,5,1}; //배열 선언 센트 동전들
int out[] = new int[4];//출력값 배열 선언
for(int j=0;j<t;j++) {
int in = list.get(j);//리스트의 첫번째 값,첫번째 거스름돈
for(int i=0;i<coin.length;i++) {//나누기4번이 반복된다.
out[i] = in/coin[i];//25센트로 나눈 몫이 출력의 첫번째 값에 저장된다.
in = in%coin[i];//25센트로 나눈 나머지가 다시 입력으로 들어가 10센트로 나누어진다.
}
System.out.println(Arrays.toString(out)); //배열의 출력
}
}
}
package study;
import java.util.*;
public class study_2720 {
public static void main(String[] args) {
int coin[] = {25,10,5,1};
int out[] = new int[4];
while(true) {
Scanner sc = new Scanner(System.in);
System.out.println("500이하의 금액을 입력하세요");
int in = sc.nextInt();
for(int i=0;i<coin.length;i++) {
out[i] = in/coin[i];
in = in%coin[i];
}
System.out.println(Arrays.toString(out));
}
}
}
<Test_Result>
<현빈>
import java.io.*;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine()); //테스트 케이스 수
int quarter = 25;
int dime = 10;
int nickel = 5;
int penny = 1;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < t; i++) {//테스트 케이스 갯수만큼 for문
int c = Integer.parseInt(br.readLine());
sb.append(c / quarter + " ");
c %= quarter;
sb.append(c / dime + " ");
c %= dime;
sb.append(c / nickel + " ");
c %= nickel;
sb.append(c / penny + "\\n");
}
System.out.print(sb);
}
}
import java.io.*;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine()); //테스트 케이스 수
int quarter = 25;
int dime = 10;
int nickel = 5;
int penny = 1;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < t; i++) {//테스트 케이스 갯수만큼 for문
while(true){
int c = Integer.parseInt(br.readLine());
if(!(c >= 1 && c <= 500)) { // 1<=C<=500 범위가 아니면 재입력
System.out.println("다시 입력해주세요");
}else{
sb.append(c / quarter + " ");
c %= quarter;
sb.append(c / dime + " ");
c %= dime;
sb.append(c / nickel + " ");
c %= nickel;
sb.append(c / penny + "\\n");
break;
}
}
}
System.out.print(sb);
}
}
- BufferedReader를 사용해 입출력을 받아와 int형태로 변수를 입력 받았으며
- For반복문
→ 테스트 케이스 수 만큼 for문을 반복해서 지정한 거스름돈을 최적의 수로 거슬러 준다. - Stringbuilder
→최적의 수를 stringbuilder안에 저장해주고 마지막에 전부 출력을 해준다
<Test_Result>
<유진>
// 백준 2720번 문제 세탁소 사장 동혁
// Scanner 사용
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 테스트 케이스의 개수
// 124, 25, 194 3개의 테스트 케이스
// 거슬러 줄 동전 종류의 금액 단위
int[] coins = {25, 10, 5, 1};
// 테스트 케이스 수만큼 반복, 각 케이스별 최소 갯수의 거스름돈을 출력
for(int i=0; i < T; i++) {
while(true) {
int C = sc.nextInt(); // 거스름돈 입력
if(!(C >= 1 && C <= 500)) { // 1<=C<=500 범위가 아니면 재입력
System.out.println("다시 입력해주세요");
}else { // 1<=C<=500 범위 안에 들어가면 테스트 실행
int q = C / coins[0]; // 쿼터의 갯수 저장
C %= coins[0]; // 쿼터 동전으로 거슬러주고 남은 금액
int d = C / coins[1]; // 다임의 갯수 저장
C %= coins[1]; // 다임 동전으로 거슬러주고 남은 금액
int n = C / coins[2]; // 니켈의 갯수 저장
C %= coins[2]; // 니켈 동전으로 거슬러주고 남은 금액
int p = C / coins[3]; // 페니의 갯수 저장
// 거슬러 준 동전의 최소 갯수 결과값
System.out.printf("%d %d %d %d ",q,d,n,p);
break;
}
}
}
sc.close();
}
}
<Test_Result1>
// 백준 2720번 문제 세탁소 사장 동혁
// 성능 좋은 IO패키지 BufferedReader 사용
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine()); // String을 int형으로 변환. 테스트 케이스의 개수
// 124, 25, 194 3개의 테스트 케이스
// 거슬러 줄 동전 종류의 금액 단위
int[] coins = {25, 10, 5, 1};
// 테스트 케이스 수만큼 반복, 각 케이스별 최소 갯수의 거스름돈을 출력
for(int i=0; i < T; i++) {
while(true) {
int C = Integer.parseInt(br.readLine()); // 거스름돈 입력
if(!(C >= 1 && C <= 500)) { // 1<=C<=500 범위가 아니면 재입력
System.out.println("다시 입력해주세요");
}else { // 1<=C<=500 범위 안에 들어가면 테스트 실행
int q = C / coins[0]; // 쿼터의 갯수 저장
C %= coins[0]; // 쿼터 동전으로 거슬러주고 남은 금액
int d = C / coins[1]; // 다임의 갯수 저장
C %= coins[1]; // 다임 동전으로 거슬러주고 남은 금액
int n = C / coins[2]; // 니켈의 갯수 저장
C %= coins[2]; // 니켈 동전으로 거슬러주고 남은 금액
int p = C / coins[3]; // 페니의 갯수 저장
// 거슬러 준 동전의 최소 갯수 결과값
System.out.printf("%d %d %d %d ",q,d,n,p);
break;
}
}
}
}
}
<Test_Result2>
➡️
유진 코드 리뷰
: 입출력 메서드를 1) Scanner 2) BufferedReader로 2가지를 이용해 테스트함.
- 쿼터, 다임, 니켈, 페니 큰 단위의 동전 순서대로 배열에 저장.
- 테스트 케이스 T만큼 입력값을 받을 수 있도록 for문에서 T만큼의 범위를 반복하도록 지정.
- 쿼터 → 다임 → 니켈 → 페니 순으로 최대한의 동전을 사용해 거스름돈을 지불하도록 하여 최적의 몫(최소 동전의 갯수) 도출
➡️
유진 코드 결과 분석
: 입출력 메서드를 1) Scanner 2) BufferedReader로 2가지를 이용해 테스트함.
- Scanner를 사용한 경우는 BufferedReader에 비해 2배 정도 메모리 소모량 및 수행시간이 들어간 걸 확인할 수 있음.
- while 반복문과 if 조건문을 사용해 입력 가능한 1<=C<=500 범위값을 주었는데 메모리 소모는 물론 수행시간도 대폭 하향하는 결과가 출력됨.
- 현빈님의 코드과 수행시간 면에서 차이가 났는데 for 반복문 안에서 새로운 변수가 반복적으로 선언되고, 출력 결과 또한 반복문 안에서 여러번 출력되는 코드이기 때문에 수행시간이 더 소요된 걸로 판단됨.
Reference
- IO 패키지의 BufferedReader 참고
[JAVA] BufferedReader 와 Bufferedwriter 사용법
[JAVA] BufferedReader 와 Bufferedwriter 사용법
BufferedReader :Scanner와 유사. Bufferedwriter :System.out.println();과 유사 둘은 모두 기존에 ...
blog.naver.com
- 그리디 알고리즘의 예시
알고리즘: 그리디 알고리즘(Greedy Algorithm) 공부하고 예제 한번 풀어보자!
알고리즘: 그리디 알고리즘(Greedy Algorithm) 공부하고 예제 한번 풀어보자!
그리디 알고리즘이란(Greedy Algorithm)이란? 뜻 그대로 탐욕스런 알고리즘이라고 생각하면 쉽다. 미래를 내다 보지 않고 당장 눈 앞에 보이는 최적의 선택을 하는 방식이다. 그리디 알고리즘은 간단
seungjuitmemo.tistory.com
- 그리디 알고리즘 수행단계 참고
[Java/알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기
[Java/알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기
해당 글에서는 알고리즘의 설계 방법 중 탐욕법/그리디 알고리즘에 대해서 이해를 돕기 위해 작성한 글입니다. 1) 그리디 알고리즘(탐욕법, Greedy Algorithm) 💡 그리디 알고리즘(탐욕법, Greedy Algorit
adjh54.tistory.com
'Team 발표 과제' 카테고리의 다른 글
| 백준 1388. 바닥 장식 (0) | 2024.10.10 |
|---|---|
| 백준 2003번 "수들의 합2" (0) | 2024.10.10 |
| 백준 (자바) 17608번 막대기 (3) | 2024.10.03 |
| 백준 (자바)문제 7785번 "회사에 있는 사람" (0) | 2024.10.03 |
| 1417. 국회의원 선거 (0) | 2024.10.02 |
