4.5. 연습문제

오늘의 연습문제는 다음 카페에서 본 퀴즈인데, 왕초보 파이썬의 게시판에도 올려서 함께 풀어보았던 것이랍니다. 문제를 보실까요?

[문제] 컴퓨터가 몇 대 있고 연산해야할 프로그램도 몇 개 있습니다. 가장 최적화 된 프로그램 대 컴퓨터 분배를 수행할 수 있는 프로그램을 작성하세요.

예) 컴퓨터는 2대가 있고, 프로그램의 수행시간은 각 3분, 5분, 2분이라면, 컴퓨터 하나는 3분, 2분짜리 프로그램을 수행하고 다른 컴퓨터는 5분짜리 프로그램을 수행하면 됩니다.

입력
computer : 2

program : 3, 5, 2

출력
computer1 : 5
computer2 : 3, 2

어떠세요? 좀 어렵죠? 저도 이 문제를 보고 문제가 무슨 뜻인지 몰라서 한참 헤맸답니다. 그러나 총명하신 여러분은 금방 이해하셨으리라 생각합니다.

이제 문제를 풀어볼텐데요, 아래의 해설을 보시기 전에 문제를 다른 곳에 옮겨놓고 잠시 생각을 해보시기 바랍니다. 가능하면 직접 풀어보는 것이 좋으니까요.

컴퓨터 여러 대가 프로그램을 나눠서 수행한다면, 각각의 컴퓨터에게 같은 양의 일을 줘서 같이 끝내는 것이 좋겠죠? 예에서는 총 10분 동안 할 일을 컴퓨터 두 대에게 나눠주는 거니까 각각 5분 씩 일을 시키면 되는 거구요.

만약, 수행할 프로그램 중에 평균보다 더 오래 걸리는 것이 있다면, 그러니까 프로그램이 7분, 3분 두 개가 주어지면 어떻게 나눠주는 것이 좋을까요? 할 수 없이 한 대는 7분 동안, 다른 한 대는 3분 동안 일을 해야겠죠? 7분 짜리를 5분, 2분으로 쪼개서 넘겨주라구요? 시로~.

지금까지 살펴본 것을 바탕으로 문제 해결을 위한 논리를 만들어 보겠습니다.

프로그램들을 전부 수행하는 데 걸리는 총수행시간을 구한다.
총수행시간을 컴퓨터 대수로 나누어 각각의 컴퓨터의 평균수행시간을 구한다.
만약 평균수행시간보다 더 오래 걸리는 프로그램이 있으면:
    그냥 컴퓨터에게 준다.
평균 수행시간보다 짧게 걸리는 것들은:
    평균수행시간만큼 모아서 컴퓨터에게 준다.

처음에는 이런 식으로 문제를 풀었는데, 나중에 다시 보니까 복잡하면서도 비효율적이라는 생각이 들더군요. 그래서 몇날몇일을 고민하다보니 기발한 아이디어가 떠올랐습니다.

새로운 해결방법의 핵심은 ‘가장 가벼운 바구니에 빵을 담는다’라는 것입니다. ‘컴퓨터’와 ‘수행할 프로그램’ 대신 ‘바구니’와 ‘빵’이라고 생각한 것이죠. 그렇게 되면, 컴퓨터에게 프로그램을 분배하는 것은 바구니에 빵을 하나씩 담는 것과 흡사하지요.

바구니를 준비한다.
바구니에 담을 빵들을 크기순으로 정렬한다.
빵을 모두 바구니에 담을 때까지:
    가장 가벼운 바구니에 가장 큰 빵을 담는다.
결과를 돌려준다.

이 논리를 프로그램으로 구현한 것이 아래의 예제입니다. 대화식으로 작업하는 것보다 텍스트 에디터를 사용해서 프로그램 파일로 작성하는 것이 좋겠죠?

# prg2com.py

def prg2com(inlist, coms):
    outlist = []
    sumout = []
    for x in range(coms):
        outlist.append([])
        sumout.append(0)
 
    inlist.sort()
    inlist.reverse()
 
    for bread in inlist:
        lowbasket = sumout.index(min(sumout))
        outlist[lowbasket].append(bread)
        sumout[lowbasket] += bread
 
    return outlist       

print prg2com([3,15,6,22,13,2], 3)

정말 간단하죠? 예전에 소개해드렸던 풀이를 보셨던 분이라면 놀라실 거예요. 저 스스로도 감탄했거든요.

프로그램을 전체적으로 보면 prg2com()이라는 함수를 하나 정의해두고, 맨 마지막 줄에서 그 함수를 호출하는 형태입니다. 그리고, prg2com() 함수는 inlist와 coms라는 두 개의 인자를 받아서, outlist를 결과로 돌려줍니다.

문제에서 입력과 출력을 아래와 같이 한다고 했는데, 예제에서는 단순하게 리스트와 변수를 입력받고, 리스트를 출력하도록 처리했습니다. 그렇게 하는 것이 간편하고 문제에 집중하는데 도움이 되는 것 같아서요.

일단 함수만 만들어두면 입출력을 구현하는 것은 식은 죽 먹기겠죠?

입력
computer : 2
program : 3, 5, 2

출력
computer1 : 5
computer2 : 3, 2

이제 함수의 내부를 살펴봅시다. 먼저 "바구니를 준비한다."

    outlist = []
    sumout = []
    for x in range(coms):
        outlist.append([])
        sumout.append(0)

outlist가 바로 바구니(컴퓨터)들의 목록이구요, sumout은 바구니 한 개마다 담겨진 빵(수행할 프로그램)의 합계를 갖는 목록입니다. coms는 함수의 인자로 받은 컴퓨터 대수(바구니의 개수)였죠? coms 값이 3이라면 위의 for 문을 수행한 후에 outlist는 [[], [], []]와 같이 되고, sumout은 [0, 0, 0]이 됩니다. 나중에 함수가 모두 실행되고 나면 outlist에는 결과값이 [[22], [15, 3, 2], [13, 6]]와 같이 담기고, 그 때 sumout은 [22, 20, 19]과 같이 되어있도록 할 생각이지요.

다음으로, "바구니에 담을 빵들을 크기순으로 정렬한다."

    inlist.sort()
    inlist.reverse()

함수의 인자로 받은 inlist를 sort()로 정렬한 다음, reverse()로 순서를 뒤집습니다. 리스트에 sort()를 적용하면 리스트의 원소들이 오름차순으로 정렬되구요, 다시 reverse()를 적용하면 내림차순으로 정렬되는 것입니다. 이제 각각의 빵을 바구니로 분배하겠습니다.

    for bread in inlist:
        lowbasket = sumout.index(min(sumout))
        outlist[lowbasket].append(bread)
        sumout[lowbasket] += bread

가장 가벼운 바구니를 구하기 위해 min(sumout)을 했구요, 그 바구니의 인덱스를 구해서 lowbasket이라고 하였습니다. 각각의 바구니는 outlist와 sumout에서 같은 인덱스를 쓴다는 점을 이용하기 위해서이지요. 예를 들어서, 만약 outlist 전체가 [[22], [15], [13, 6]]인 상태라면 sumout은 [22, 15, 19]가 되어있을 테구요, 현재 가장 가벼운 바구니는 15가 들어있는 바구니입니다.

>>> outlist = [[22], [15], [13, 6]]
>>> sumout = [22, 15, 19]
>>> min(sumout)
15

이것의 인덱스를 알아보면 1이라는 걸 알 수 있지요.

>>> sumout.index(15)
1

이제 구해진 인덱스를 lowbasket이라고 하고, outlist와 sumout에서 인덱스 1인 바구니는 다음과 같습니다.

>>> outlist[1]
[15]
>>> sumout[1]
15

이런 방법으로 두 리스트에서 같은 바구니를 가리키는 부분을 찾아서 바구니에 빵을 담을 때, 그 바구니가 얼마나 찼는지도 함께 체크해두는 겁니다. sumout[lowbasket] += bread
는
sumout[lowbasket] = sumout[lowbasket] + bread
와 같은 의미입니다.

inlist의 모든 원소에 대해 이 일을 반복했으면, 즉 모든 빵을 바구니에 나눠담았으면, 구해진 outlist를 함수의 결과값으로 돌려줍니다.

    return outlist

끝이에요~. 이제 프로그램을 한 번 돌려보세요. 아주 잘~ 될거예요~

출처 : wikidocs 왕초보를 위한 파이썬