그리디

Computer Sci./Algorithms

[킥스타트] Google Kick Start 2020 Round F 문제 풀이

이번 포스팅에서는 킥스타트 2020 Round F에 대한 문제 풀이를 공유하고자 한다. 1. ATM Queue 나는 이 문제를 우선순위 큐를 가지고 풀었다. 배열에 담겨진 각각의 출금액을 A1, A2, A3, ... , An 이라고 했을 때 그 출금액의 인덱스(몇 번째에 출금을 하는지)와 1회 최대 출금액(X)으로 나눈 몫을 가지고 클래스를 만들어서 출금액 몫 오름차순, 그리고 몫이 같을 경우 인덱스 오름차순이 되게 클래스의 기준을 만들어서 우선순위 큐에 넣으면 자동으로 정렬이 되어서 출력된다. 시간복잡도는 O(NlogN) 2. Metal Hervest 이 문제는 그리디 알고리즘으로 풀었다. 추수 기간이 오버랩 되지 않는다고 해서(These time intervals do not overlap) 문제가 ..

Computer Sci./Algorithms

[킥스타트] Google Kick Start 2020 Round A 문제 풀이

지금까지 백준만 풀다가 올해 남은 기간동안에는 구글 킥스타트 문제들을 좀 풀어보기로 했다. 구글 킥스타트는 구글에서 매년 개최하는 알고리즘 대회이다. 전 세계의 수만명이 참가하여 코딩 실력을 겨룬다. 1년에 여러 차례 대회가 열리는데(2020년 기준 한 달에 한 번꼴) 매번 대회가 끝나면 등수가 공개되어서, 객관적인 나의 수준도 판단할 수 있다. 매년 조금씩 바뀌지만 올해는 각 라운드당 3시간동안 네 문제를 푸는 형식으로 진행이 되고 있다. 나는 올해 중반부터 시작했고, 처음이다보니 아직 문제를 막 잘 풀지는 못했다. 그래서 2020년에 출제된 기출문제를 하나씩 풀어보면서 연습하고 그 내용을 블로그에 정리해 보려고 한다. 총 4문제 중에 4번 문제는 못 풀었고, 1~3번 문제만 풀어서 이에 대한 간단한 ..

Computer Sci./Algorithms

백준 1202 / 보석 도둑 / 그리디, 우선순위 큐 / JAVA

오늘 살펴볼 문제는 백준 1202번 문제이다. https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 이 문제는 전형적인 그리디 알고리즘 문제이다. 각각의 주머니에 대해서 넣을 수 있는 최대 가격의 보석을 적절하게 넣어주면 풀 수 있는 문제이다. 처음에 내가 했던 접근은 다음과 같다. 보석을 1. 가격이 비싼 순으로 2. 같은 가격이면 무게가 가벼운 순으로 정렬되는 PriortyQueue를 만든다. 그리고 가방을 무게 순으로 오름차순으로 정렬한..

Computer Sci./Algorithms

백준 2109 / 그리디(Greedy) 알고리즘 / JAVA

오늘 설명할 문제는 백준 2109번 순회 강연이다. https://www.acmicpc.net/problem/2109 2109번: 순회강연 문제 한 저명한 학자에게 n(0≤n≤10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1≤d≤10,000)일 안에 와서 강연을 해 주면 p(1≤p≤10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다. 예를 들어 네 대학에서 제시한 www.acmicpc.net 전형적인 그리디 알고리즘 문제로, 이 알고리즘에 대한 이해가 있다면 어렵지 않게 풀 수..

DevOwen
'그리디' 태그의 글 목록