중복된, 비효율적인 연산을 줄이는 연습문제 -요리사-

1. 문제

 

4012. [모의 SW역량테스트] 요리사

 

SW Expert Academy

SW Expert Academy

 

N개의 식재료를 N/2개씩 나누어 2개의 요리를 하려고 한다. 각 요리의 맛은 음식을 구성하는 식재료들의 시너지의 합으로 구해진다.

 

음식의 맛의 차이가 최소가 되는 경우를 찾는다면?

 

 

2. 풀이1

 

순열과 조합을 이용하는 문제가 될텐데 실전 문제에까지 직접 구현해서 사용할 이유는 전혀 없고 

 

from itertools import combinations, permutations를 이용하자

 

처음에 풀때는 2개의 재료에 대해서는 설명이 명확한데 3개의 재료에 대해서는 시너지를 어떻게 계산하는지 명확하지가 않아서 문제였는데

 

1,2,3,4,5,6에서 2,3,4와 1,5,6으로 나뉜다고 한다면

 

s23+s32+s24+s42+s34+s43이랑 s15+s51+s16+s61+s56+s65라고 한다더라

 

그러니까 3개에서 2개를 뽑는 순열을 이용해서 시너지 배열에 넣어가지고 합을 구하면 될것 같다

 

from itertools import combinations,permutations

T = int(input())

for t in range(1,T+1):
    
    n = int(input())

    s = [list(map(int,input().split())) for _ in range(n)]

    ingredient = range(0,n) ##음식재료 0~n-1

    all_combs = combinations(ingredient,n//2)  ##음식재료 n개에서 n/2개를 뽑는 조합의 수

    min_s = 20000
    
    ##모든 조합의 수에서 조합을 꺼내고
    for comb in all_combs:
        
        comb2 = []  ##comb에는 n/2개를 뽑는 조합이 들어가니, 나머지 n/2개를 구성하는 작업
        
        for i in range(n):
            
            if i not in comb:
                
                comb2.append(i) #comb에 들어가지 않는 수를 comb2에 넣는다
        
        #comb, comb2의 재료들의 순열을 구한다
        all_a_ingred = permutations(comb,2)
        all_b_ingred = permutations(comb2,2)

        a_taste = 0
        b_taste = 0
        
        ##순열에서 하나씩 꺼내서 시너지를 누적합시켜서
        ##A의 맛과 B의 맛을 구한다
        for a_ingred, b_ingred in zip(all_a_ingred,all_b_ingred):
            
            a_taste += (s[a_ingred[1]][a_ingred[0]])
            b_taste += (s[b_ingred[1]][b_ingred[0]])
        
        #A,B의 맛 차이를 구한다
        taste = abs(a_taste-b_taste)
        
        #최솟값을 갱신한다.
        if min_s > taste:
            
            min_s = taste
    
    print('#'+str(t),min_s)

 

 

근데 50개 다 맞추는데 1초 걸렸는데 남들 풀이보면 0.2초까지도 나오더라고? 어떻게 가능할까?

 

 

3. 최적화 시도1

 

첫번째로 생각해볼만한 방법은 n개중에서 n/2개를 뽑은 조합을 결정하고 나서 나머지 n/2개를 뽑는 조합을 구하는데

 

이전에 뽑은 조합을 다시한번 순회하는 과정을 거쳐서 거기에 포함되지 않은 수를 나머지 리스트에 넣는 방식으로 구했는데

 

##모든 조합의 수에서 조합을 꺼내고
for comb in all_combs:

    comb2 = []  ##comb에는 n/2개를 뽑는 조합이 들어가니, 나머지 n/2개를 구성하는 작업

    for i in range(n):

        if i not in comb:

            comb2.append(i) #comb에 들어가지 않는 수를 comb2에 넣는다

 

combinations가 조합을 어떻게 구하는지를 좀 자세히 살펴봤는데 해법을 찾을 수 있었다

 

 

이렇게 위와 같이 하나의 n/2개를 뽑는 조합에 대응하는 반대 위치에 나머지 조합이 존재한다는 점이다.

 

그렇다면 인덱스를 이용해서 comb를 순회하지 않고도 comb2를 바로 찾을 수 있을 것이다.

 

그러니까 i번째 조합에 대응하는 정확히 나머지 조합의 위치는 len_c-1-i이다..

 

여기서 len_c = len(all_combs)

 

그리고 all_combs를 전부 순회하지 않고 len(all_combs)의 절반만 순회하더라도 모든 경우의 수를 찾을 수 있을 것이다

 

from itertools import combinations,permutations
 
T = int(input())
 
for t in range(1,T+1):
     
    n = int(input())
 
    s = [list(map(int,input().split())) for _ in range(n)]
    
    ##음식 재료
    ingredient = range(0,n)
    
    #n개의 재료 중에서 n/2개를 뽑는 조합
    all_combs = list(combinations(ingredient,n//2))
    
    ##all_combs의 길이
    len_c = len(all_combs)
 
    min_s = 20000
 
    for i in range(len_c//2):  ##전체 조합의 절반만 순회해도 된다.
    
         ##combinations함수는 i번째 n/2개 조합에 대하여, 정확히 반대 위치인 len_c-1-i에 
         ##나머지 n/2개가 있는 조합이 존재한다
         
        comb = all_combs[i]
        comb2 = all_combs[len_c-1-i]
 
        all_a_ingred = permutations(comb,2)
        all_b_ingred = permutations(comb2,2)
 
        a_taste = 0
        b_taste = 0
     
        for a_ingred, b_ingred in zip(all_a_ingred,all_b_ingred):
             
            a_taste += (s[a_ingred[1]][a_ingred[0]])
            b_taste += (s[b_ingred[1]][b_ingred[0]])
 
        taste = abs(a_taste-b_taste)
 
        if min_s > taste:
             
            min_s = taste
     
    print('#'+str(t),min_s)

 

이렇게 했을때 0.5초로 절반정도 시간을 줄일 수 있었다.

 

하지만 여전히 아쉽다

 

 

4. 최적화시도 2

 

이번엔 중간에 순열을 구하는 부분이 조금 아쉽다. 순열을 굳이 구해야하나?

 

all_a_ingred = permutations(comb,2)
all_b_ingred = permutations(comb2,2)

a_taste = 0
b_taste = 0

for a_ingred, b_ingred in zip(all_a_ingred,all_b_ingred):

    a_taste += (s[a_ingred[1]][a_ingred[0]])
    b_taste += (s[b_ingred[1]][b_ingred[0]])

 

예를 들어 2,3,4에서 2개를 뽑는 순열 (2,3), (3,2), (2,4), (4,2), (3,4), (4,3)을 구한 다음에 각각을 순회하여

 

s23+s32+s24+s42+s34+s43을 구했지만..

 

사실 조합 (2,3), (2,4), (3,4)만 구하더라도, 서로 뒤집기만 하면 되니까.. 굳이 순열을 구할 필요는 없다

 

from itertools import combinations,permutations
 
T = int(input())
 
for t in range(1,T+1):
     
    n = int(input())
 
    s = [list(map(int,input().split())) for _ in range(n)]
 
    ingredient = range(0,n)
 
    all_combs = list(combinations(ingredient,n//2))
 
    len_c = len(all_combs)
 
    min_s = 20000
 
    for i in range(len_c//2):
         
        comb = all_combs[i]
        comb2 = all_combs[len_c-1-i]
 
       ##이번엔 순열 대신에 조합을 구하고
        all_a_ingred = combinations(comb,2)
        all_b_ingred = combinations(comb2,2)
 
        a_taste = 0
        b_taste = 0
       
       ##음식의 맛을 구할때, s[a_ingred[1]][a_ingred[0]]과 s[a_ingred[0]][a_ingred[1]]을 동시에 더해줌
        for a_ingred, b_ingred in zip(all_a_ingred,all_b_ingred):
             
            a_taste += (s[a_ingred[1]][a_ingred[0]]+s[a_ingred[0]][a_ingred[1]])
            b_taste += (s[b_ingred[1]][b_ingred[0]]+s[b_ingred[0]][b_ingred[1]])
 
        taste = abs(a_taste-b_taste)
 
        if min_s > taste:
             
            min_s = taste
     
    print('#'+str(t),min_s)

 

 

이랬을때 0.4초이다.. 하지만 1등은 0.2~0.3초만에 푸는데.. 더 빠르게는 불가능할까?

 

 

5. 최적화시도 3

 

조합을 구해놓고 조합을 순회하여 맛의 합을 구하는게 아니라,

 

조합을 구하면서 각 조합에 대해서 맛을 누적합시키면 어떨까??

 

그러니까 이전 알고리즘은

 

2,3,4에서 2개를 뽑는 조합 (2,3), (2,4), (3,4)를 구한다음에

 

[(2,3),(2,4),(3,4)]를 순회하여서 (2,3)이 나오면 s23+s32

 

(2,4)가 나오면 s24+s42, (3,4)가 나오면 s34+s43을 더해주는데..

 

그냥 2,3,4에서 2개를 뽑는 조합은 이중 for문으로 쉽게 작성할 수 있고..

 

첫번째 조합 (2,3)을 구한 순간에 s23+s32를 구하고

 

두번째 조합 (2,4)를 구한 순간에 s24+s42를 구하고

 

세번째 조합 (3,4)를 구한 순간에 s34+s43을 구한다면??

 

조합리스트를 순회하는 시간을 제거할 수 있다

 

from itertools import combinations
 
T = int(input())
 
for t in range(1,T+1):
     
    n = int(input())
 
    s = [list(map(int,input().split())) for _ in range(n)]
    
    ##음식 재료 0~n-1
    
    ingredient = range(0,n)
    
    ##n개중에 n/2개를 뽑는 조합
 
    all_combs = list(combinations(ingredient,n//2))
 
    len_c = len(all_combs)
 
    min_s = 20000
 
   ##전체 조합에서 절반만 순회하여
    for i in range(len_c//2):
   
   #i번째 조합과 len_c-1-i번째 조합은 서로 배반이면서 합집합이 0~n-1이 되는
   #n/2, n/2개로 나눠지는 집합이다.
   
        comb = all_combs[i]
        comb2 = all_combs[len_c-1-i]
 
        a_taste = 0
        b_taste = 0
   
   #각 조합의 길이는 n/2이므로, 각 조합에서 2개를 뽑는 조합 인덱스 x,y를 구한다.
   #조합을 구하면서 동시에 맛도 누적해서 더해준다
   
        for x in range(n//2-1): 
             
            for y in range(x+1,n//2):
                 
                a_taste += (s[comb[x]][comb[y]]+s[comb[y]][comb[x]])
                b_taste += (s[comb2[x]][comb2[y]]+s[comb2[y]][comb2[x]])
   
   ##맛의 차이의 절댓값을 구하고
        taste = abs(a_taste-b_taste)
   
   ##최솟값을 갱신
 
        if min_s > taste:
             
            min_s = taste
     
    print('#'+str(t),min_s)

 

 

6. 되돌아보기

 

생각하면서 비효율적인 부분이 어디인지 체크하고, 시간복잡도 줄인거 아주 좋았고

 

기본원리를 알아야한다는게 여기서 결국 통하네

 

조합을 구하는 가장 기본적인 방법이 다중 for문인데.. 이걸 몰랐다면? 

 

이런걸 쉽게 생각할 수 있었을까??

 

#각 조합의 길이는 n/2이므로, 각 조합에서 2개를 뽑는 조합 인덱스 x,y를 구한다.
#조합을 구하면서 동시에 맛도 누적해서 더해준다

    for x in range(n//2-1): 

        for y in range(x+1,n//2):

            a_taste += (s[comb[x]][comb[y]]+s[comb[y]][comb[x]])
            b_taste += (s[comb2[x]][comb2[y]]+s[comb2[y]][comb2[x]])