Load Balancing Problem

Load Balancing 이라는 개념은 앞으로 몇번 접하게 될 개념입니다. 컴퓨터분야에서뿐만 아니라 다른 분야 (예를 든다면 이삿짐 업체나, 택배업체, 우체국 등등..) 에서도 쓰입니다. Load Balancing은 역할분담을 가장 적당하고 고르게 하여 각각의 개체들이 부담을 적게 느끼고 전체 작업시간을 단축시킬수 있도록 해 줍니다. 간단한 LoadBalancingProblem 문제를 접하여보고 기회가 닿는다면 조금더 복잡한 종류의 문제를 풀어보는것도 좋을것 같습니다.
----

[edit]

출제자 ¶

IPSC, 임인택이 한글화하고 요구하는 입&출력 스펙을 변경함

- 원래 문제 링크

[edit]

Problem name : Load Balancing ¶

SuperComputer 사는 N 개의 CPU 로 이루어진 슈퍼컴퓨터를 제작하였다. 각각의 CPU는 1에서 N 까지 번호가 새겨져 있으며 각각 독립적인 작업을 수행한다. 새로운 작업이 생기면 무작위로 한개의 CPU 에 그 작업이 할당된다. 이럴 경우 어떤 CPU 에는 작업이 엄청 많고 다른 CPU 에는 할당된 작업이 적거나 아예 없는 상황이 발생하게 된다. 이럴경우 각 CPU 에 작업을 적당하게 분배하여야 하는데 각각의 재분배 작업은 N번 CPU가 1-N, 1-N CPU 에 각각 하나씩의 작업을 전달하는 것이다. 차근차근 살펴보면,

1번 CPU의 작업의수를 본다. 다른 CPU 에 비해 작업이 많으면 양옆의 CPU 중에 한곳으로한 작업을 전달해줄수 있는데 1번 CPU 의 왼쪽에는 CPU 가 없으므로 2번 CPU 에만 작업을 전달해 줄 수 있다.
2번 CPU 의 작업의 수를 본다. 만약 2 번 CPU 의 작업의 수가 많다고 생각되면 1번, 3번 CPU 로 작업을 전달 해 줄수 있다.
(...) N 번 CPU 를 본다. 작업을 전달해줘야 할 경우 N 번 CPU 의 오른쪽에는 CPU 가 없으므로, 왼쪽으로만 전달할 수 있다.
다시 1 번 CPU 를 본다.
.....
(이 과정을 모든 CPU 가 최고-최저<=1 이 될때까지 반복한다)
.....

[edit]

입력값 ¶

IPSC 에는 입력을 파일로 받도록 하였으나 여기서는 직접 사용자가 다음과 같은 형식으로 입력한다.

~cpp 
CPU 의 갯수
초기에 각 CPU 에 할당된 작업의 수..

예를 들어보면,

~cpp 
3
0 99 3

8
16 17 15 0 20 1 1 2

10
0 0 100 0 0 0 0 0 0 0

[edit]

출력값 ¶

작업의 이동 후 각각의 CPU 에 적당하게 작업이 분배되었는가?
작업의 이동 횟수는 얼마인가?
몇번 돌아보았는가? (1부터 N 까지 보았을때를 1 round 라고 한다)

[edit]

source ¶

해결자	개발시간	사용언어	Source
강양욱	.	Java	IPSCLoadBalancing-macare.zip
임인택	.	Java	LoadBalancingProblem/임인택 (그냥 예전에 풀어놨던 것)
나휘동	.	Python	LoadBalancingProblem/Leonardong

[edit]

이 문제에 대한 의견이나 질문을 말해주세요 ¶

IPSC 라고 해서 엄청 어려운 문제도, 그렇다고 한번에 풀수 있는 쉬운 문제도 아닙니다. 풀어본 문제 몇개 중에서 재미있다고 생각되는 문제들을 여러 사람들이 함께 풀어보았으면 하는 바람에서 페이지를 열어보았습니다. - 임인택

----
see also IpscLoadBalancing, 문제은행
----
문제분류