소프티어 4차 인증평가 문제 풀이

  • 2022/09/25
  • 5-minute read

Problem

Table of Contents

슈퍼컴퓨터 클러스터 설명

  • 문제가 꽤 깁니다…만 아무튼 요약하자면 다음과 같습니다.
  • 제한된 비용을 이용하여, 여러 대의 PC를 업그레이드한다.
  • 최종 업그레이드 시, 가장 성능이 낮은 PC의 성능을 최대화한다.
  • 결과물은 성능이 가장 낮은 컴퓨터의 최대값을 출력
  • 성능 업그레이드는 PC당 1번만 가능하며, 업그레이드하는 성능의 제곱만큼의 비용이 든다.
  • 예를 들어, 1에서 4로 업그레이드한다면, 3의 제곱으로 9만큼 비용이 든다.

슈퍼컴퓨터 클러스터 풀이

  • 입력은 두 줄로 입력
  • 첫 번째 줄 입력은 PC의 개수, 전체 업그레이드 예산
  • 두 번째 줄 입력은 각 PC의 성능
  • 입력이 꽤 많을 수 있으므로, sys.stdin.readline을 적절히 활용하는 것이 좋음.
  • 각 PC의 성능을 A까지 업그레이드 한다면, 다음과 같이 코드를 작성할 수 있습니다.
cost = 0
for i in PCs:
    if i < A:
        cost += ((A - i) ** 2)
  • 해당 문제의 시간 제한은 Python기준 5초이며, 입력으로 들어오는 PC의 개수는 최대 $10^5$입니다.
  • Python은 대략 1초에 2천만번의 연산이 가능하므로, 최대 연산 가능 횟수는 약 1억번입니다.
  • PC의 개수는 최대 $10^5$이며, 각 PC의 성능의 범위는 최대 $10^9$이며, 예산 범위는 $10^{18}$입니다.
  • 1대의 PC에 최대 예산인 $10^{18}$을 사용한다면, 업그레이드 가능한 성능은 $10^9$입니다.
  • PC가 1대이고, 처음부터 성능이 최대인 $10^9$이었다면, 최대 성능은 $2 \times 10^9$이 됩니다.
  • 따라서, 탐색 범위(RANGE)는 $1$ ~ $2 \times 10^9$입니다.
  • 모든 PC에 대해, 모든 성능의 범위를 탐색하며, 업그레이드 가능한 최소 값을 찾는다면, $O(N \times RANGE)$이므로, $O(10^{14})$이 되어 시간 범위를 초과합니다.
  • $O(N \times log{RANGE})$이라면, 약 $O(10^5 \times 31)$이므로, 시간 범위 안에 가능합니다.
  • 이 문제는 모든 PC를 살펴서 업그레이드를 진행($O(N)$)하면서, Binary Search 방식($O(log{RANGE})$)을 통해, 최대 업그레이드 가능한 성능을 탐색하는 문제입니다.
  • 코드는 다음과 같이 한 번 작성해봤으며, Softeer에 제출하여 정답임을 확인하였습니다.
import sys

input = sys.stdin.readline

N, B = map(int, input().split()) # 컴퓨터의 대수, 업그레이드 예산

PCs = list(map(int, input().split())) # 각 PC의 성능

left = 1 
right = 2000000000

while (left + 1) < right: # 무한 루프에 빠지지 않도록, 1보다 적게 차이나면 멈추도록 설정
    cost = 0
    center = (left + right) // 2 # 무조건 버려짐
    for i in PCs:
        if i < center:
            cost += (center - i) ** 2
            if cost > B:
                right = center - 1
                break
    else:
        left = center

best_PC = 0
for center in range(left, right + 1): 
    # left or right 중, 최적이 어떤 것인지 한 번 더 확인
    cost = 0
    for i in PCs:
        if i < center:
            cost += (center - i) ** 2
            
    if cost <= B:
        best_PC = center

print(best_PC)

통근버스 출발 순서 검증하기 설명

  • 이 문제도 상당히 깁니다만… 요약하자면 다음과 같습니다.
  • 통근버스 정렬을 스택을 이용한 스택 정렬로 모델링할 수 있는데,
  • 스택 정렬은 정렬이 불가능한 경우가 있다는 것
  • 입력된 버스들 중, 정렬이 불가능한 경우의 수가 몇 가지인지 찾는 문제
  • Python 기준 시간 제한은 2초이며, 메모리는 여유롭다.
  • 통근버스의 수는 최대 5,000대까지 주어진다. (버스 번호의 중복 X)
  • 총 버스의 수가 먼저 주어지고, 그 다음 줄에 버스의 순서가 주어진다.

통근버스 출발 순서 검증하기 풀이

  • 우선 연산 횟수를 계산해보면 2초의 시간이므로, 최대 40,000,000번의 연산이 가능하다.
  • N개 중 3개를 선택하는 경우의 수는 총 $N!/(3! \times (N - 3)!)$이므로, 대충 계산만해도 $O(N^3)$이므로, 시간 초과가 뜰 것임을 예상할 수 있다.
  • 대략 $O(N^2)$ 이하가 되면, 시간 초과 없이 가능할 것으로 예측 가능하다.
  • 해당 문제에서 찾아야하는 조건은 $i < j < k$를 만족하면서, $a_i < a_j$ & $a_i > a_k$인 값을 찾는 것
  • 임의의 자연수 X에 대해, arr[X][j]를 j보다 뒤에 있는 버스 중, X보다 값이 작은 것의 개수라고 정의한다면,
  • j = N일 때는 arr[X][N] = 0이며, j = N - 1이면, arr[X][N - 1] = (a[N - 1] < X ? 1 : 0)이 됩니다.
  • 지속해서 반복하면, arr[X][N - 2] = arr[X][N - 1] + (a[N - 2] < X ? 1 : 0)이 되며, 일반화하면, arr[X][j] = arr[X][j + 1] + (arr[X][j] < X ? 1 : 0)이 됩니다.
  • j의 가능한 범위는 1 ~ N - 1까지 사용이 가능하며, 이를 이용하면, $O(N^2)$으로 계산이 가능하다.
  • 이렇게 미리, 특정 값보다 작은 개수를 미리 계산한 후, 다시 i, j를 i < j & a[i] < a[j]인 경우에 a[a[i]][j]를 더해주면 시간 범위 안에 정답을 구할 수 있다.
  • 코드는 다음과 같이 작성해보았습니다.
import sys

input = sys.stdin.readline

N = int(input())

buses = list(map(int, input().split()))

arr = [[0] * (N + 1) for _ in range(N + 1)]

for j in range(N - 1, -1, -1):
    for X in range(1, N + 1):
        if buses[j] < X:
            arr[X][j] = arr[X][j + 1] + 1
        else:
            arr[X][j] = arr[X][j + 1]

result = 0
for i in range(N):
    for j in range(i, N):
        if buses[i] < buses[j]:
            result += arr[buses[i]][j]
            
print(result)

Review

  • 도전하자는 의미로 도전했던 Softeer 정기 평가… 아주 쉽게 광탈하였다.
  • 슈퍼컴퓨터 문제는 문제 풀이를 어떤 식으로 하면 되는지에 대한 이해는 있었으나, 아직 Big-O에 대한 내용이 익숙하지 않아서, 어느 정도의 계산량이 시간을 초과하지 않는 지에 대한 내용을 몰랐던 것 같다.
  • 게다가 추가적으로 현대 모비스 코테가 상당히 쉬웠기에… 얕봤던 것도 있는듯하다.
  • 수확이라면, Python은 1초에 2천만번이 계산하능하니, 이를 이용해서 Big-O로 대략적인 방법을 예측할 수 있다는 것 정도?
  • 또한, 이진 탐색의 경우, 상황에 따라 경계 조건을 다르게 두어야한다는 점도 인상 깊었다.
  • 해당 문제의 경우, 예산 초과의 경우는 center - 1로 설정해도 문제가 되지 않지만, 예산 범위 내라고 해서 center + 1로 처리를 하면, 해당 center값이 최적 값인 경우도 있었으므로, 이를 주의해야한다.
  • 상황에 따라, 이진 탐색 시 while문의 조건과 left, right의 값의 변경에 주의하자.
  • 두 번째 문제는 상황을 3개를 골라서 경우를 살피는 경우를 2개와 2개로 나누어서 처리하는 방법을 이용하였다.
  • 특별한 알고리즘이 적용되는 것보다는 아이디어가 중요했던 것 같은데, 이 문제는 다시 나와도 틀릴 것 같다.
  • 정리하면서 모든 경우를 미리 계산하고 더하는 것이라는 사실을 이해하긴 했지만, 그렇게 쉽게 이해되지는 않았다.
  • 경우만 미리 잘 계산한다면, 결과가 나오는데는 그리 오래 걸리진 않았다.
  • 나름 알찼던 Softeer 평가였으며, 다음에 기회가 되면 또 한 번… 도전해보겠습니다 :D

comments