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 |