문제 출처 : https://softeer.ai/practice/6252
대규모 머신 러닝에서는 여러 컴퓨터를 하나의 클러스터로 묶어 계산을 수행하는 경우가 많다. 병렬 컴퓨팅 파워가 늘어나면 훨씬 더 거대한 데이터도 실용적으로 사용할 수 있게 된다. 클라우드 컴퓨팅을 이용하는 기업도 많지만, 개인정보와 보안, 네트워킹, 비용 등의 문제로 직접 클러스터를 구축하는 경우도 많다.
현지도 이러한 머신 러닝용 클러스터를 관리하는 역할을 맡고 있다. 클러스터의 성능은 컴퓨터의 수가 많아질 수록, 각각의 성능이 올라갈 수록 향상된다. 그런데 어느 날 협업 중인 몇몇 연구실에서 클러스터의 성능을 업그레이드해 달라는 요청을 보내 왔다. 이들은 특히 클러스터를 이루는 각각의 컴퓨터 중 성능이 가장 낮은 컴퓨터의 성능이 병목이 된다고 알려 왔다.
이 클러스터에는 N대의 컴퓨터가 있으며, 각각의 성능은 ai라는 정수로 평가할 수 있다. 현지는 각각의 컴퓨터에 비용을 들여 업그레이드를 진행할 수 있다. 성능을 d만큼 향상시키는 데에 드는 비용은 d2원이다. (단, d는 자연수이다.)
업그레이드를 하지 않는 컴퓨터가 있어도 되지만, 한 컴퓨터에 두 번 이상 업그레이드를 수행할 수는 없다.
업그레이드를 위한 예산이 B원 책정되어 있다. 현지의 목표는 B원 이하의 총 비용으로 업그레이드를 수행하여, 성능이 가장 낮은 컴퓨터의 성능을 최대화하는 것이 목표이다. 이 최선의 최저성능을 계산하는 프로그램을 작성하시오.
제약조건
1≤N≤10^5인 정수
1≤ai≤10^9인 정수
1≤B≤10^18인 정수
B 값이 매우 크므로 long으로 선언함에 유의하자.
풀이
오답 리마인드
N이 10만에 B가 매우 크므로 문제에서 주어진 것 처럼 하나씩 탐색하는 것은 무조건 시간초과로 계산하였다.
1번째 풀이
- PriorityQueue에 입력값들을 넣기 (O(NlogN))
- pq에서 하나씩 꺼내면서 최저 값과 비교 후 cost 계산. ArrayList에 지나온 pq의 값을 넣어주면서 다음 최저 값 비교 시 해당 list 탐색 후 pq로 적은 수를 탐색할 수 있도록 함.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
long B = Long.parseLong(st.nextToken());
PriorityQueue<Integer> pq = new PriorityQueue<>();
st = new StringTokenizer(br.readLine());
int minPerformance = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
int ai = Integer.parseInt(st.nextToken());
minPerformance = Math.min(minPerformance, ai);
pq.offer(ai);
}
boolean flag = true;
ArrayList<Integer> preList = new ArrayList<>();
while (flag) {
minPerformance++;
long cost = 0;
for (int i = 0; i < preList.size(); i++) {
int preN = preList.get(i);
cost += Math.pow(minPerformance - preN, 2);
if (cost > B) {
flag = false;
break;
}
}
if (!flag) break;
while (!pq.isEmpty() && pq.peek() < minPerformance) {
int num = pq.poll();
cost += Math.pow(minPerformance - num, 2);
if (cost > B) {
flag = false;
break;
}
preList.add(num);
}
}
System.out.print(minPerformance-1);
br.close();
}
}결과
subtask1, 2에서는 정답으로 처리되었지만 subtask3에서 대부분 시간초과가 발생했다.
-> 음, 최저 값(정답)을 서칭할 때 +1씩하는 것이 아닌 다음 최저 값으로 갱신하면서 cost로 해당 최저 값이 불가할 시 두 인덱스 사이를 탐색한다면 시간을 줄일 수 있지 않을까 ? 생각하였다.
2번째 풀이
1) 풀이에서 얻은 방법대로 가장 정답에 근접한 인덱스를 찾고 해당 인덱스 사이를 +1로 탐색하며, 찾자.
-> 설계과정에서 최댓값을 설정하면 서칭이 빠를 듯 했지만 최댓값 설정이 뚜렷하게 생각나지 않아 설계로 들어감
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
long B = Long.parseLong(st.nextToken());
int[] performance = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) performance[i] = Integer.parseInt(st.nextToken());
Arrays.sort(performance);
int minPer = performance[0];
int minIdx = 0;
boolean find = false;
// 다음 인표치로 잡고 가능성 계산
while (true) {
minIdx++;
if (minIdx == N) break;
minPer = performance[minIdx];
long cost = 0;
for (int i = 0; i < minIdx; i++) {
cost += Math.pow(minPer - performance[i], 2);
if (cost > B) {
find = true;
break;
}
}
if (find) break;
}
// 찾은 인덱스의 -1부터 값을 키우면서 가능한 최저 성능 찾기
minPer = performance[minIdx-1];
boolean flag = true;
while (flag) {
minPer++;
long cost = 0;
for (int i = 0; i < minIdx; i++) {
cost += Math.pow(minPer - performance[i], 2);
if (cost > B) {
flag = false;
break;
}
}
}
System.out.println(minPer-1);
br.close();
}
}결과
subtask1, 2는 정답. 풀이 1보다는 subtask3에서 시간을 많이 줄였으나 역시 두 인덱스 사이의 값 차이가 크다면 시간복잡도를 해결하지 못하는 문제를 직면
-> 음... 빠르게 값을 찾는다 ? 이진탐색. 최대값 설정이 가능한가를 다시 고민해봄. 10^9의 제곱이 10^18이니깐 최대로 증가할 수 있는 값은 10^9. 따라서 최대 성능은 2*10^9.
3번째 풀이 (정답)
최저값 1
최대값 2 * 10^9
-> 이진탐색, 가능여부판단하며 정답값 도출
import java.io.*;
import java.util.*;
public class Main {
static int[] performance;
static int N;
static long B;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
B = Long.parseLong(st.nextToken());
performance = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) performance[i] = Integer.parseInt(st.nextToken());
Arrays.sort(performance);
long low = 1;
long high = 2 * 1_000_000_000;
while (low < high) {
long mid = (low + high+1) / 2;
if (sol(mid)) low = mid;
else high = mid - 1;
}
System.out.print(low);
br.close();
}
static boolean sol(long mid) {
long cost = 0;
for (int i = 0; i < N; i++) {
if (performance[i] >= mid) return true;
cost += Math.pow(mid-performance[i], 2);
if (cost > B) {
return false;
};
}
return true;
}
}결과
정답.
리뷰
문제를 읽고, 그래프 알고리즘을 다 제외하고 dp랑 그리디를 생각하였다. 하지만 이 문제는 두 가지 모두 아니므로 수학적 사고력을 요하는 문제라고 생각해서 어떻게 시간을 줄일지만 생각하였다. but, 이진탐색으로 서칭을 줄이는 문제였다. 다음부터는 어떤 값을 찾아서 결과를 도출해야한다면 이진탐색을 떠올려야겠다.
잘 보고 갑니다 ㅎㅎ