[이코테/dfs/삼성기출] 연산자 끼워넣기(정답,해설)

문제 

14888번: 연산자 끼워넣기

 

정답(순열)

from itertools import permutations
n = int(input())
nums = list(map(int,input().split()))
data = list(map(int,input().split())) 
exam = ["p","m","c","d"] 
opers = []
for d in range(len(data)):
    for _ in range(data[d]):
        opers.append(exam[d]) 
        
# 어차피 연산자는 4개이므로 다음과 같이 더 간단하게 작성할 수 있다
# opers = 'p' * data[0] + 'm' * data[1] + 'c' * data[2] + 'd' * data[3]
 
cal_min = 1e9
cal_max = -1e9

def calculator(operlist):
    res = nums[0]
    for i in range(1,len(nums)): 
            if operlist[i-1] == "p":
                res += nums[i]
            elif operlist[i-1] == "m":
                res -= nums[i]
            elif operlist[i-1] == "c":
                res *= nums[i]
            elif operlist[i-1] == "d" :
                res = int(res/nums[i])
                # res //= nums[i] 
    return res 

for per in list(permutations(opers,len(opers))):
    res = calculator(per)
    cal_min = min(cal_min,res)
    cal_max = max(cal_max,res)

print(cal_max)
print(cal_min)

 

정답(dfs)

n = int(input())
data = list(map(int,input().split()))
add,sub,mul,div = map(int,input().split())
min_v = 1e9
max_v = -1e9 

def dfs(i,now): 
    global min_v, max_v,add,sub,mul,div
    if i == n: 
        min_v = min(min_v,now)
        max_v = max(max_v,now)
    else:
        if add>0:
            add-=1
            dfs(i+1,now+data[i])
            add+=1
        if sub>0:
            sub-=1
            dfs(i+1,now-data[i])
            sub+=1
        if mul>0:
            mul-=1
            dfs(i+1,now*data[i])
            mul+=1
        if div>0:
            div-=1
            dfs(i+1,int(now/data[i]))
            div+=1

dfs(1,data[0]) 

print(min_v)
print(max_v)

 

해설

처음 풀 때는 당연히 순열을 떠올려 풀었다.

주어진 연산자들로 만들 수 있는 순열 경우의 수 마다 연산을 수행한 후 최소/최대값을 갱신하는 방식으로 풀리긴 했다. 

하지만 주어진 연산자의 개수에 따라 경우의 수가 급격히 늘어날 수 있고, 따라서 시간,공간 복잡도가 늘어나게 되므로 바람직한 풀이방식은 아니었다. 

 

dfs 풀이방식은 재귀호출을 이용해 주어진 연산자를 모두 사용했을 때 연산의 결과값을 갱신하는 방식으로 구현한다.

정답 코드를 보고 내가 궁금했던 점은 두 가지였다.

 

1. 저 코드가 어떻게 모든 경우의 수를 한번씩 다 해 볼 수 있다는 건지 로직에 대한 의문

2. 순열과 dfs방식 둘 다 결국은 전체 경우의 수를 한번씩 모두 계산해보는건데 어떻게 dfs가 더 효율적인지에 대한 의문

 

공부를 하면서 내 나름대로 의문에 대한 해답을 찾을 수 있었다. 

 

---

예를 들어, 수열 [1,2,3,4] 와 연산자 +,-,x 가 주어지고 연산자 끼워넣기를 통해 최소/최대값을 구하는 문제가 있을 때 

순열을 사용한 풀이
- 주어진 연산자를 배치하는 모든 경우의 수를 구해 각각의 경우의 수 마다 연산하여 결과값을 갱신한다.

다시말해,  1 + 2 - 3 x 4 를 계산해 나온 결과값인 0을 처음 저장하고, 그 다음 1 + 2 x 3 - 4 를 계산해 그 결과값인 5를 이전 결과값과 비교하여 저장하는 과정을 총 경우의 수 6번만큼 반복하게 된다. 
문제풀이 코드에서는 이 경우의 수를 구하는 과정을 permutations를 사용해 구현했다.

 

dfs를 사용한 풀이
- 각 연산자의 사용횟수를 체크하고, 재귀호출을 통해서 다음 연산자와의 계산을 하여 모든 연산자를 사용했을 때 결과값을 갱신한다.

처음 함수를 호출할 때 1과 숫자배열의 첫 번째 값을 넘겨준다. 

그리고 각 연산자의 남은 개수가 0보다 많으면 해당 연산자의 개수를 -1하고, 재귀호출을 하면서 연산을 수행한 값을 넘김

이 때 i의 역할은 재귀호출의 단계를 표시하는 용도 = 연산을 수행한 횟수를 체크하는 용도 라고 생각하니까 이해하기 쉬웠다.

 

예를 들어서 1 + 2 - 3 x 4 연산을 처음에 수행했다면 재귀호출은 

1. i = 1인 단계에서 호출된 dfs(2, 3) : +연산자 사용

2. i = 2인 단계에서 호출된 dfs(3, 0) : -연산자 사용

3. i = 3인 단계에서 호출된 dfs(4, 0) : x 연산자 사용

4. i = 4인 단계에서는 i == n 이 성립하기 때문에 최종 결과값 0을 min_v로 갱신하고 함수를 빠져나간다. 

5. 그러면 i=3이었던 단계의 함수호출이 끝난 후 다시 해당  연산자 x 의 개수를 증가시키고, 다음 div연산자(/)가 있는지 확인하지만 존재하지 않기 때문에 이 단계의 함수도 종료된다.

6. 그 다음 i=2 인 단계로 돌아와서 함수호출이 끝난 후 연산자 - 의 개수를 증가시키고, 다음 mul 연산자(x)가 있는지 확인하고, dfs(3,9)를 재귀호출한다. : x연산자 사용 

7. 다시 i = 3인 단계가 되고, sub연산자(-)가 있으므로 dfs(4,5)를 재귀호출 : - 연산자 사용

8. i==4가 되었기 때문에 결과값 5를 갱신하고 함수를 빠져나옴

9. 위 과정을 반복하면 결국 모든 연산자를 조합한 경우의 수를 한번씩 계산할 수 있다. 

 

전체 과정에서 i는 연산자가 몇 번 사용되었는지 알 수 있기 때문에 연산의 종료시점을 정할 수 있다.

( n은 숫자의 개수이고, 연산자의 개수는 항상 (n-1)이기 때문에 처음 1을 가지고 들어간 dfs함수에서 모든 연산자를 다 사용했을 때 i의 값은 n과 일치하게 될 것이므로)

 

 

결과적으로, 이러한 로직을 통해서 dfs로도 모든 경우의 수를 계산할 수 있음을 알 수 있었고, 

두 번째 의문이었던 왜 dfs가 더 효율적인지도 나름 그럴듯한 답을 생각해봤다. 

저장된 이전의 값을 다시 활용하는 점에서 다이나믹 프로그래밍이 떠오르기도 했는데 

재귀호출을 하고, 다시 돌아와서 다른 연산을 하는 과정을 통해 연산의 총 횟수자체를 줄이는 효과가 나기 때문에 더 효율적이지 않을까 하는 나만의 답을 얻게 되었다..  

 

 

전체적으로 어렵게 느껴왔던 dfs와 재귀호출에 대해 조금 더 이해하게 되었고
백트래킹의 개념도 처음 알게되어서 아주 의미있는 문제였다!

 

 

 

참조

이것이 취업을 위한 코딩테스트다(with. python)