본문 바로가기
알고리즘/JAVA

Greedy Algorithm

by vivi 2021. 10. 4.

1. 씨름선수

import java.util.*;

class Main {

	public int solution(int n, int[][] arr) {
		int answer = n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
					answer--;
					break;
				}
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[][] arr = new int[n][2];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < 2; j++) {
				arr[i][j] = kb.nextInt();
			}
		System.out.print(T.solution(n, arr));
	}
}

N(5<=N<=30,000) 이기 때문에 O(n^2) 으로는 시간 초과가 된다. (채점은 통과하긴 했다.)

import java.util.*;

class Body implements Comparable<Body> {
	int height, weight;

	Body(int h, int w) {
		this.height = h;
		this.weight = w;
	}

	@Override
	public int compareTo(Body o) {
		// TODO Auto-generated method stub
		if (this.height == o.height)
			return o.weight - this.weight;
		else
			return o.height - this.height;
	}
}

class Main {

	public int solution(int n, ArrayList<Body> arr) {
		int answer = 1;
		int max = arr.get(0).weight;
		for (int i = 1; i < n; i++) {
			if (arr.get(i).weight > max) {
				max = arr.get(i).weight;
				answer++;
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		ArrayList<Body> arr = new ArrayList<>(n);
		for (int i = 0; i < n; i++)
			arr.add(new Body(kb.nextInt(), kb.nextInt()));

		Collections.sort(arr);

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

정렬 후 비교해나가는 방식. O(n)

 

import java.util.*;

class Body implements Comparable<Body> {
	int height, weight;

	Body(int h, int w) {
		this.height = h;
		this.weight = w;
	}

	@Override
	public int compareTo(Body o) {
		// TODO Auto-generated method stub
		return o.height - this.height;
	}
}

class Main {
	public int solution(int n, ArrayList<Body> arr) {
		int answer = 0;
		int max = Integer.MIN_VALUE;
		for (Body ob : arr) {
			if (ob.weight > max) {
				answer++;
				max = ob.weight;
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		ArrayList<Body> arr = new ArrayList<>(n);
		for (int i = 0; i < n; i++)
			arr.add(new Body(kb.nextInt(), kb.nextInt()));
		Collections.sort(arr);
		System.out.print(T.solution(n, arr));
	}
}

 

2. 회의실 배정

import java.util.*;

class Item implements Comparable<Item> {
	int s, e;

	Item(int s, int e) {
		this.s = s;
		this.e = e;
	}

	@Override
	public int compareTo(Item o) {
		// TODO Auto-generated method stub
		if (this.e == o.e)
			return this.s - o.s;
		else
			return this.e - o.e;
	}
}

class Main {
	public int solution(int n, ArrayList<Item> arr) {
		int answer = 0;
		int next = 0;
		for (Item ob : arr) {
			if (ob.s >= next) {
				next = ob.e;
				answer++;
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		ArrayList<Item> arr = new ArrayList<>(n);
		for (int i = 0; i < n; i++)
			arr.add(new Item(kb.nextInt(), kb.nextInt()));
		Collections.sort(arr);
		System.out.print(T.solution(n, arr));
	}
}

 

3. 결혼식

import java.util.*;

class Time implements Comparable<Time> {
	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.s == o.s)
			return this.e - o.e;
		else
			return this.s - o.s;
	}
}

class Main {
	public int solution(int n, ArrayList<Time> arr) {
		int answer = Integer.MIN_VALUE;
		int tmp = 0;
		for (int i = 0; i < n; i++) {
			tmp = i + 1;
			for (int j = 0; j < i; j++) {
				if (arr.get(j).e <= arr.get(i).s)
					tmp--;
			}
			answer = Math.max(answer, tmp);
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		ArrayList<Time> arr = new ArrayList<>(n);
		for (int i = 0; i < n; i++)
			arr.add(new Time(kb.nextInt(), kb.nextInt()));
		Collections.sort(arr);
		System.out.print(T.solution(n, arr));
	}
}

N(5<=N<=100,000), O(n^2) 시간 초과

 

import java.util.*;

class Main {
	public int solution(int n, int[] arr) {
		int answer = Integer.MIN_VALUE;
		int cnt = 0;
		for (int i = 0; i < 73; i++) {
			cnt += arr[i];
			answer = Math.max(answer, cnt);
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[73];
		for (int i = 0; i < n; i++) {
			arr[kb.nextInt()]++;
			arr[kb.nextInt()]--;
		}
		System.out.print(T.solution(n, arr));
	}
}

 

import java.util.*;

class Time implements Comparable<Time> {
	int time;
	char state;

	Time(int time, char state) {
		this.time = time;
		this.state = state;
	}

	@Override
	public int compareTo(Time o) {
		if (this.time == o.time)
			return this.state - o.state;
		else
			return this.time - o.time;
	}
}

class Main {
	public int solution(int n, ArrayList<Time> arr) {
		int answer = Integer.MIN_VALUE;
		int cnt = 0;
		for (Time t : arr) {
			if (t.state == 'e')
				cnt--;
			else
				cnt++;
			answer = Math.max(answer, cnt);
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		ArrayList<Time> arr = new ArrayList<>(2*n);
		for (int i = 0; i < n; i++) {
			arr.add(new Time(kb.nextInt(), 's'));
			arr.add(new Time(kb.nextInt(), 'e'));
		}
		Collections.sort(arr);
		System.out.print(T.solution(n, arr));
	}
}

 

4. 최대 수입 스케쥴

import java.util.*;

class Schedule implements Comparable<Schedule> {
	int d, m;

	Schedule(int d, int m) {
		this.d = d;
		this.m = m;
	}

	@Override
	public int compareTo(Schedule o) {
		if (this.d == o.d)
			return o.m - this.m;
		else
			return o.d - this.d;
	}
}

class Main {
	public int solution(int n, ArrayList<Schedule> arr) {
		int answer = 0;
		int day = arr.get(0).d;
		for (int i = day; i > 0; i--) {
			int len = arr.size();
			int idxtmp = 0;
			boolean flag = false;
			for (int j = 0; j < len; j++) {
				if (arr.get(j).d < i)
					break;
				else {
					flag = true;
					if (arr.get(j).m > arr.get(idxtmp).m) {
						idxtmp = j;
					}
				}
			}
			if (flag) {
				answer += arr.get(idxtmp).m;
				arr.remove(idxtmp);
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		ArrayList<Schedule> arr = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			int m = kb.nextInt();
			int d = kb.nextInt();
			arr.add(new Schedule(d, m));
		}
		Collections.sort(arr);
		System.out.print(T.solution(n, arr));
	}
}

 

우선순위 큐 사용, 이진트리로 구성되어있어 log n의 성능이다.

import java.util.*;

class Schedule implements Comparable<Schedule> {
	int d, m;

	Schedule(int d, int m) {
		this.d = d;
		this.m = m;
	}

	@Override
	public int compareTo(Schedule o) {
		return o.d - this.d;
	}
}

class Main {
	public int solution(int n, ArrayList<Schedule> arr) {
		int answer = 0;
		int max = arr.get(0).d;
		// 작은 값을 우선 순위로 하는 우선 순위 큐
		// PriorityQueue<Integer> pQ = new PriorityQueue<>();

		// 큰 값을 우선 순위로 하는 우선 순위 큐
		PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
		int j = 0;
		for (int i = max; i > 0; i--) {
			for (; j < n; j++) {
				if (arr.get(j).d < i)
					break;
				else {
					pQ.offer(arr.get(j).m);
				}
			}
			if (!pQ.isEmpty())
				answer += pQ.poll();
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		ArrayList<Schedule> arr = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			int m = kb.nextInt();
			int d = kb.nextInt();
			arr.add(new Schedule(d, m));
		}
		Collections.sort(arr);
		System.out.print(T.solution(n, arr));
	}
}

 

5. 다익스트라 알고리즘

import java.util.*;

class 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) {
		// TODO Auto-generated method stub
		return this.cost - ob.cost;
	}
}

class Main {
	static int n, m;
	static ArrayList<ArrayList<Edge>> graph;
	static int[] dis;

	public 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;
			if (nowCost > dis[now])
				continue;
			for (Edge ob : graph.get(now)) {
				if (dis[ob.vex] > nowCost + ob.cost) {
					dis[ob.vex] = nowCost + ob.cost;
					pQ.offer(new Edge(ob.vex, nowCost + ob.cost));
				}
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.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 = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			graph.get(a).add(new Edge(b, c));
		}
		T.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 + " : imposible");
		}

	}
}

 

6. 친구인가? (Disjoint-Set : Union&Find) 서로소 집합

import java.util.*;

class Main {
	public String solution(int n, int[][] arr, int a, int b) {
		Queue<Integer> q = new LinkedList<>();
		int[] check = new int[n + 1];
		check[a] = 1;
		for (int i = 1; i < n + 1; i++) {
			if (arr[i][a] == 1 || arr[a][i] == 1)
				q.offer(i);
		}
		while (!q.isEmpty()) {
			int cur = q.poll();
			if (cur == b)
				return "YES";
			else {
				for (int i = 1; i < n + 1; i++) {
					if ((arr[i][cur] == 1 || arr[cur][i] == 1) && check[i] == 0) {
						check[i] = 1;
						q.offer(i);
					}
				}
			}
		}
		return "NO";
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[][] arr = new int[n + 1][n + 1];
		for (int i = 0; i < m; i++) {
			arr[kb.nextInt()][kb.nextInt()] = 1;
		}
		int a = kb.nextInt();
		int b = kb.nextInt();
		System.out.print(T.solution(n, arr, a, b));
	}
}

 

import java.util.*;

class Main {
	static int[] unf;

	public static int find(int v) {
		if (unf[v] == v)
			return v;
		else
			return unf[v] = find(unf[v]);
	}

	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 kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		unf = new int[n + 1];
		for (int i = 1; i < n + 1; i++)
			unf[i] = i;
		for (int i = 0; i < m; i++) {
			union(kb.nextInt(), kb.nextInt());
		}
		if (find(kb.nextInt()) != find(kb.nextInt()))
			System.out.print("NO");
		else
			System.out.print("YES");
	}
}

 

최소 스패닝 트리를 만드는 방법 크루스칼 & 프림 알고리즘

7. 원더랜드(크루스칼 : Uion&Find)

import java.util.*;

class Edge implements Comparable<Edge> {
	int v1, v2, cost;

	public Edge(int v1, int v2, int cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.cost - o.cost;
	}
}

class Main {
	static ArrayList<Edge> arr;
	static int[] unf;

	public int find(int fa) {
		if (fa == unf[fa])
			return unf[fa];
		else
			return unf[fa] = find(unf[fa]);
	}

	public void union(int a, int b) {
		int fa = find(a);
		int fb = find(b);
		if (fa != fb) {
			unf[fa] = fb;
		}
	}

	public int solution() {
		int answer = 0;
		for (Edge e : arr) {
			int v1 = e.v1;
			int v2 = e.v2;
			if (find(v1) != find(v2)) {
				union(v1, v2);
				answer += e.cost;
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int v = kb.nextInt();
		int e = kb.nextInt();
		arr = new ArrayList<>(e);
		unf = new int[v + 1];
		for (int i = 1; i < v + 1; i++) {
			unf[i] = i;
		}
		for (int i = 0; i < e; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			arr.add(new Edge(a, b, c));
		}
		Collections.sort(arr);
		System.out.print(T.solution());
	}
}

 

import java.util.*;

class Edge implements Comparable<Edge> {
	int v2, cost;

	public Edge(int v2, int cost) {
		this.v2 = v2;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.cost - o.cost;
	}
}

class Main {
	static ArrayList<ArrayList<Edge>> arr;
	static int[] ch;

	public int solution() {
		int answer = 0;
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		pQ.offer(new Edge(1, 0));
		while (!pQ.isEmpty()) {
			Edge e = pQ.poll();
			if (ch[e.v2] != 1) {
				ch[e.v2] = 1;
				answer += e.cost;
				for (int i = 0; i < arr.get(e.v2).size(); i++) {
					Edge tmp = arr.get(e.v2).get(i);
					if (ch[tmp.v2] != 1)
						pQ.offer(tmp);
				}
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int v = kb.nextInt();
		int e = kb.nextInt();
		ch = new int[v + 1];
		arr = new ArrayList<ArrayList<Edge>>(v + 1);
		for (int i = 0; i < v + 1; i++) {
			arr.add(new ArrayList<Edge>());
		}
		for (int i = 0; i < e; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			arr.get(a).add(new Edge(b, c));
			// 무방향이므로 양쪽에서 이동 할 수 있도록
			arr.get(b).add(new Edge(a, c));
		}
		System.out.print(T.solution());
	}
}

'알고리즘 > JAVA' 카테고리의 다른 글

dynamic programming(동적계획법)  (0) 2021.10.06
DFS, BFS 활용  (0) 2021.09.27
Recursive, Tree, Graph(DFS, BFS 기초)  (0) 2021.09.26
10. 마구간 정하기(결정알고리즘)  (0) 2021.09.25
9. 뮤직비디오(결정알고리즘)  (0) 2021.09.25

관련글

댓글

티스토리툴바