이번 장에서는 Greedy 알고리즘을 활용하여 문제를 해결해본다.
모든 코드는 깃허브 (링크)의 테스트 코드로 정리해두었다.
씨름선수
현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다.
현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.
“A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은 (크고, 무겁다) 지원자가 존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.”
N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요.
- 입력설명
첫째 줄에 지원자의 수 N(5<=N<=100,000)이 주어집니다.
두 번째 줄부터 N명의 키와 몸무게 정보가 차례로 주어집니다. 각 선수의 키와 몸무게는 모두 다릅니다. - 출력설명
첫째 줄에 씨름 선수로 뽑히는 최대 인원을 출력하세요. - 입력예제 1
5
172 67
183 65
180 70
170 72
181 60 - 출력예제 1
3 - 출력설명
(183, 65), (180, 70), (170, 72) 가 선발됩니다.
(181, 60)은 (183, 65)보다 키와 몸무게 모두 낮기 때문에 탈락이고,
(172, 67)은 (180, 70) 때문에 탈락입니다. - 풀이
Greedy: 현재 상황에서 최선의 선택을 한다.
public class Wrestler {
@EqualsAndHashCode
static class Player implements Comparable<Player> {
int height;
int weight;
public Player(int height, int weight) {
this.height = height;
this.weight = weight;
}
@Override
public int compareTo(Player player) {
return player.height - this.height;
}
}
public int solution1(Player[] players) {
Arrays.sort(players);
int answer = 0;
int maxWeight = Integer.MIN_VALUE;
for (Player player : players) {
if (player.weight > maxWeight) {
answer++;
maxWeight = player.weight;
}
}
return answer;
}
@Test
@DisplayName("씨름 선수")
public void main() {
Player[] inputs = {
new Player(172, 67), new Player(183, 65), new Player(180, 70),
new Player(170, 72), new Player(181, 60)
};
int answer1 = solution1(inputs);
assertEquals(3, answer1);
}
}회의실 배정
한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다.
각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.
단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
- 입력설명
첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다.
둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.
회의 시간은 0시부터 시작된다.
회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다. - 출력설명
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라. - 입력예제 1
5
1 4
2 3
3 5
4 6
5 7 - 출력예제 1
3 - 예제설명
(2, 3), (3, 5), (5, 7)이 회의실을 이용할 수 있다. - 입력예제 2
3
3 3
1 3
2 3 - 출력예제 2
2 - 풀이
회의가 빨리 끝나는 순으로 선택을 해야한다.
public class AssignMeetingRoom {
static class Meeting implements Comparable<Meeting> {
int startTime;
int endTime;
public Meeting(int startTime, int endTime) {
this.startTime = startTime;
this.endTime = endTime;
}
@Override
public int compareTo(Meeting meeting) {
return this.endTime == meeting.endTime
? this.startTime - meeting.startTime
: this.endTime - meeting.endTime;
}
}
public int solution1(Meeting[] meetings) {
Queue<Meeting> queueOfMeetings = new PriorityQueue<>();
for (Meeting meeting : meetings) {
queueOfMeetings.offer(meeting);
}
int answer = 0;
int maxEndTime = Integer.MIN_VALUE;
while (!queueOfMeetings.isEmpty()) {
Meeting tmpMeeting = queueOfMeetings.poll();
if (tmpMeeting.startTime >= maxEndTime) {
maxEndTime = tmpMeeting.endTime;
answer++;
}
}
return answer;
}
@Test
@DisplayName("회의실 배정")
public void main() {
Meeting[] input1 = {
new Meeting(1, 4), new Meeting(2, 3), new Meeting(3, 5),
new Meeting(4, 6), new Meeting(5, 7)
};
int answer1 = solution1(input1);
assertEquals(3, answer1);
Meeting[] input2 = {
new Meeting(3, 3), new Meeting(1, 3), new Meeting(2, 3)
};
int answer2 = solution1(input2);
assertEquals(2, answer2);
}
}결혼식
현수는 다음 달에 결혼을 합니다.
현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.
피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다.
각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다.
현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요.
만약 한 친구가 오는 시간 13, 가는 시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다.
- 입력설명
첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.
시간은 첫날 0시를 0으로 해서 마지막날 밤 12시를 72로 하는 타임라인으로 오는 시간과 가는 시간이 음이 아닌 정수로 표현됩니다. - 출력설명
첫째 줄에 피로연장에 동시에 존재하는 최대 인원을 출력하세요. - 입력예제 1
5
14 18
12 15
15 20
20 30
5 14 - 출력예제 1
2 - 풀이
동일한 시간에 가는 사람과 오는 사람이 있는 경우 항상 가는 사람이 먼저 간다는 것을 주의할 것!
public class Wedding {
static class Time implements Comparable<Time> {
int time;
char status; // a = 가는 시간, b = 오는 시간
public Time(int time, char status) {
this.time = time;
this.status = status;
}
// 시작시간 순으로 오름차순
// 시작시간이 동일한 경우 status값 기준으로 오름차순
@Override
public int compareTo(Time t) {
return this.time == t.time
? this.status - t.status
: this.time - t.time;
}
}
public int solution1(Time[] times) {
Arrays.sort(times);
int answer = Integer.MIN_VALUE;
int count = 0;
for (Time time : times) {
if (time.status == 'b') {
count++;
} else {
count--;
}
answer = Math.max(answer, count);
}
return answer;
}
@Test
@DisplayName("결혼식")
public void main() {
Time[] inputs = {
new Time(14, 'b'), new Time(18, 'a'),
new Time(12, 'b'), new Time(15, 'a'),
new Time(15, 'b'), new Time(20, 'a'),
new Time(20, 'b'), new Time(30, 'a'),
new Time(5, 'b'), new Time(14, 'a')
};
int answer1 = solution1(inputs);
assertEquals(2, answer1);
}
}최대 수입 스케쥴(PriorityQueue)
현수는 유명한 강연자이다. N개의 기업에서 강연 요청을 해왔다.
각 기업은 D일 안에 와서 강연을 해주면 M만큼의 강연료를 주기로 했다.
각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야한다.
단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.
- 입력설명
첫 번째 줄에 자연수 N(1<=N<=10,000)이 주어지고, 다음 N개의 줄에 M(1<=M<=10,000)과 D(1<=D<=10,000)가 차례로 주어진다. - 출력설명
첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다. - 입력예제 1
6
50 2
20 1
40 2
60 3
30 3
30 1 - 출력예제 1
150 - 풀이
마감일 기준으로 내림차순으로 정렬하고 금액 기준으로 내림차순한다.
public class MaxIncomeSchedule {
static class Speech implements Comparable<Speech> {
int cost;
int deadline;
public Speech (int cost, int deadline) {
this.cost = cost;
this.deadline = deadline;
}
@Override
public int compareTo(Speech speech) {
return this.deadline == speech.deadline
? speech.cost - this.cost
: speech.deadline - this.deadline;
}
}
public int solution1(Speech[] inputs) {
Arrays.sort(inputs);
Queue<Integer> queueOfCost = new PriorityQueue<>(reverseOrder());
int maxDeadline = Arrays.stream(inputs)
.mapToInt(i -> i.deadline)
.max()
.orElse(0);
int answer = 0;
int outerJ = 0;
for (int i = maxDeadline; i >= 1; i--) {
for (; outerJ < 6; outerJ++) {
if (inputs[outerJ].deadline < i) {
break;
}
queueOfCost.offer(inputs[outerJ].cost);
}
if (!queueOfCost.isEmpty()) {
answer += queueOfCost.poll();
}
}
return answer;
}
@Test
@DisplayName("최대 수입 스케쥴")
public void main() {
Speech[] inputs1 = {
new Speech(50, 2), new Speech(20, 1), new Speech(40, 2),
new Speech(60, 3), new Speech(30, 3), new Speech(30, 1)
};
int answer1 = solution1(inputs1);
assertEquals(150, answer1);
}
}다익스트라(Dijkstra) 알고리즘
아래의 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하는 프로그램을 작성하세요.
경로가 없으면 Impossible를 출력한다.
- 입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보와 거리비용이 주어진다. - 출력설명
1번 정점에서 각 정점으로 가는 최소비용을 2번 정점부터 차례대로 출력하세요. - 입력예제 1
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 - 출력예제 1
2 11
3 4
4 9
5 14
6 impossible - 풀이
다익스트라 알고리즘을 적용하기 위해서는 가중치에 음수가 있어서는 안된다.
PriorityQueue를 사용하지 않은 경우의 시간 복잡도는 O(n * n)이 된다.
PriorityQueue의 시간 복잡도는 logn이므로 시간 복잡도는 = O(n * logn)이 된다.
public class Dijkstra {
static class Edge implements Comparable<Edge> {
int vertex;
int cost;
public Edge(int vertex, int cost) {
this.vertex = vertex;
this.cost = cost;
}
@Override
public int compareTo(Edge edge) {
return this.cost - edge.cost;
}
}
private static final int NUMBERS = 6;
private static final int[] DISTANCES = new int[NUMBERS + 1];
private static final ArrayList<ArrayList<Edge>> GRAPH = new ArrayList<>();
public void solution1(int v) {
Queue<Edge> queueOfEdge = new PriorityQueue<>();
queueOfEdge.offer(new Edge(v, 0));
DISTANCES[0] = 0;
DISTANCES[v] = 0;
while (!queueOfEdge.isEmpty()) {
Edge currentEdge = queueOfEdge.poll();
int currentVertex = currentEdge.vertex;
int currentCost = currentEdge.cost;
if (currentCost > DISTANCES[currentVertex]) {
continue;
}
for (Edge edge : GRAPH.get(currentVertex)) {
if (DISTANCES[edge.vertex] > currentCost + edge.cost) {
DISTANCES[edge.vertex] = currentCost + edge.cost;
queueOfEdge.offer(new Edge(edge.vertex, currentCost + edge.cost));
}
}
}
}
@Test
@DisplayName("다익스트라 알고리즘")
public void main() {
for (int i = 0; i <= 9; i++) {
GRAPH.add(new ArrayList<>());
}
Arrays.fill(DISTANCES, Integer.MAX_VALUE);
GRAPH.get(1).add(new Edge(2, 12));
GRAPH.get(1).add(new Edge(3, 4));
GRAPH.get(2).add(new Edge(1, 2));
GRAPH.get(2).add(new Edge(3, 5));
GRAPH.get(2).add(new Edge(5, 5));
GRAPH.get(3).add(new Edge(4, 5));
GRAPH.get(4).add(new Edge(2, 2));
GRAPH.get(4).add(new Edge(5, 5));
GRAPH.get(6).add(new Edge(4, 5));
solution1(1);
int[] expectedAnswer = {0, 0, 11, 4, 9, 14, Integer.MAX_VALUE};
assertArrayEquals(expectedAnswer, DISTANCES);
}
}친구인가? (Disjoint-Set: Union & Find)
오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다.
모든 학생은 1부터 N까지 번호가 부여되어있고, 현수에게는 각각 두명의 학생은 친구관계가 번호로 표현된 숫자쌍이 주어진다.
만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구,
3번 학생과 4번 학생이 친구이다. 그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다.
학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램을 작성하세요.
두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다.
- 입력설명
첫 번째 줄에 반 학생수인 자연수 N(1<=N<=1,000)과 숫자쌍의 개수인 M(1<=M<=3,000)이 주어지고,
다음 M개의 줄에 걸쳐 숫자쌍이 주어진다.
마지막 줄에는 두 학생이 친구인지 확인하는 숫자쌍이 주어진다. - 출력설명
첫 번째 줄에 “YES"또는 "NO"를 출력한다. - 입력예제 1
9 7
1 2
2 3
3 4
1 5
6 7
7 8
8 9
3 8 - 출력예제 1
NO - 풀이
Disjoint-Set: 서로소 집합. 서로 공통되는 부분이 없는 집합
친구들 연결관계를 그래프로 이해하고 연결관계가 다른 친구는 서로소 그래프라고 판단한다.
find 메서드와 union 메서드는 형태를 암기해서 사용하자.
return unionAndFind[vertex] = find(unionAndFind[vertex])
코드를 통해 압축을 이해하고 시간복잡도를 줄인다.
public class IsFriend {
private int[] unionAndFind;
private int find(int vertex) {
if (vertex == unionAndFind[vertex]) {
return vertex;
} else {
return unionAndFind[vertex] = find(unionAndFind[vertex]);
}
}
private void union(int studentA, int studentB) {
int studentAGroup = find(studentA);
int studentBGroup = find(studentB);
if (studentAGroup != studentBGroup) {
unionAndFind[studentAGroup] = studentBGroup;
}
}
public String solution1(int[][] students, int targetA, int targetB) {
for (int[] student : students) {
union(student[0], student[1]);
}
int targetAGroup = find(targetA);
int targetBGroup = find(targetB);
return targetAGroup == targetBGroup ? "YES" : "NO";
}
@Test
@DisplayName("친구인가 (Disjoint-Set: Union & Find)")
public void main() {
int studentCount = 9;
int[][] students1 = {
{1, 2}, {2, 3}, {3, 4}, {1, 5},
{6, 7}, {7, 8}, {8, 9}
};
unionAndFind = new int[studentCount + 1];
for (int i = 0; i < unionAndFind.length; i++) {
unionAndFind[i] = i;
}
String expectedAnswer1 = "NO";
String answer1 = solution1(students1, 3, 8);
assertEquals(expectedAnswer1, answer1);
}
}원더랜드(최소스패닝트리)
원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.
원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.
아래의 그림은 그 한 예를 설명하는 그림이다.
위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시 를 연결하는 방법을 찾아낸 것이다.
- 입력설명
첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.
다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.
이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다. - 출력설명
모든 도시를 연결하면서 드는 최소비용을 출려한다. - 입력예제 1
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 - 출력예제 1
196 - 풀이(크루스칼(kruskal)을 활용)
최소스패닝트리: 크루스칼 = 어떠한 그래프에서 모든 Vertex가 연결되어 있는 그래프를 추출해내는 것
그래프와 트리의 차이는 그래프는 자기자신으로 돌아올 수 있는 회로가 존재하고
트리는 자기 자신으로 돌아올 수 있는 회로가 존재하지 않는다.
크루스칼 알고리즘은 회로가 되어서는 안된다.
트리에서 간선의 수 = 정점의 수 + 1이 된다.
트리구조가 만들어지고나면 이후에 더 이상의 간선이 추가되지 않을 것이므로 중간에 끊어줄 수 있다. (시간복잡도 감소)
만든 간선의 수를 카운트하고 만들어진 간선의 수가 정점의 수 + 1이라면 로직을 타지않고 흘려보내도록 한다. - 풀이(프림(prim)을 활용)
가중치가 있는 무방향 인접리스트를 만들어야한다.
정점을 확인하는 1차원 체크배열이 필요하다.
우선순위큐가 필요한데 우선순위큐에는 선택한 정점에서 갈 수 있는 정점들의 비용이 들어간다.
크루스칼(kruskal)을 활용한 풀이
public class WonderLandKruskal {
private int[] unionAndFind;
private int count = 0;
private int cost = 0;
private final int vertexCount = 9;
static class Edge implements Comparable<Edge> {
int cityA;
int cityB;
int cost;
public Edge(int cityA, int cityB, int cost) {
this.cityA = cityA;
this.cityB = cityB;
this.cost = cost;
}
@Override
public int compareTo(Edge edge) {
return this.cost - edge.cost;
}
}
private int find(int vertex) {
if (vertex == unionAndFind[vertex]) {
return vertex;
} else {
return unionAndFind[vertex] = find(unionAndFind[vertex]);
}
}
private void union(Edge edge) {
if (count >= vertexCount + 1) {
return;
}
int cityAGroup = find(edge.cityA);
int cityBGroup = find(edge.cityB);
if (cityAGroup != cityBGroup) {
count++;
cost += edge.cost;
unionAndFind[cityAGroup] = cityBGroup;
}
}
public void solution1(List<Edge> edges) {
Collections.sort(edges);
edges.forEach(this::union);
}
@Test
@DisplayName("원더랜드 (최소스패닝트리: 크루스칼, Union & Find 활용)")
public void main() {
List<Edge> edges = new ArrayList<>(List.of(
new Edge(1, 2, 12),
new Edge(1, 9, 25),
new Edge(2, 3, 10),
new Edge(2, 8, 17),
new Edge(2, 9, 8),
new Edge(3, 4, 18),
new Edge(3, 7, 55),
new Edge(4, 5, 44),
new Edge(5, 6, 60),
new Edge(5, 7, 38),
new Edge(7, 8, 35),
new Edge(8, 9, 15)
));
unionAndFind = new int[vertexCount + 1];
for (int i = 0; i <= vertexCount; i++) {
unionAndFind[i] = i;
}
solution1(edges);
assertEquals(196, cost);
}
}**프림(Prim)을 활용한 풀이
public class WonderLandPrim {
int[] checkArray;
static class Edge implements Comparable<Edge> {
int vertex;
int cost;
public Edge(int vertex, int cost) {
this.vertex = vertex;
this.cost = cost;
}
@Override
public int compareTo(Edge edge) {
return this.cost - edge.cost;
}
}
public int solution1(ArrayList<ArrayList<Edge>> graph) {
int answer = 0;
Queue<Edge> queueOfEdge = new PriorityQueue<>();
queueOfEdge.add(new Edge(1, 0));
while (!queueOfEdge.isEmpty()) {
Edge currentEdge = queueOfEdge.poll();
int currentVertex = currentEdge.vertex;
if (checkArray[currentVertex] == 0) {
checkArray[currentVertex] = 1;
answer += currentEdge.cost;
for (Edge edge : graph.get(currentVertex)) {
if (checkArray[edge.vertex] == 0) {
queueOfEdge.offer(edge);
}
}
}
}
return answer;
}
@Test
@DisplayName("원더랜드 (최소스패닝트리: 프림, PriorityQueue)")
public void main() {
int edgeCount = 9;
checkArray = new int[edgeCount + 1];
ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
for (int i = 0; i <= edgeCount; i++) {
graph.add(new ArrayList<>());
}
graph.get(1).add(new Edge(2, 12));
graph.get(2).add(new Edge(1, 12));
graph.get(1).add(new Edge(9, 25));
graph.get(9).add(new Edge(1, 25));
graph.get(2).add(new Edge(3, 10));
graph.get(3).add(new Edge(2, 10));
graph.get(2).add(new Edge(8, 17));
graph.get(8).add(new Edge(2, 17));
graph.get(2).add(new Edge(9, 8));
graph.get(9).add(new Edge(2, 8));
graph.get(3).add(new Edge(4, 18));
graph.get(4).add(new Edge(3, 18));
graph.get(3).add(new Edge(7, 55));
graph.get(7).add(new Edge(3, 55));
graph.get(4).add(new Edge(5, 44));
graph.get(5).add(new Edge(4, 44));
graph.get(5).add(new Edge(6, 60));
graph.get(6).add(new Edge(5, 60));
graph.get(5).add(new Edge(7, 38));
graph.get(7).add(new Edge(5, 38));
graph.get(7).add(new Edge(8, 35));
graph.get(8).add(new Edge(7, 35));
graph.get(8).add(new Edge(9, 15));
graph.get(9).add(new Edge(8, 15));
int expectedAnswer1 = 196;
int answer1 = solution1(graph);
assertEquals(expectedAnswer1, answer1);
}
}'Algorithm' 카테고리의 다른 글
| [Algorithm] Dynamic Programming (0) | 2022.03.04 |
|---|---|
| [Algorithm] BFS 활용 (0) | 2022.03.01 |
| [Algorithm] DFS 활용 (0) | 2022.03.01 |
| [Algorithm] Graph (0) | 2022.02.28 |
| [Algorithm] DFS 원리 (0) | 2022.02.28 |
