Load Balancing 이라는 개념은 앞으로 몇번 접하게 될 개념입니다. 컴퓨터분야에서뿐만 아니라 다른 분야 (예를 든다면 이삿짐 업체나, 택배업체, 우체국 등등..) 에서도 쓰입니다. Load Balancing은 역할분담을 가장 적당하고 고르게 하여 각각의 개체들이 부담을 적게 느끼고 전체 작업시간을 단축시킬수 있도록 해 줍니다. 간단한 LoadBalancingProblem 문제를 접하여보고 기회가 닿는다면 조금더 복잡한 종류의 문제를 풀어보는것도 좋을것 같습니다. ---- == 출제자 == IPSC, ["임인택"]이 한글화하고 요구하는 입&출력 스펙을 변경함 - [http://ipsc.ksp.sk/problems/ipsc2002/b.php 원래 문제 링크] == Problem name : Load Balancing == SuperComputer 사는 N 개의 CPU 로 이루어진 슈퍼컴퓨터를 제작하였다. 각각의 CPU는 1에서 N 까지 번호가 새겨져 있으며 각각 독립적인 작업을 수행한다. 새로운 작업이 생기면 무작위로 한개의 CPU 에 그 작업이 할당된다. 이럴 경우 어떤 CPU 에는 작업이 엄청 많고 다른 CPU 에는 할당된 작업이 적거나 아예 없는 상황이 발생하게 된다. 이럴경우 각 CPU 에 작업을 적당하게 분배하여야 하는데 각각의 재분배 작업은 N번 CPU가 1-N, 1-N CPU 에 각각 하나씩의 작업을 전달하는 것이다. 차근차근 살펴보면, 1. 1번 CPU의 작업의수를 본다. 다른 CPU 에 비해 작업이 많으면 양옆의 CPU 중에 한곳으로한 작업을 전달해줄수 있는데 1번 CPU 의 왼쪽에는 CPU 가 없으므로 2번 CPU 에만 작업을 전달해 줄 수 있다. 1. 2번 CPU 의 작업의 수를 본다. 만약 2 번 CPU 의 작업의 수가 많다고 생각되면 1번, 3번 CPU 로 작업을 전달 해 줄수 있다. 1. (...) N 번 CPU 를 본다. 작업을 전달해줘야 할 경우 N 번 CPU 의 오른쪽에는 CPU 가 없으므로, 왼쪽으로만 전달할 수 있다. 1. 다시 1 번 CPU 를 본다. ..... (이 과정을 모든 CPU 가 최고-최저<=1 이 될때까지 반복한다) ..... == 입력값 == 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 }}} == 출력값 == 1. 작업의 이동 후 각각의 CPU 에 적당하게 작업이 분배되었는가? 1. 작업의 이동 횟수는 얼마인가? 1. 몇번 돌아보았는가? (1부터 N 까지 보았을때를 1 round 라고 한다) == source == || 해결자 || 개발시간 || 사용언어 || Source || || 강양욱 || . || Java || Upload:IPSCLoadBalancing-macare.zip || || 임인택 || . || Java || [LoadBalancingProblem/임인택] (그냥 예전에 풀어놨던 것) || || 나휘동 || . || Python || [LoadBalancingProblem/Leonardong] || == 이 문제에 대한 의견이나 질문을 말해주세요 == IPSC 라고 해서 엄청 어려운 문제도, 그렇다고 한번에 풀수 있는 쉬운 문제도 아닙니다. 풀어본 문제 몇개 중에서 재미있다고 생각되는 문제들을 여러 사람들이 함께 풀어보았으면 하는 바람에서 페이지를 열어보았습니다. - 임인택 ---- see also IpscLoadBalancing, ["문제은행"] ---- ["문제분류"]