합의 차이가 최소가 되는 분할 1편

1. 알고리즘

 

1 이상의 양의 정수가 리스트 내에 존재

 

하나의 리스트를 두개의 리스트로 분할하고자 하는데 각 리스트의 수의 합의 차이가 최소가 되도록 분할하고자 한다.

 

합의 차이의 최솟값을 return

 

가장 쉬운 방법은 itertools.combinations를 이용해서 완전 탐색을 하는 것

 

그러나 완전 탐색을 하면 효율성이 매우 떨어짐

 

먼저 초기 변수를 지정함

 

mmr은 주어진 전체 리스트

 

n은 리스트의 인덱스 지정

 

team1은 첫번째 리스트의 정수 총합

 

team2는 두번째 리스트의 정수 총합

 

table은 dynamic programming table

 

def findMinAbsDiff(mmr, n, team1, team2, table):
 
    # Base case: if the list becomes empty, return the absolute
    # difference between both sets
    if n < 0:
        return abs(team1 - team2)
 
    # Construct a unique key from dynamic elements of the input.
    # Note that we can uniquely identify the subproblem with `n` and `S1` only,
    # as `S2` is nothing but `S-S1`, where `S` is the sum of all elements
    key = (n, team1)
 
    # If the subproblem is seen for the first time, solve it and
    # store its result in a dictionary
    if key not in table:
 
        # Case 1. Include the current item in subset `S1` and recur
        # for the remaining items `n-1`

        inc = findMinAbsDiff(mmr, n - 1, team1+mmr[n], team2, table)
 
        # Case 2. Exclude the current item from subset `S1` and recur for
        # the remaining items `n-1`

        exc = findMinAbsDiff(mmr, n - 1, team1, team2+mmr[n], table)
 
        table[key] = min(inc, exc)
 
    return table[key]

 

recursive하면서 dynamic programming으로 접근하는 것을 고려함

 

아이디어는 n번째 원소가 team1에 포함된 경우와 team1이 아닌 team2에 포함된 경우로 나눌 수 있다는 것

 

2가지를 고려해서 최솟값을 선택하면 된다는 거

 

dynamic programming을 위해 table을 만드는데 n과 team1을 이용해서 유일하게 key를 만들 수 있다고 함

 

recursive가 단순히 보기만 하면 이해가 안되니까 간단한걸로 한번 하나하나 생각을 해봄

 

# Input: a set of items
mmr = [10,20]

# create a dictionary to store solutions to subproblems
table = {}
team1 = 0
team2 = 0

print('The minimum difference is', findMinAbsDiff(mmr, len(mmr) - 1, team1, team2, table))

{(0, 20): 10}
{(0, 20): 10, (0, 0): 10}
{(0, 20): 10, (0, 0): 10, (1, 0): 10}
The minimum difference is 10

 

[10,20]을 넣는다고 생각해보자.. 구하고자 하는 문제의 답은 [10,20]에서 최소 합이 되도록 분할을 하는 것이므로 findMinAbsDiff([10,20],1,0,0,table)이다

 

먼저 n=1이므로 20이 team1에 포함된 경우와 team2에 포함된 경우로 나뉠거임

 

table = {}

 

n=1이고 team1=0일때 key = (1,0)인데 이 key는 table에 없으니까...

 

inc = findMinAbsDiff([10,20],0,20,0,table)   - ①

 

exc = findMinAbsDiff([10,20],0,0,20,table)   - ②

 

그러면 이제 inc랑 exc 각각에서 findMinAbsDiff가 계산이 될거임

 

---------------------------------------------------------------------------------------------------------------

 

①의 inc부터 먼저 보면 findMinAbsDiff([10,20],0,20,0,table)은....

 

n=0이고 team1=20이므로 key=(0,20)

 

10이 team1에 포함되냐 포함이 안되냐...로 나뉠테니까

 

inc = findMinAbsDiff([10,20],-1,30,0,table)

 

exc = findMinAbsDiff([10,20],-1,20,10,table)

 

근데 n<0이므로 이제 inc와 exc를 구할 수 있을거임.. inc=30이고 exc=10

 

그래서 table[key]=min(inc,exc)이므로... table[(0,20)]=10 이 값이 ① inc=10에 들어가야함.. inc를 계산했으니까

 

그러니까 table[(0,20)]=10으로 dynamic table을 저장한다음에 inc에도 값을 구해놓는거임

 

실제로 table을 print해봤는데 {(0,20) : 10}을 볼수 있음

 

------------------------------------------------------------------------------------------------------------------

②의 exc도 비슷하게 계산할 수 있다.. 

 

n=0이고 team1=0이므로... key=(0,0)이고 이 key는 현재 table에 없으니까...

 

10이 team1에 포함되냐 안되냐로 나뉘면서...

 

inc = findMinAbsDiff([10,20],-1,10,0,table)

 

exc = findMinAbsDiff([10,20],-1,10,20,table)

 

n<0니까 inc와 exc를 구할수 있다.. inc=10, exc=10

 

그러면 table[(0,0)]=10이 저장되면서 ②의 exc=10으로 계산이 되는거임

 

역시 table을 print해봤는데 {(0,20):10,(0,0):10}이 된거 볼 수 있음

 

--------------------------------------------------------------------------------------------------

 

그러면 다시 처음으로 돌아가서... key = (1,0)일때...

 

inc = findMinAbsDiff([10,20],0,20,0,table)=10   - ①

 

exc = findMinAbsDiff([10,20],0,0,20,table)=10   - ②

 

이고... table[(1,0)]=10으로 저장되면서 실제로 이 값이 findMinAbsDiff([10,20],1,0,0,table)의 값이므로 정답은 10

 

[10,20]을 분할하는데 두 리스트의 합의 차이가 최소가 되는 최솟값은 10

 

----------------------------------------------------------------------------------------------------

 

너무 단순한 예시니까 조금 더 복잡한 예시를 들면 recursive한다는 것을 느낄 수 있을 것 같다

 

# Input: a set of items
mmr = [10,20,15,5,25]

# create a dictionary to store solutions to subproblems
table = {}
team1 = 0
team2 = 0

print('The minimum difference is', findMinAbsDiff(mmr, len(mmr) - 1, team1, team2, table))

{(0, 65): 55}
{(0, 65): 55, (0, 45): 15}
{(0, 65): 55, (0, 45): 15, (1, 45): 15}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5, (0, 5): 45}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5, (0, 5): 45, (1, 5): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5, (0, 5): 45, (1, 5): 5, (2, 5): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5, (0, 5): 45, (1, 5): 5, (2, 5): 5, (0, 35): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5, (0, 5): 45, (1, 5): 5, (2, 5): 5, (0, 35): 5, (0, 15): 25}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5, (0, 5): 45, (1, 5): 5, (2, 5): 5, (0, 35): 5, (0, 15): 25, (1, 15): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5, (0, 5): 45, (1, 5): 5, (2, 5): 5, (0, 35): 5, (0, 15): 25, (1, 15): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5, (0, 5): 45, (1, 5): 5, (2, 5): 5, (0, 35): 5, (0, 15): 25, (1, 15): 5, (0, 0): 55}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5, (0, 5): 45, (1, 5): 5, (2, 5): 5, (0, 35): 5, (0, 15): 25, (1, 15): 5, (0, 0): 55, (1, 0): 15}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5, (0, 5): 45, (1, 5): 5, (2, 5): 5, (0, 35): 5, (0, 15): 25, (1, 15): 5, (0, 0): 55, (1, 0): 15, (2, 0): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5, (0, 5): 45, (1, 5): 5, (2, 5): 5, (0, 35): 5, (0, 15): 25, (1, 15): 5, (0, 0): 55, (1, 0): 15, (2, 0): 5, (3, 0): 5}
{(0, 65): 55, (0, 45): 15, (1, 45): 15, (0, 50): 25, (0, 30): 5, (1, 30): 5, (2, 30): 5, (0, 60): 45, (0, 40): 5, (1, 40): 5, (0, 25): 5, (1, 25): 5, (2, 25): 5, (3, 25): 5, (0, 20): 15, (1, 20): 5, (0, 5): 45, (1, 5): 5, (2, 5): 5, (0, 35): 5, (0, 15): 25, (1, 15): 5, (0, 0): 55, (1, 0): 15, (2, 0): 5, (3, 0): 5, (4, 0): 5}
The minimum difference is 5

 

[10,20,15,5,25]를 두 집합으로 분할하는데 합의 차이가 최소가 되도록 분할할때, 그 최솟값은??

 

구하고자 하는 문제는 findMinAbsDiff([10,20,15,5,25],4,0,0,table)

 

그러면 먼저 n=4이고 team1=0인 경우.. key=(4,0)이고... mmr[4]=25가 team1에 들어가냐 안들어가냐로 나뉘면서...

 

inc = findMinAbsDiff([10,20,15,5,25],3,25,0,table) - ①

 

exc = findMinAbsDiff([10,20,15,5,25],3,0,25,table) - ②

 

table[(4,0)] = min(inc,exc)

-----------------------------------------------------------------------------------------------------------

 

그러면 table[(4,0)] = min(inc,exc)을 구하기 위해 ①의 inc와 ②의 inc를 구할거임

 

inc = findMinAbsDiff([10,20,15,5,25],3,25,0,table) - ①을 먼저 구하기 위해...

 

n=3이고 team1=25에서.. mmr[3]=5가 team1에 들어가냐 안들어가냐로 나뉘면서...

 

inc_(3,25) = findMinAbsDiff([10,20,15,5,25],2,30,0,table)

 

exc_(3,25) = findMinAbsDiff([10,20,15,5,25],2,25,5,table)

 

inc = min(inc_(3,25),exc_(3,25))

 

-----------------------------------------------------------------------------------------------------------

 

inc = min(inc_(3,25),exc_(3,25))를 구하기 위해서... inc_(3,25) = findMinAbsDiff([10,20,15,5,25],2,30,0,table)을 계산해야하는데...

 

n=2이고 team1=30이면서 mmr[2]=15가 team1에 들어가냐 안들어가냐로 나뉘면서...

 

inc_(2,30) = findMinAbsDiff([10,20,15,5,25],1,45,0,table)

 

exc_(2,30) = findMinAbsDiff([10,20,15,5,25],1,30,15,table)

 

inc(3,25) = min(inc_(2,30),exc_(2,30))................................

 

-------------------------------------------------------------------------------------------------------

 

................................................ 계속 반복

 

-------------------------------------------------------------------------------------------------------------

 

이렇게 n을 줄여나가면서 recursive하게 가장 작은 마지막 문제로 도달할 것이고...

 

가장 마지막 문제를 풀게되면 역방향으로 돌아가면서 처음 문제의 답을 구할수 있는거임

 

그 과정에서 이미 푼 문제는 table에 저장하여 table[key]로 불러오기만 하면 이미 푼 문제는 바로 답을 내니까 시간도 절약

 

# Input: a set of items
mmr = [ 68, 35, 1, 70, 25, 79, 59, 63, 65, 6, 46, 82, 28, 62, 92, 96, 43, 28, 37, 92, 5, 3, 54, 93, 83, 22, 17, 19, 96, 48, 27, 72, 39, 70, 13, 68, 100, 36, 95, 4, 12, 23, 34, 74, 65, 42, 12, 54, 69, 48, 45 ]

# create a dictionary to store solutions to subproblems
table = {}
team1 = 0
team2 = 0

print('The minimum difference is', findMinAbsDiff(mmr, len(mmr) - 1, team1, team2, table))

The minimum difference is 1

 

이렇게 길어도 1초안에 답을 낼수 있음

 

완전탐색하면 영원히 답이 안나옴

 

 

2. 되돌아보기

 

문제 자체는 이해하기 쉬운데 상당히 고난이도의 문제였다

 

dynamic programming의 개념은 알겠는데.. 응용하기가 쉽지 않네

 

유일한 key를 (n,team1)으로 설정할수 있는지??

 

2가지 가능성 mmr[n]이 team1에 포함되느냐 포함되지 않느냐로 나눠서 생각할 수 있는지?? (사실 이게 제일 어려운듯)

 

n을 줄여나가면서 recursive하게 짤수 있느냐??

 

다시 한다면 풀수 있을까.? 계속 보면서 익히는 수밖에

 

 

3. 참고

 

https://www.techiedelight.com/minimum-sum-partition-problem/

Minimum Sum Partition Problem – Techie Delight