Greedy
유형
1.씨름 선수
//문제
“A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은
(크고, 무겁다) 지원자가 존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.” N명의
지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는
프로그램을 작성
//입력
5
172 67
183 65
180 70
170 72
181 60
//출력
3class Body implements Comparable<Body>{
public int h,w;
public Body(int h, int w) {
this.h = h;
this.w = w;
}
@Override
public int compareTo(Body o) {
return o.h-this.h;
}
}
public class ex1 {
public static int solution(ArrayList<Body> arr, int n){
int cnt=0;
Collections.sort(arr);
int max=Integer.MIN_VALUE;
for(Body x : arr){
if(x.w > max){
max=x.w;
cnt++;
}
}
return cnt;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n= sc.nextInt();
ArrayList<Body> arr = new ArrayList<>();
for(int i=0; i<n; i++){
int h=sc.nextInt();
int w=sc.nextInt();
arr.add(new Body(h,w));
}
System.out.println(solution(arr,n));
}
}
풀이
1.h,w를 받을 수 있는 Body객체를 생성해서 ArrayList에 추가한다.
2.Comparable을 상속받아서 키 내림차순으로 정렬하고 Collections.sort(arr)을 해준다.
3.키는 이미 정렬되어 있기 때문에 키는 x가 다음으로 갈수록 무조건 작고, 앞사람보다 몸무게도 작으면 탈락이다.앞사람보다 몸무게가 더 크면 선발되기 때문에 cnt++을 해준다.(최댓값 알고리즘)
2.회의실 배정
//문제
각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서
회의실을 사용할 수 있는 최대수의 회의를 찾아라.
//입력
5
1 4
2 3
3 5
4 6
5 7
//출력
3class Time implements Comparable<Time>{
public int startT;
public int lastT;
public Time(int startT, int lastT) {
this.startT = startT;
this.lastT = lastT;
}
@Override
public int compareTo(Time o) {
if(this.lastT==o.lastT) return this.startT-o.startT;
else return this.lastT-o.lastT;
}
}
public class ex2 {
public static int solution(ArrayList<Time> arr,int n){
int answer =0;
Collections.sort(arr);
int end=Integer.MIN_VALUE;
for(Time x : arr){
if(x.startT >= end){
answer++;
end=x.lastT;
}
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n= sc.nextInt();
ArrayList<Time> arr = new ArrayList<>();
for(int i=0; i<n; i++){
int startT=sc.nextInt();
int lastT=sc.nextInt();
arr.add(new Time(startT,lastT));
}
System.out.println(solution(arr,n));
}
}
풀이
1.시작시간,끝시간 저장가능한 객체 Time생성 후 끝나는 시간을 오름차순 기준으로 정렬, Collections.sort(arr)
2.end라는 값을 선언하고 각 x의 끝나는 시간으로 만든다. 다음 x의 시작시간이 현재 end의 시간과 일치하거나 더 크면 회의실 사용이 가능해서 answer++을 해주고 end를 현재 x의 끝나는 시간으로 초기화해준다.
3.결혼식
//문제
최대 3일동안 피로연장을 빌렸을때 동시에 존재하는 최대인원을 출력해라.
시간은 0~72까지
//입력
5
14 18
12 15
15 20
20 30
5 14
//출력
2class Clock implements Comparable<Clock>{
int time;
char state;
public Clock(int time, char state) {
this.time = time;
this.state = state;
}
@Override
public int compareTo(Clock o) {
if(this.time == o.time) return this.state - o.state;
else return this.time - o.time;
}
}
public class ex3 {
public static int solution(ArrayList<Clock> arr){
int answer = Integer.MIN_VALUE;
int cnt = 0;
Collections.sort(arr);
for(Clock x : arr){
if(x.state =='s') cnt++;
else cnt--;
answer = Math.max(answer, cnt);
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Clock> arr = new ArrayList<>();
for(int i=0; i<n; i++){
int st = sc.nextInt();
int et = sc.nextInt();
arr.add(new Clock(st,'s'));
arr.add(new Clock(et,'e'));
}
System.out.println(solution(arr));
}
}풀이
1.우선 st는 's', et는 'e' 로 Clock객체에 시간기준 오름차순으로 따로따로 입력받아서 저장한다. 시간이 겹칠 경우에는 et먼저 빼내야하기 때문에 오름차순으로 정렬해서
'e'가 먼저 빠질수있게 정렬한다.
2.Collections.sort(arr)한 다음에 forEach문을 돌린다. 여기서 's'를 만나면 cnt++; 'e'를 만나면 cnt--;를 해준다. 이때 cnt가 최고일 때의 값을 answer에 담는다.
4.최대 수입 스케쥴(PriorityQueue 응용문제)
//
현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강
연을 해 주면 M만큼의 강연료를 주기로 했다.
각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.
//입력
6
50 2
20 1
40 2
60 3
30 3
30 1
//출력
150class Lecture implements Comparable<Lecture>{
public int money;
public int day;
Lecture(int money, int day){
this.money = money;
this.day = day;
}
@Override
public int compareTo(Lecture o) {
return o.day - this.day;
}
}
public class ex4 {
static int n=0,max=Integer.MIN_VALUE;
public static int solution(ArrayList<Lecture> arr){
int answer=0;
//작은 값 우선
//PriorityQueue pQ = new PriorityQueue<>();
//큰 값 우선
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
Collections.sort(arr);
int j=0;
for(int i=max; i>=1; i--){
for( ; j<n; j++){ //j값 유지
if(arr.get(j).day<i) break; //max보다 작으면 그만
pQ.offer(arr.get(j).money);
}
if(!pQ.isEmpty()) answer+=pQ.poll();
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
ArrayList<Lecture> arr = new ArrayList<>();
for(int i=0; i<n; i++){
int money = sc.nextInt();
int day = sc.nextInt();
arr.add(new Lecture(money,day));
if(day>max) max=day;
}
System.out.println(solution(arr));
}
}풀이
1.Lecture객체를 만들어서 Comparable을 상속받아 day내림차순으로 정렬한다. Collection.sort(arr)해준다.
2.PriorityQueue를 Collections.reverseOrder()로 선언해준다. 이렇게 선언하면 pQ.poll()을 했을때 큰값을 먼저 뺀다.
3.그렇게 해서 입력받은 day의 최고값을 max라고 해주고, max를 내림차순으로 2중for문을 이용해서 해당 day의 money에 접근한다. 이때 j의 값을 계속 유지시키기 위해서 j를 for문 밖에 선언한다.
4.3일의 기간이 있는 강연은 둘째,첫째날에도 해도 되기 때문에 pQ에 저장된 거에서 그냥 큰값만 빼면 된다.
5.💥 다익스트라 알고리즘(많이 어려움,이해 잘안됨)
//문제
아래의 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하는 프로
그램을 작성하세요. (경로가 없으면 Impossible를 출력한다)
정점의수n , 간선의수m 입력받음.
//입력
6 9
1 2 12 // 1번 정점에서 2번정점으로 가는데 12의 비용이 든다.
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5
//출력
2 : 11
3 : 4
4 : 9
5 : 14
6 : impossibleclass Edge implements Comparable<Edge>{
public int vex; //정점
public int cost; //가중치 값
Edge(int vex, int cost) {
this.vex = vex;
this.cost = cost;
}
@Override
public int compareTo(Edge ob){
return this.cost-ob.cost; //가중치 값기준으로 오름차순
}
}
public class ex5 {
static int n, m;
static ArrayList<ArrayList<Edge>> graph;
static int[] dis;
public static void solution(int v){
PriorityQueue<Edge> pQ = new PriorityQueue<>();
pQ.offer(new Edge(v, 0));
dis[v]=0;
while(!pQ.isEmpty()){
Edge tmp=pQ.poll(); //가장 비용이 작은 값
int now=tmp.vex;
int nowCost=tmp.cost;
//나중에 poll하는 nowCost가 기존 dis[now]보다 크면 forEach x
if(nowCost>dis[now]) continue;
//핵심
for(Edge x : graph.get(now)){
if(dis[x.vex]>nowCost+x.cost){
dis[x.vex]=nowCost+x.cost;
pQ.offer(new Edge(x.vex, nowCost+x.cost));
}
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
graph = new ArrayList<ArrayList<Edge>>();
for(int i=0; i<=n; i++){
graph.add(new ArrayList<Edge>());
}
dis=new int[n+1];
Arrays.fill(dis, Integer.MAX_VALUE); //매우 큰값으로 기본값 세팅
for(int i=0; i<m; i++){
int a=sc.nextInt(); //a에서
int b=sc.nextInt(); //b로
int c=sc.nextInt(); //가중치 값
graph.get(a).add(new Edge(b, c));
}
solution(1);
for(int i=2; i<=n; i++){
if(dis[i]!=Integer.MAX_VALUE) System.out.println(i+" : "+dis[i]);
else System.out.println(i+" : impossible");
}
}
}
풀이
1.우선 이런 가중치 문제는 무조건 인접리스트를 이용해서 값을 담아야한다.
2.Edge라는 객체를 만든다. 그리고 가중치거리의 최단거리를 저장할 dis[]을 만든다.그리고 dis[]에 값을 모두 Arrays.fill(dis,MAX_VALUE)로 선언해준다.
3.인접리스트에는 6개가 저장되고 , 그 6개의 정점에대한 간선과 가중치값이 저장되어있다.이때 이 인접리스트를 가중치값을 기준으로 오름차순으로 정렬한다. 짧은거리부터 체크해가기 위함.
4.pQ를 만들고 pQ에 pQ.offer(new Edge(v, 0)); 를 해준다. 1정점에서 1정점으로 가는 가중치는 0이기 때문에 dis[v]=0;으로 해준다.
5.while문을 돌린다. 현재 pQ의 가장 작은 값을 빼서 tmp라고 하고, 그 tmp의 정점을 now, 가중치값을 nowCost라고 한다.
6.이제 forEach문이 핵심이다. dis[]에는 다 최대값으로 초기화되어있는 상태이고 현재 정점의 가중치값과 인접리스트에 저장되어있고 forEach로 접근한 x.cost의 합이 dis[]의 값보다 낮으면, 그 합한 가중치 값으로 저장하고, pQ.offer로 그 저장한 가중치와 정점을 넣어준다.
7.여기서 나중에 poll하는 nowCost가 기존 dis[now]보다 크면 forEach를 안돌리기위해서 if(nowCost>dis[now]) continue; 를 넣어준다.
확실하게 잘 모르겠다,, 다시 보자
6.친구인가? (Disjoint-Set : Union&Find) (서로소 집합)
//문제
학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램을 작성
YES,NO
//입력
9 7
1 2
2 3
3 4
1 5
6 7
7 8
8 9
3 8
//출력
NOpublic class ex6 {
static int[] unf;
//집합으로 연결된 최댓값 찾음
public static int Find(int v){
if(v==unf[v]) return v;
else return unf[v]=Find(unf[v]);
}
//각 f(a),f(b)의 값을 찾아서 다르면 연결.
public static void Union(int a, int b){
int fa=Find(a);
int fb=Find(b);
if(fa!=fb) unf[fa]=fb;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
unf=new int[n+1];
for(int i=1; i<=n; i++) unf[i]=i;
for(int i=1; i<=m; i++){
int a =sc.nextInt();
int b =sc.nextInt();
Union(a,b); //집합생성
}
int a=sc.nextInt();
int b=sc.nextInt();
int fa=Find(a);
int fb=Find(b);
if(fa==fb) System.out.println("YES");
else System.out.println("NO");
}
}
풀이
1.unf[]라는 각 인자의 값들이 들어갈 배열을 만든다.
2.Find(int v)라는 집합으로 연결되어있는 최대값을 찾는 함수와 Union(int a, int b)이라는 각 요소 a,b를 집합으로 연결하는 함수를 만든다.
3.입력 그대로 psvm에 치고 결과 창출.
부가 설명
Find()함수는 해당 인자의 값이 v==unf[v]가 될때까지 계속 Find(unf[v]);를 재귀로 호출해서 연결되어있는 값(최대값)을 찾는다.
Union()함수는 두 인자를 받아서 각 해당하는 연결되어있는 값(최대값)을 찾은 다음 그 값들을 서로 비교해서 다르면 unf[fa]=fb;를 해줘서 더 큰 숫자로 해줌으로써 서로 연결.
그냥 무조건 외워야한다.
7.원더랜드(최소스패닝트리 : 크루스칼, Union&Find 활용)
//문제
원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.
원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는
폐쇄하려고 한다. 모든 도시를 연결하는 최소비용을 구해라.
//입력
9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15
//출력
196class Edge2 implements Comparable<Edge2>{
int v1;
int v2;
int cost;
public Edge2(int v1, int v2, int cost) {
this.v1 = v1;
this.v2 = v2;
this.cost = cost;
}
@Override
public int compareTo(Edge2 o) {
return this.cost-o.cost;
}
}
public class ex7 {
static int[] unf;
//집합으로 연결된 최댓값 찾음
public static int Find(int v){
if(v==unf[v]) return v;
else return unf[v]=Find(unf[v]);
}
//각 f(a),f(b)의 값을 찾아서 다르면 집합으로 연결.
public static void Union(int a, int b){
int fa=Find(a);
int fb=Find(b);
if(fa!=fb) unf[fa]=fb;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
unf = new int[n+1];
ArrayList<Edge2> arr =new ArrayList<>();
for(int i=1; i<=n; i++) unf[i]=i;
for(int i=0; i<m; i++){
int v1=sc.nextInt();
int v2=sc.nextInt();
int cost=sc.nextInt();
arr.add(new Edge2(v1,v2,cost));
}
//크루스칼 로직 --> 순환이 되면안됨. 트리형태가 되어야함.
int answer=0;
Collections.sort(arr);
for(Edge2 ob : arr){
int fv1=Find(ob.v1);
int fv2=Find(ob.v2);
if(fv1!=fv2){
answer+=ob.cost;
Union(ob.v1,ob.v2);
}
}
System.out.println(answer);
}
}
풀이
1.Edge라는 객체를 만들고 , 가중치 값 기준으로 오름차순으로 정렬시킨다. 낮은값부터.
2.ArrayList<객체> arr =new ArrayList<>();로 만들고 arr.add(new Edge2(v1,v2,cost)); 생성.
3.입력 값을 담은 arr을 Collections.sort(arr) 한 다음에, forEach해서 v1,v2를 Find()해서 이미 같은 집합인지 아닌지 판별한다. 같은 집합이 아니면 Union()함수를 통해 집합으로 등록하고 answer에 cost를 더한다.
크루스칼 로직은 -> 순환이 되면안된다. 트리형태가 되어야한다.
8.원더랜드(최소스패닝트리 : 프림, PriorintyQueue)
//문제
원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.
원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는
폐쇄하려고 한다. 모든 도시를 연결하는 최소비용을 구해라.
//입력
9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15
//출력
196class Edge3 implements Comparable<Edge3>{
public int vex;
public int cost;
Edge3(int vex, int cost) {
this.vex = vex;
this.cost = cost;
}
@Override
public int compareTo(Edge3 ob){
return this.cost-ob.cost;
}
}
public class ex8 {
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
ArrayList<ArrayList<Edge3>> graph = new ArrayList<ArrayList<Edge3>>();
for(int i=0; i<=n; i++){
graph.add(new ArrayList<Edge3>());
}
int[] ch = new int[n+1];
for(int i=0; i<m; i++){
int v1=sc.nextInt();
int v2=sc.nextInt();
int cost=sc.nextInt();
//방향그래프면 한방향만 넣으면되는데, 양방향이라서 두방향 다.
graph.get(v1).add(new Edge3(v2,cost));
graph.get(v2).add(new Edge3(v1,cost));
}
//프림알고리즘(우선순위 큐)
int answer=0;
PriorityQueue<Edge3> pQ = new PriorityQueue<>();
pQ.offer(new Edge3(1,0));
while (!pQ.isEmpty()){
Edge3 tmp = pQ.poll();
int ev = tmp.vex;
//회로면안되고, 트리형태를 만들기 위해서 ch[] 체크배열로 if문
if(ch[ev]==0){
ch[ev]=1;
answer+=tmp.cost;
for(Edge3 ob : graph.get(ev)){
//이미 체크된 간선 빼고
if(ch[ob.vex]==0) pQ.offer(new Edge3(ob.vex,ob.cost));
}
}
}
System.out.println(answer);
}
}풀이
1.이 방식은 우선순위큐(프림:priority)를 이용한 풀이방식이다.
2.Edge객체를 낮은 비용기준으로 정리해준다. 여기서 Edge객체는 vex,cost만 변수로 갖는다.
3.ArrayList<ArrayList<객체>> graph 방식으로 graph(방향그래프)를 선언한다.
4.입력한 정점 갯수만큼 for문을 돌려서 graph.add(new ArrayList<객체>()); 해준다. 그리고 ch[]을 만들어서 들렸던 곳을 들리지않게 선언해준다.
5.간선의 갯수만큼 for문을 돌려서 v1,v2,cost를 입력받고
graph.get(v1).add(new Edge3(v2,cost));
graph.get(v2).add(new Edge3(v1,cost));
를 해준다. 이유는 무방향(양방향)그래프 이기 때문이다. v1->v2,cost v2->v1,cost
6.PriorityQueue를 선언해준다. 그리고 pQ에 pQ.offer(new Edge3(1,0));를 해준다. 1정점으로 가는비용은 없기 때문. while문을 돌리고 poll()한 값을 tmp, tmp의 정점을 ev라고 하자. 회로가아닌, 트리형태를 만들어야하기 때문에 ch[]배열로 if문을 연다. 0이면 ch[ev]=1;로 체크해주고, asnwer에 cost를 더한다. forEach문으로 해당 poll한 정점 ev의 리스트에 접근한다. 그래서 이미 체크된(뒷 방향)방향 빼고 모든 방향을 pQ.offer를 해준다.
