[Softeer] 슈퍼컴퓨터 클러스터

hyeop29·2023년 3월 5일
0

문제

대규모 머신 러닝에서는 여러 컴퓨터를 하나의 클러스터로 묶어 계산을 수행하는 경우가 많다. 병렬 컴퓨팅 파워가 늘어나면 훨씬 더 거대한 데이터도 실용적으로 사용할 수 있게 된다. 클라우드 컴퓨팅을 이용하는 기업도 많지만, 개인정보와 보안, 네트워킹, 비용 등의 문제로 직접 클러스터를 구축하는 경우도 많다.

현지도 이러한 머신 러닝용 클러스터를 관리하는 역할을 맡고 있다. 클러스터의 성능은 컴퓨터의 수가 많아질 수록, 각각의 성능이 올라갈 수록 향상된다. 그런데 어느 날 협업 중인 몇몇 연구실에서 클러스터의 성능을 업그레이드해 달라는 요청을 보내 왔다. 이들은 특히 클러스터를 이루는 각각의 컴퓨터 중 성능이 가장 낮은 컴퓨터의 성능이 병목이 된다고 알려 왔다.

이 클러스터에는 N대의 컴퓨터가 있으며, 각각의 성능은 ai라는 정수로 평가할 수 있다. 현지는 각각의 컴퓨터에 비용을 들여 업그레이드를 진행할 수 있다. 성능을 d만큼 향상시키는 데에 드는 비용은 d2원이다. (단, d는 자연수이다.)

업그레이드를 하지 않는 컴퓨터가 있어도 되지만, 한 컴퓨터에 두 번 이상 업그레이드를 수행할 수는 없다.

업그레이드를 위한 예산이 B원 책정되어 있다. 현지의 목표는 B원 이하의 총 비용으로 업그레이드를 수행하여, 성능이 가장 낮은 컴퓨터의 성능을 최대화하는 것이 목표이다. 이 최선의 최저성능을 계산하는 프로그램을 작성하시오.

제약조건

1≤N≤10^5인 정수
1≤ai≤10^9인 정수
1≤B≤10^18인 정수

입력형식

첫째 줄에 컴퓨터의 수와 예산을 나타내는 정수 N과 B가 공백을 사이에 두고 주어진다.
둘째 줄에 각 컴퓨터의 성능을 나타내는 N개의 정수 a1, a2, ..., an이 공백을 사이에 두고 주어진다.

B의 범위가 매우 넓어, 사용하는 프로그래밍 언어에 따라 64비트 정수형을 사용해야 할 수 있음에 유의하시오.

출력형식

첫째 줄에 예산을 효율적으로 사용했을 때, 성능이 가장 낮은 컴퓨터의 성능으로 가능한 최댓값을 출력하시오.

입력예제 1

4 10
5 5 6 1

출력예제 1

4
네 번째 컴퓨터의 성능을 1에서 4로 업그레이드 하는 데 드는 비용은 32=9원이다. 이 경우, 가장 낮은 성능의 컴퓨터는 4의 성능을 가지게 되며, 가장 낮은 성능으로 가능한 최대값은 4가 됨을 알 수 있다.

입력예제 2

10 10
5 3 9 8 4 3 1 8 6 3

출력예제 2

3

일곱 번째 컴퓨터의 성능을 1에서 3으로 업그레이드 하는 데 드는 비용은 22=4원이다. 이 경우, 가장 낮은 성능의 컴퓨터는 3의 성능을 가지게 된다.

가장 낮은 성능이 4가 되기 위해서는 원래 3의 성능을 가지고 있었던 두 번째, 여섯 번째, 그리고 열 번째 컴퓨터를 향상시키는 데 드는 비용 12+12+12=3원과 일곱 번째 컴퓨터의 성능을 3이 아닌 4로 향상시키는 데 드는 비용 (4-1)2=9원, 총 12원이 들기 때문에 불가능하다.

나의 풀이

처음에 내가 가진 비용으로 가장 낮은 성능의 컴퓨터의 성능값을 계산할려고 했지만, 컴퓨터 수가 많아질 경우, 비용이 커질 경우를 생각하면 말도 안되는 생각이였다.

제한 시간도 5초인 것을 활용하여, 가장 낮은 성능의 컴퓨터의 성능값이 될 수 있는 모든 수를 넣어서 내가 가진 비용인 B가 넘지 않는 선에서 최대의 값을 찾으면 될 거 같다는 생각을 하고, 코드를 실행에 옮겼다.

우선 가장 낮은 성능의 컴퓨터의 성능값이 될 수 있는 수의 범위는
최소값은 내가 입력 받은 컴퓨터의 성능 중 가장 작은 값이고, 최대값은 내가 사용할 수 있는 비용의 루트값을 최소값에 더한 값이다.

필자는 효율을 높이기 위해 이진탐색을 사용했다. 이진탐색은 컴퓨터 N개의 성능을 나타내는 리스트에서 가장 낮은 성능의 컴퓨터의 성능값을 만들도록 비용을 계산 한 후(cal_fee 함수가 되겠다.) 이진탐색의 mid 값과 비교해서 이진탐색을 해나가도록 하였다.

앞서 구한 최소값과 최대값을 start, end로 넣고 이진탐색을 시작하고, 주의할점은 일반 이진탐색처럼 같은 값을 찾는게 아닌 최대한 비용을 쓰면서 성능이 가장 낮은 컴퓨터의 성능으로 가능한 최대값이 나오도록 해야한다, 경우에 따라 비용을 다 쓸 수도 있겠지만 아닌 경우를 생각해서 binarysearch 함수 temp 변수에 내가 가진 비용안에 성능을 찾은 경우의 해당 성능값을 갱신해주었다.

import sys
import math

N, B = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
result = 0

max_a = int(a[N - 1] + pow(B,0.5))

def cal_fee(mid, a_list) :
    fee = 0
    for i in a_list :
        if mid > i :
            fee += pow(mid - i, 2)
    return fee

def binarysearch(start, end, a_list, temp) :
    if start > end :
        return temp
    mid = (start + end) // 2
    # print("mid : {}, start : {}, end : {}, cal : {}".format(mid, start, end, cal_fee(mid, a_list)))
    if(cal_fee(mid, a_list) <= B) :
        temp = mid
        return binarysearch(mid + 1, end, a_list, temp)
    else :
        return binarysearch(start, mid - 1, a_list, temp)

result = binarysearch(a[0], max_a, a, 0)

print(result)

생각하는데 시간이 걸린 만큼 다시 한번 더 풀어봐야겠다.

profile
hyeop29

0개의 댓글