728x90
⬛ 06. 그리디
⬛ 06-1. 그리디 알고리즘
- 현재 상태에서 보는 선택지 중 최선의 선택지를 전체 선택지의 최선이라고 가정하는 알고리즘
- 그리디 알고리즘 적용 직전에 대상 데이터들을 (오름차순/내림차순) 정렬해두는 경우 多
현재 기준값을 기준으로 비교하고, 비교 한 뒤 현재의 기준값이 계속 갱신되는 행위 반복하는 것 !
⬛ 그리디 접근 방식
- 1) 객체화 시켜서 각 필드의 값들에 대하여 객체의 compareTo 사용하여 정렬시키고, 최초 0번 값을 기준값으로 하여 비교한 뒤, 기준값 갱신시키는 방식
ex) 신입사원
class Sawon implements Comparable<Sawon>{
//필드
...
//생성자
...
@Override
public int compareTo(Sawon o) {
return 조건
};- 2) 배열화 시켜서 Arrays.sort(배열, (a,b) → a[0]-b[0] ); 정렬시키고, 기준값을 갱신
int line[][] = new int[n][2];
for(int i=0; i<n; i++){
line[i][0] = 특정 기준;
line[i][1] = 특정 기준;
}
--> 여기서 i로는 각 인덱스 객체찍고, 0번에 특정값, 1번에 특정값 담아준다고 생각할 것.
//정렬 -오름차순
Arrays.sort(line, (a, b) -> (a[1] - b[1] ));
//정렬- 내림차순
Arrays.sort(line, (a, b) -> (b[1] - a[1] ));🟦 백준 1715번. 카드 정렬하기
- 적은 묶음 두 개씩 우선순위 큐에 담아가면서 합치고 pQ에 다시 담는 활동을 size 가 1 아닌 동안 반복하면 된다.
import java.util.PriorityQueue;
import java.util.Scanner;
/*1715번. 카드 정렬하기 */
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb = new Scanner(System.in);
int N = kb.nextInt();//묶음 개수
int[] arr= new int[N];
for(int i=0; i<N; i++) arr[i] = kb.nextInt();
//우선순위 큐 자동 오름차순 정렬
PriorityQueue<Integer> pQ = new PriorityQueue<>();
for(int i=0; i<N; i++) {
pQ.add(arr[i]);//자동 우선순위 정렬 될건데
}
int answer = 0;
while(pQ.size() != 1){
int a = pQ.poll();
int b = pQ.poll();
answer += (a+b);
pQ.add(a+b);//다시 담기
}
System.out.println(answer);
}
}
🟦 백준 1931번. 회의실
- 회의실 객체 하나 만들어서 종료 시간 기준 정렬해놓은 뒤, 만약 종료 시간 같다면 시작 시간 우선으로,
- 이제 차례로 arr 순회하면서 현재 회의의 종료시간보다 크거나 같은 시작 시간의 회의 발견 시, answer++ 후 ed 종료 시간을 갱신시킨다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
/*1931번. 회의실 배정 */
class Heai implements Comparable<Heai>{
int st, ed;
Heai(int st, int ed){
this.st = st;
this.ed = ed;
}
@Override
public int compareTo(Heai o) {
if(this.ed == o.ed) {//종료 시간 같다면
return this.st - o.st;//시작 시간 기준 오름차순
}
return this.ed - o.ed;//종료 시간 기준 오름차순
}
}
public class Main {
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int N = kb.nextInt();
ArrayList<Heai> arr = new ArrayList<>();
for(int i=0; i<N; i++) {
int a = kb.nextInt();
int b= kb.nextInt();
arr.add(new Heai(a, b));//객체 담고
}
//저 기준대로 정렬
Collections.sort(arr);
//그리디 알고리즘 - 종료 시간 기준 정렬 해놓고,선택 한 종료 시간보다 크거나 같은 시작 시간 갖는 애 택
int answer= 1;//일단 얘는 한다 생각 하고 카운팅
int ed = arr.get(0).ed; //첫번쨰 종료 시간
for(int i=1; i<N; i++) {
if(ed <= arr.get(i).st) {//현재 끝 시간 다음에 올 수 있는 시작 회의 발견 시
answer++;//누적
ed = arr.get(i).ed;//얘로 갱신
}
}
//정답 출력
System.out.println(answer);
}
}
🟦 백준 1946번. 신입 사원
- 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발
- = 하나라도 떨어지면 탈락
- 그러므로 서류성적 높은 사람 우선 정렬 시켜놓은 다음에, (현재 선택한 사람은 어쨋든 서류가 젤 높은 사람이고) 이 사람보다 면접 마저 떨어지는 사람 발견 시 탈락
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
//신입 사원
class Sawon implements Comparable<Sawon>{
int s;//서류
int m;//면접
Sawon(int s, int m){
this.s= s;
this.m = m;
}
@Override
public int compareTo(Sawon o) {
// TODO Auto-generated method stub
if(this.s == o.s) {
return this.m - o.m;//같으면 면접 오름차순 정렬
}
return this.s-o.s;//성적 등수 기준 오름차순 정렬
}
}
public class Main {
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
int T = kb.nextInt();
ArrayList<Integer> answer= new ArrayList<>();//정답용
for(int t = 0; t<T; t++) {
int N = kb.nextInt();//사람 수
ArrayList<Sawon> arr = new ArrayList<>();
for(int i=0; i<N; i++) {
int a = kb.nextInt();
int b = kb.nextInt();
arr.add(new Sawon(a, b));//성적, 면접 담기
}
//아까 기준대로 정렬시킴
Collections.sort(arr);
int cnt= 1;
int target = arr.get(0).m;
//그리디 - 서류 높은 순서대로 니까. 이제 현재 애보다 면접 등수 낮으면 탈락
for(int i=1; i<N; i++) { //뒤부터 돌면서
if(target > arr.get(i).m) { //타겟보다 더 높은 면접 점수 갖는 애 발견 시
cnt++;
target = arr.get(i).m;//면접 기준 점수 갱신
}
}
//정답 세팅
answer.add(cnt);//현재 카운팅
}
//답 출력
for(int x : answer )System.out.println(x);
}
}
🟦 침몰하는 타이타닉 | 그리디, 투포인터
- 투포인터, 그리디로 풀었다.
- 최대한 많이 태워야 보트 사용이 최소가 된다.
- 즉, 남아있는 가장 작은 값 + 가장 큰 값을 처리해서 빈틈없이 매워야 한다.
- 일단, 정렬시켜놓고, 두명의 합이 기준 값 m보다 큰지 작은지 구분시켰다.
1) 두 명의 합이 m보다 크면
- R로 찍은 값 한명만 태운다는 뜻으로 R감소 후 answer++
2) 두 명의 합이 m보다 작거나 같으면
- L++, R—:즉 둘다 처리했다 이거임. answer++
package to_0719_1;
//침몰하는 타이타닉
import java.util.*;
class Solution {
//솔루션 함수
public int solution(int[] nums, int m){//N명, Mkg 이하
int answer = 0;
//데이터 정렬시킴
Arrays.sort(nums);
int L = 0;
int R = nums.length -1;
int sum;
while(L <= R) {
sum = nums[L] + nums[R];
if(sum > m ) { // 두 값의 합이 m보다 큰 경우, 그냥 answer++처리 후. R-- | 한개만 담는다 이뜻
answer++;
R--;
}else if(sum <=m) {//작거나 같으면 둘 다 담을 수 있다는 것이므로
answer++;
L++;
R--;//두 개 다 처리했다는 뜻으로 움직임
}
}
return answer;
}
//실행 메인
public static void main(String[] args){
Solution T = new Solution();
System.out.println(T.solution(new int[]{90, 50, 70, 100, 60}, 140));
System.out.println(T.solution(new int[]{10, 20, 30, 40, 50, 60, 70, 80, 90}, 100));
System.out.println(T.solution(new int[]{68, 72, 30, 105, 55, 115, 36, 67, 119, 111, 95, 24, 25, 80, 55, 85, 75, 83, 21, 81}, 120));
}
}
🟦 최소 이동 횟수
- 최소로 이동하고 싶다는 본 뜻 = 한 번에 가장 많이 들고 가겠다는 말
- 배열 정렬시켜놓고, 양쪽 끝에서 찍은 값이 남아있는 데이터들 중 (가장 작은 + 가장 큰)의 합이 된다.
- 직전 문제와 비슷하다.
//최소 이동 횟수 : 최소로 이동하고 싶다. = 한 번에 최대한 많이 들고가고 싶다.
import java.util.*;
class Solution {
//솔루션 함수
public int solution(int[] nums){
int answer = 0;
int pivot = 5;//기준값이 될 거고
//정렬 시킴
Arrays.sort(nums);
int L = 0, R=nums.length-1;//양쪽 끝 지칭시켜놓고
int sum;
while(L <= R) {
sum = nums[L] + nums[R];
if(sum > pivot) {
R--;//큰 것만 담고 이동
answer++;
}else if(sum <= pivot) {
L++;
R--;
answer++;
}
}
return answer;
}
public static void main(String[] args){
Solution T = new Solution();
System.out.println(T.solution(new int[]{2, 5, 3, 4, 2, 3}));
System.out.println(T.solution(new int[]{2, 3, 4, 5}));
System.out.println(T.solution(new int[]{3, 3, 3, 3, 3}));
}
}
🟦 전투 게임 | 그리디
- 객체에 정보를 담아두고, 객체 정렬 기준을 공격력 (점수 높은 애 기준) 내림차순 되도록 둔다.
- 핵심은 정렬된 상태에서 현재 i로 찍은 기준 점수보다 j로 찍은 뒷 학생들은 점수가 모두 작을 수 밖에 없다
- 다른 팀이면서 점수가 작을 떄, answer의 해당 num 으로 값을 누적시킨다.
package to_0719_3;
import java.util.*;
//전투게임
class Student implements Comparable<Student>{
int num;//번호
char team;//팀 구분
int score;//공격력
Student(int num, char team, int score){
this.num = num;
this.team = team;
this.score = score;
}
@Override
public int compareTo(Student o) {
return o.score - this.score;//역순 내림차순 정렬 (큰 -작은)
}
}
class Solution {
//솔루션 함수
public int[] solution(String[] students){
int n = students.length;
int[] answer = new int[n];
ArrayList<Student> arr = new ArrayList<>();
for(int i=0; i<n; i++) {
char a = students[i].split(" ")[0].charAt(0);//첫번쨰 값은 팀으로
int b = Integer.parseInt(students[i].split(" ")[1]);
arr.add(new Student(i, a, b));//차례대로 객체 집어넣고
}
//공격력 기준 정렬
Collections.sort(arr);
for(int i=0; i<arr.size(); i++) {
//현재 i를 기준값으로
int num = arr.get(i).num;
char t = arr.get(i).team;
int sc = arr.get(i).score;
for(int j=i; j<arr.size(); j++) { //그 뒷부분 돌면서 점수 쌓고
if(t != arr.get(j).team && sc > arr.get(j).score) { //현재보다 공격력 작은 애 발견할 때마다
answer[num] += arr.get(j).score;//여기서 누적시키고
}
}
}
return answer;
}
public static void main(String[] args){
Solution T = new Solution();
System.out.println(Arrays.toString(T.solution(new String[]{"a 20", "b 12", "a 10", "c 11", "e 12"})));
System.out.println(Arrays.toString(T.solution(new String[]{"a 17", "b 12", "a 10", "c 11", "b 24", "a 25", "b 12"})));
System.out.println(Arrays.toString(T.solution(new String[]{"b 20", "c 15", "a 200", "b 11", "b 24", "a 25", "b 12"})));
System.out.println(Arrays.toString(T.solution(new String[]{"a 30", "a 25", "a 25", "b 20", "b 25", "a 25", "b 30"})));
}
}
🟦 스프링 쿨러 - 그리디
- line[i][0] 에는 좌표 시작값, line[i][1] 에는 좌표 끝값을 담아주고 각 로프 i에 대하여 담아준다.
- st 보다 작거나 같은 시작점을 가진 애들 중에선, ed값이 가장 큰 (즉 범위 많이 커버 가능한) 애들을 선택하고 갱신시킨다.
import java.util.*;
//스프링쿨러 문제 풀이
class Solution {
public int solution(int n, int[] nums){
int answer = 0;
int[][] line = new int[nums.length+1][2];
//세팅
for(int i=0; i<=n; i++) {//각 로프i를 사용했을 때
line[i][0] = Math.max(0, i-nums[i]);//범위 시작값 (0은 안벗어나게)
line[i][1] = Math.min(n, i+nums[i]);//범위 끝값 (n은 안벗어나게)
}
//왼쪽 시작값 기준 오름차순 정렬
Arrays.sort(line, (a, b)-> a[0]-b[0]);//시작값 기준 정렬
int st = 0, ed = 0, i=0;
while(i<line.length) {
//시작점이 st보다 작거나 같은 스프링쿨러들 중에서 가장 길게 뿌릴 수 있는 애 찾는 거임
while(line[i][0] <= st) {
ed = Math.max(ed, line[i][1]); //끝점이 기존ed보다 큰 애 발견 시, 갱신
i++;
}
answer++;
if(ed == n) return answer; //끝점 다으면 종료
//위를 거쳐왔는데 ed값이 갱신 안되고 st=ed값이 됐다면 조건에 만족하는 애 없다는 거니 -1 리턴
if(st == ed) return -1; //시작점이 ed가 되어 버리면 -1리턴
st = ed;//이제 시작점을 다시 끝점으로 갱신 <-얘를 기준으로 선택
}
return answer;
}
//실행 메인
public static void main(String[] args){
Solution T = new Solution();
System.out.println(T.solution(8, new int[]{1, 1, 1, 2, 1, 1, 2, 1, 1}));
System.out.println(T.solution(4, new int[]{1, 2, 2, 0, 0}));
System.out.println(T.solution(5, new int[]{2, 0, 0, 0, 0, 2}));
System.out.println(T.solution(11, new int[]{1, 2, 3, 1, 2, 1, 1, 2, 1, 1, 1, 1}));
}
}
🟦 꽃이 피는 최단 시간
- 심는 시간은 겹쳐서는 안된다.
- flower[i][0] = 심는 시간, flower[i][1] = 성장 시간으로 둔다.
- 성장시간 기준으로 역순 정렬 (큰 -> 작은)
- 차례로 시작 점 = 직전 꽃의 심는 시간으로 갱신해주면서 가장 큰 최종 시간을 answer로 갱신
package to_0724_6;
import java.util.*;
class Solution {
//솔루션 함수
public int solution(int[] plantTime, int[] growTime){
int answer = 0;
int n = growTime.length;
int[][] flower = new int[n][2];
for(int i=0; i<n; i++) {
flower[i][0] = plantTime[i];
flower[i][1] = growTime[i];
}
//정렬-성장시간 역순
Arrays.sort(flower, (a,b) -> (b[1]- a[1]));
//그리디
int st=0, ed = 0;
for(int[] x : flower) {
ed = st + x[0] + x[1];//시작+심기+성장
answer = Math.max(answer, ed);
st += x[0];//성장시간
}
return answer;
}
public static void main(String[] args){
Solution T = new Solution();
System.out.println(T.solution(new int[]{1, 3, 2}, new int[]{2, 3, 2}));
System.out.println(T.solution(new int[]{2, 1, 4, 3}, new int[]{2, 5, 3, 1}));
System.out.println(T.solution(new int[]{1, 1, 1}, new int[]{7, 3, 2}));
System.out.println(T.solution(new int[]{5, 7, 10, 15, 7, 3, 5}, new int[]{6, 7, 2, 10, 15, 6, 7}));
System.out.println(T.solution(new int[]{1, 2, 3, 4, 5, 6, 7}, new int[]{7, 5, 4, 3, 2, 1, 6}));
}
}
728x90
'알고리즘 이론 [개념] > [복습] 코테_알고리즘 복습' 카테고리의 다른 글
| 알고리즘 및 코테 복습 - DP 동적 계획법 (0) | 2023.07.25 |
|---|---|
| 알고리즘 및 코테 복습 - 그래프(Graph) (0) | 2023.07.24 |
| 알고리즘 및 코테 복습 - DFS, BFS, 이진 탐색 (0) | 2023.07.17 |
| 알고리즘 및 코테 복습 - 구간합, 투포인터, 스택과 큐 (0) | 2023.07.17 |