[▲][Softeer][level3][21년 재직자 대회 예선] 로드 밸런서 트래픽 예측 - 파이썬(Python)

 

https://softeer.ai/practice/info.do?idx=1&eid=629&sw_prbl_sbms_sn=145222 

Softeer

 

문제

자율주행 기술은 현대 컴퓨팅의 여러 최첨단 기술에 의존하지만, 이것이 가능하게 하려면 자동차에서 할 수 없는 복잡한 계산과 실시간 도로 정보 확인 등을 중앙 서버에서 빠르고 신속하게 처리할 수 있어야 한다. 이를 위해서 흔히 사용되는 방법은 요청(request)을 처리하는 많은 워커 노드(worker node)들을 두고, 로드 밸런서(load balancer)가 이들 워커 노드에 트래픽을 적절히 분산시키는 것이다. 즉 쉽게 설명하자면, 요청(request)이 들어오면 로드 밸런서가 워커 노드에 적절히 분배 해준다고 생각하면 된다. 

현재 총 N개의 서버가 있다. 로드 밸런서와 워커 노드 모두 서버라 지칭하며, 하나의 서버가 로드 밸런서이면서 동시에 워커 노드일 수는 없다. i (1 ≤ i ≤ N)번째 서버가 로드 밸런서라면 중복을 포함하여 ri개 서버로 트래픽을 분산한다. ri = 0이면 i번째 서버는 워커 노드로, 요청을 직접적으로 처리한다. ri ＞ 0이라면, i번째 서버는 로드 밸런서로, 아래와 같은 라운드-로빈(Round-Robin) 방식으로 트래픽을 분산한다.

각각의 로드 밸런서에는 정수형 변수 xi가 있다. 처음에 xi = 1이다. 로드 밸런서로 요청이 하나 들어오면, pi, xi번 서버로 트래픽을 전달하고, xi의 값을 (xi mod ri)+1로 바꾼다. 1번 서버는 루트 로드 밸런서로, 모든 요청은 루트 로드 밸런서로만 들어온다. 주어진 트래픽 분산 규칙은 효율적인 분산이 가능하도록 아래 두 조건을 만족한다. 트래픽이 같은 로드 밸런서를 여러 번 거치지 않도록, i → pi, j 간선들로 구성된 그래프에서 사이클이 존재하지 않는다. 1번 서버에 무한히 많은 요청을 보낸다면 모든 서버로 요청이 적어도 1개 이상은 전달된다.

총 K개의 요청이 들어왔다고 할 때, 각 서버로 들어오는 요청의 개수가 몇 개인지를 구하는 프로그램을 작성하라.

 

 

 

로드밸런서의 구조는 아래와 같다.

6개의 요청이 아래와 같이 전달된다.

 

 

 

 

 

하루 종일 고민하는데 안풀렸고,,

다음날 다시 풀어보다가 답이 없어서

 

결국 알고선생님의 풀이를 참고했다 ㅠㅠ

 

https://softeer.ai/class/algotutor/detail.do?id=81 

Softeer

 

 

위상정렬 개념을 까먹은 채로 문제에 도전했어서 당연히 못풀수밖에 없었다. 

위상정렬을 이용해야한다고 해서

먼저 위상정렬을 공부했다.

 

https://jie0025.tistory.com/463

[알고리즘] 위상정렬 알고리즘 (Topology Sort) 공부

 

 

---

 

💻 풀이 참고 후 내가 쓴 정답코드

 

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int,input().split())

graph = [[] for _ in range(n+1)] #관계
serverIn = [0] * (n+1) #진입차수


#01) 관계 생성 및 진입차수 저장
for i in range(1,n+1):

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

    if tmpInfo[0] == 0: #worker
        graph[i].append(0)
    else: #loadbalancer
        graph[i]+=tmpInfo[1:]
        for child in tmpInfo[1:]:
            serverIn[child]+=1

serverIn[0] = -1
#print("serverIn",serverIn)
#print("graph", graph)



#02) 위상 정렬을 이용한 순서만들기
#진입차수가 0인 노드는 root밖에 없음 따라서, queue에 1만 넣어주고 위상정렬을 하면 된다. 

serverSequence = []

def topologySort():
    
    queue = deque()
    queue.append(1)

    while queue:
        
        now = queue.popleft()
        serverSequence.append(now)

        children = graph[now]
        
        for child in children:
            serverIn[child]-=1
            if serverIn[child] == 0:
                queue.append(child)

    #무조건 위상 정렬의 조건이므로 체크 안해줘도 된다. 


topologySort()
#print(serverSequence)

#03) k 번의 요청 처리
count = [0] * (n+1)
count[1] = k

for server in serverSequence: #노드의 개수만큼 반복 -- 
    request = count[server]

    childrenNum = len(graph[server])
    if childrenNum == 0:
        continue
    
    quotient = request // childrenNum
    reminder = request % childrenNum
    
    children = graph[server]
    for child in children :
        count[child] += quotient
    
    for j in range(reminder):
        child = graph[server][j]
        count[child] += 1


#04) 정답 출력
for i in range(1,n+1):
    print(count[i], end =" ")

 

 

 

 

흠 다시 풀어봐야지...