인프런 JAVA 알고리즘 정리(Greedy Algorithm 1~8번)
1. 씨름 선수
키 몸무게가 있고 자신보다 키 몸무게 둘다 큰 사람이 없다면 선택
-> (183, 65) - 키가 제일 큼
-> (180, 70) - 자신보다 키가 큰 사람중 자신보다 몸무게 큰 사람이 없음
-> (170, 72) - 자신보다 키가 큰 사람중 자신보다 몸무게 큰 사람이 없음
1. 사람을 키순으로 정렬한다. ( 첫번째 사람은 일단 키가 제일 크니 픽)
2. 그 뒤로 몸무게가 앞 사람보다 크다면 픽 ( 앞사람보다 키는 작지만 몸무게는 제일 높다는 소리)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
ArrayList<Body> arr = new ArrayList<>();
for(int i=0; i<num; i++){
int h = sc.nextInt();
int w = sc.nextInt();
arr.add(new Body(h,w));
}
Collections.sort(arr);
int cnt = 1;
int weight = arr.get(0).weight;
// 몸무게가 앞에 나온 최고 몸무게 보다 크다면 선발
for(int i=1; i<arr.size(); i++){
if(weight<arr.get(i).weight){
cnt++;
weight=arr.get(i).weight;
}
}
System.out.println(cnt);
}
// 사람 클래스를 키를 기준으로 내림차순 만든다.
static class Body implements Comparable<Body>{
int key;
int weight;
public Body(int key, int weight){
this.key = key;
this.weight = weight;
}
@Override
public int compareTo(Body o) {
return o.key-this.key;
}
}
2. 회의실 배정
// 끝나는 시간을 기준으로 오름 차순 정렬 -> 빨리 끝나는거를 찾기 위해
// 끝나는 시간이 같다면? -> 시작시간을 기준으로 오름 차순
public static int solution(ArrayList<Time> arr){
int cnt =0;
int et = 0;
for(Time ob : arr) {
// 끝나는 시간 보다 시작이간이 크거나 같으면 배정
if(ob.s >= et){
cnt++;
et = ob.e;
}
}
return cnt;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
ArrayList<Time> arr = new ArrayList<>();
for(int i=0; i<num; i++){
int s = sc.nextInt();
int e = sc.nextInt();
arr.add(new Time(s,e));
}
Collections.sort(arr);
int result = solution(arr);
System.out.println(result);
}
static class Time implements Comparable<Time>{
int s;
int e;
public Time(int s, int e){
this.s = s;
this.e = e;
}
// 끝나는 시간이 같다면 시작시간을 기준으로 오름차순
@Override
public int compareTo(Time o) {
if(this.e==o.e) return this.s - o.s;
return this.e-o.e;
}
}
3. 결혼식
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] day = new int[73];
for(int i=0; i<num; i++){
int s = sc.nextInt();
int e = sc.nextInt();
for(int j=s; j<e; j++)
day[j]++;
}
int max = 0;
for(int x : day) {
if(x>max) max = x;
}
System.out.println(max);
}
4. 최대 수입 스케쥴(PriorityQueue 응용문제)
우선순위 큐 란? ( Logn )
-최소값이 기본으로 우선순위. -> poll() 가장 작은 값 리턴-최대값으로 우선순위를 한다면 reverse 해줘야 됨. -> poll() 가장 작은 큰 값 리턴
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
- 1. 돈, 날짜 중 날짜를 내림차순으로 먼저 정렬
- 2. 날짜순으로 for문을 돌며 날짜들 중 최대 강연료를 GET
static int num, max = Integer.MIN_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
num = sc.nextInt();
ArrayList<Lecture> arr = new ArrayList<>();
for(int i=0; i<num; i++){
int m = sc.nextInt();
int d = sc.nextInt();
arr.add(new Lecture(m, d));
if(d>max) max=d;
}
System.out.println(solution(arr));
}
public static int solution(ArrayList<Lecture> arr){
int answer = 0;
// 정수가 들어갔을 때 poll() 시 가장 큰값이 리턴
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
Collections.sort(arr); // 날짜에 의해 내림차순
int j=0; // 순서대로 접근하기 위해 j값을 for문 밖 초기화
for(int i=max; i>=1; i--){
for(; j<num; j++){
if(arr.get(j).time<i) break;
pQ.offer(arr.get(j).money);
}
if(!pQ.isEmpty()) answer+=pQ.poll(); // 가장 높은 강연료 GET
}
return answer;
}
public static class Lecture implements Comparable<Lecture>{
int money;
int time;
public Lecture(int money, int time){
this.money = money;
this.time = time;
}
@Override
public int compareTo(Lecture o) {
return o.time-this.time;
}
}
5. 다익스트라 알고리즘
정점으로의 최소 거리비용을 출력하는 프로그램
6. 친구인가? ( Union & Find )
서로소 집합을 만들어라. -> Union & Find 알고리즘
Union -> 한 집합으로 만드는 메서드
7. 원더랜드(최소스패닝트리 : 크루스칼)
모든 도시를 최소 비용으로 연결해라.
1. PriorityQueue를 사용하여 최소 비용을 계속 출력
2. UNION & FIND 알고리즘으로 같은 집합이면(그래프) -> 연결 금지
3. 같은 집합이 아니면(no그래프) sum에 비용추가
public static int find (int a){
if(arr[a]==a) return arr[a];
else return arr[a] = find(arr[a]);
}
public static boolean union (int start, int end){
int a = find(start);
int b = find(end);
if(a!=b) {
arr[a] = b;
return true;
}else{
return false;
}
}int sum = 0;
while(!pQ.isEmpty()){
Route route = pQ.poll();
if(union(route.start, route.end)) sum += route.value;
}
7. 원더랜드(최소스패닝트리 : 프림)
0. 각 정점을 인접리스트로 설정
1. PriorityQueue 활용
2. ch배열 설정후 작은비용이면 체크 -> 체크된 배열은 패스