[이코테] 완전탐색, DFS - 연산자 끼워넣기 with 파이썬

JIN KANG·2022년 10월 19일

DFS algorithm python 완전탐색 이코테 코딩테스트

이코테

목록 보기

19/29

1. 문제

백준 14888과 동일한 문제
링크
수 리스트, 연산자 리스트가 들어온다.
수의 순서는 바꾸지 않고, 연산자를 사이에 끼워 넣는다.
계산
- 연산자 우선 순위를 무시하고 앞에서부터 진행
- 나눗셈은 몫만 취한다.
- 음수를 양수로 나눌때는 양수로 바꾼뒤 몫을 취하고, 그 몫을 음수로 바꾼다.
입력, N개의 숫자, N-1개의 연산자
- 수의 갯수
- 수
- 덧셈, 뺄셈, 곱셉, 나눗셈의 수
출력 : 연산결과의 최대값, 최소값
조건 : 연산의 중간과정과 결과과정들의 범위는 -10억~10억 사이이다.

입출력 예시

2. 아이디어

연산 코드를 연산으로 바꿔서, permutations 모듈로 순열로 만든다음, 모든 순열 조건에 대해서, 연산을 해보고 최대값과 최소값을 갱신한다.

3-1. 코드 (permutations 활용 version)

Python3는 시간초과, PyPy는 시간안에 통과 가능

from itertools import permutations
## 입력 
N = int(input())

numbers = list(map(int, input().split()))

# 연산자 리스트로 바꾸기
cal = list(map(int, input().split()))
cal_text = ['+','-','*','/']
cal_sign = ''

for idx, num in enumerate(cal):
    cal_sign += cal_text[idx]*num
    
cal_signs = list(cal_sign)

maximum = -1e9
minimum = 1e9


for combi in permutations(cal_signs, len(cal_signs)):   # 연산의 모든 경우
    total = numbers[0]                # 연산의 합
    for i in range(1,len(numbers)):   # 숫자 두번째부터, 끝까지 
        if combi[i-1] == '+':
            total += numbers[i]
        elif combi[i-1] == '-':
            total -= numbers[i]
        elif combi[i-1] == '*':
            total *= numbers[i]
        elif combi[i-1] == '/':
            total = int(total/numbers[i])    
            # c++14의 기준 , 양수로 바꾼뒤 몫을 취하고, 그 몫을 음수로 바꾸는 것
    
    if total > maximum:
        maximum = total
    if total < minimum:
        minimum = total
        
print(maximum)
print(minimum)

3-2. 참조코드 (재귀 활용 version)

재귀를 이용한 저자의 코드에서 이해가 안되는 부분이 있어서, 백준에 제출된 코드 중 유사한 것으로 학습했다.

# 재귀문 
# 재귀는 선언적 프로그래밍이다. 목표만 설정하면 된다. 
# index로 종료 , result에 값이 모이게 

def dfs(index, result, add, sub, mul, div):
    global n , max_num, min_num
    if index == n :
        max_num = max(max_num , result)
        min_num = min(min_num , result)
        return   # 리턴이 없기 때문에, 앞선 재귀문들이 그냥 끝나버린다. 
    else:
        if add :
            dfs(index + 1, result + nums[index] , add-1, sub, mul, div)
        if sub:
            dfs(index +1 , result - nums[index] , add, sub-1, mul, div)
        if mul:
            dfs(index +1, result * nums[index], add, sub, mul-1, div)
        if div:
            dfs(index+1, int(result / nums[index]), add, sub, mul, div-1)
            
# 입력
n = int(input())

nums = list(map(int, input().split()))
# 최소값, 최대값 초기화
max_num = -1e9
min_num = 1e9

add, sub, mul, div = map(int, input().split())

dfs(1, nums[0], add, sub, mul, div)

print(max_num)
print(min_num)