close
프로필 배경
프로필 로고

TIL 혼자 정리

알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1 · 2023. 3. 30. fullscreen 넓게보기

그리디 알고리즘 섹션 - (1)

728x90

📍 섹션9. Greedy 그리디 알고리즘

그리디 알고리즘 섹션 - (1)

🟪 그리디 알고리즘

  • 현재 상태에서의 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘
  • 매순간 최선의 선택지를 선택
  • 단, 항상 최적의 해를 보장하지는 못한다.

9-1. 씨름 선수

🟪 객체 비교 | compareTo() 재정의

//A기준 오름차순 : this.A - 대상.A
//A기준 내림차순 : 대상.A - this.A

  • 1) 키 기준 내림차순 정렬된 상태에서,
  • 2) 몸무게가 이전 max보다 작은 애가 나오면 (키 + 몸무게까지) 모두 미달인 것이므로 탈락임
  • 3) 그러므로 max가 갱신될 때마다 선발생으로 카운팅
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/* 9-1. 씨름 선수 
 * A와 다른 모든 선수 비교하며 (키 & 무게) 모두 높은 애만 선발/모두 낮으면 탈락시킴 */

class Body implements Comparable<Body>{
    public int h, w;
    Body(int h, int w){
        this.h = h;
        this.w = w;
    }
    //객체 비교 메소드 
    public int compareTo(Body o) {
        return o.h - this.h; //키 기준 내림차순이 됨
        //A기준 오름차순 : this.A - 대상.A
        //A기준 내림차순 : 대상.A - this.A
    };
}

public class Main1 {
    //솔루션 함수 
    public int solution(ArrayList<Body> arr, int n) {
        int cnt = 0;
        Collections.sort(arr); //내림차순 객체 정렬 
        int max = Integer.MIN_VALUE;
        //이미 키 기준 정렬되어 있기 때문에 
        //다음 순서대로 돌면서 기준 max보다 큰값이 나오면 카운팅한다. (선발)
        //기준 max보다 작은 애들이 나오면 탈락인 이유는 
        //이미 키 기준 후순위인데, 몸무게까지 낮은 상황이기 때문임
        for(Body ob : arr) { //키 기준 내림차순 정렬된 애 하나씩 뽑아와서
            //몸무게만 비교하면됨. 
            if(ob.w > max) {
                max = ob.w;
                cnt++;
            }
        }
        return cnt;
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        ArrayList<Body> arr = new ArrayList<>();
        for(int i=0; i<n; i++) {
            int h = kb.nextInt();
            int w = kb.nextInt();
            arr.add(new Body(h,w));
        }
        System.out.println(T.solution(arr, n));
    }

}

9-2. 회의실 배정

  • 이 경우, 최대한 많이 회의할 수 있길 원하는 것이므로
  • 1) 끝나는 시간 기준 정렬 후
  • 2) 현재 끝나는 시간 기준, 얘보다 시작 시간 이 크거나 같은 회의를 선택해나가면 됨
  • 3) 만약 끝나는 시간이 모두 같다면, 그때는 시작시간 기준 재정렬해야함.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/* 9-2. 회의실 배정 */
class Time implements Comparable<Time>{
    public int s, e; //시작, 끝 시간
    Time(int s, int e){
        this.s = s;
        this.e = e;
    }
    @Override
    public int compareTo(Time o) {
        // TODO Auto-generated method stub
        //만약 끝 시간이 같은 경우
        if(this.e == o.e) {
            return this.s - o.e; //시작시간 기준 오름차순 정렬
        }
        else return this.e - o.e;//기본적으로 끝 시간 기준 오름차순 정렬 
    }
}

public class Main2 {
    //솔루션 함수 
    public int solution(ArrayList<Time> arr, int n) {
        int cnt= 0;
        //정렬
        Collections.sort(arr);

        int et = 0; //끝나는 시간을 최소로 잡아두고 
        for(Time ob : arr) {//하나씩 꺼내오는데
            //꺼낸 회의의 시작시간이 기존 끝나는 회의 시간보다 크다면 회의 가능
            if(ob.s >= et) {
                cnt++; //카운팅
                et = ob.e; //끝나는 시간 = 현재 선택한 회의 끝 시간 
            }
        }
        return cnt;
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();
        Scanner kb = new Scanner(System.in);
        int n= kb.nextInt();
        ArrayList<Time> arr = new ArrayList<>();

        for(int i=0; i<n; i++) {
            int s = kb.nextInt();
            int e = kb.nextInt();
            arr.add(new Time(s, e));
        }

        System.out.println(T.solution(arr, n));        
    }
}

9-3. 결혼식 최대 인원

  • 각 Time1 객체는 (시간, 상태) 담음
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/* 9-3. 결혼식 최대 인원  */
class Time1 implements Comparable<Time1>{
    public int time;
    public char state;
    Time1(int time, char state){
        this.time = time;
        this.state = state;
    }
    public int compareTo(Time1 o) {
        //시간이 같으면 상태 기준 오름차순 정렬 
        if(this.time == o.time) return this.state - o.state;
        else return this.time - o.time;
    };
}
public class Main3 {
    //솔루션 
    public int solution(ArrayList<Time1> arr) {
        int answer = Integer.MIN_VALUE;

        Collections.sort(arr);//정렬
        //시간 기준 오름차순, 동일 시간에 대해서는 상태 알파벳 순으로 (e -> s) 순 처리
        //현 순간 사람 카운팅용 
        int cnt= 0;
        for(Time1 x : arr) {
            //시작 시간 떄 카운팅하고 
            if(x.state == 's') cnt++;
            else cnt--; //끝나면 빼버림
            answer = Math.max(answer, cnt);//기존 answer 보다 카운팅 클 때 교체
        }
        return answer; 
    }

    //메인 실행 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        ArrayList<Time1> arr = new ArrayList<>();
        for(int i=0; i<n; i++) {
            int sT = kb.nextInt();
            int eT = kb.nextInt();
            arr.add(new Time1(sT, 's'));
            arr.add(new Time1(eT, 'e'));
        }

        System.out.println(T.solution(arr));
    } 
}
728x90
저작자표시 비영리 변경금지

'알고리즘 이론 [개념] > [개념] 코테 알고리즘 공부 - 시즌 1' 카테고리의 다른 글

트리 관련 개념 정리  (0) 2023.04.03
그리디 알고리즘 섹션 - (2)  (0) 2023.03.31
DFS, BFS 활용 섹션 -(5) | 복습  (0) 2023.03.29
DFS, BFS 활용 섹션 -(4)  (0) 2023.03.28
DFS, BFS 활용 섹션 - (3)  (0) 2023.03.27
알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 1 관련 글
더 보기

티스토리툴바