백준 14888번 : 연산자 끼워넣기

Python을 이용한 14888 번 :연산자 끼워넣기에 대해서 포스팅하겠습니다.

Table of Contents

14888번 문제설명

N개의 수로 이루어진 수열 A₁, A₂, …, A_N이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

접근방법

1. 깊이 우선 탐색(DFS) 활용

이 문제의 핵심은 가능한 모든 연산자 조합을 사용하여 식을 만드는 것입니다.
깊이 우선 탐색 사용하여 모든 가능한 연산자 조합을 탐색합니다.
각 단계에서 사용 가능한 연산자 중 하나를 선택하고, 다음 숫자로 넘어가며 이 과정을 반복합니다.

2. 연산자 조합 관리

주어진 연산자(덧셈, 뺄셈, 곱셈, 나눗셈)의 개수에 따라 모든 조합을 생성해야 합니다.
각 연산자에 대한 남은 개수를 추적하며, 사용 가능할 때만 해당 연산자를 사용합니다.

3. 연산 순서 고려

문제에서 연산자 우선순위를 무시하고 앞에서부터 순차적으로 계산한다고 명시했습니다.
이에 따라, 연산은 입력된 숫자와 선택된 연산자의 순서에 따라 진행됩니다.

4. 정수 나눗셈의 특별한 처리

음수를 양수로 나누는 경우, C++14 기준에 따라 처리합니다.
음수를 양수로 나누고, 결과를 음수로 변환합니다.

5. 최대값과 최소값의 계산

각 조합으로 계산된 결과값을 기록하며, 이 중 최대값과 최소값을 찾습니다.
모든 조합을 탐색한 후, 계산된 최대값과 최소값을 출력합니다.

6. 효율적인 탐색과 메모리 관리

재귀적 DFS를 사용할 때, 메모리 오버플로우나 시간 초과를 피하기 위해 주의 깊게 구현해야 합니다.
불필요한 탐색을 줄이기 위해 백트래킹 기법을 적용할 수 있습니다.

DFS를 사용했을 때와 백트래킹의 코드 접근 법 차이

재귀 함수의 인자 활용 개선: 이 코드에서는 각 연산자의 남은 횟수(plus, minus, multi, divide)를 직접적으로 재귀 함수의 인자로 사용합니다. 이 방법은 현재 단계에서 사용 가능한 연산자의 수를 명확하게 추적하게 해주며, 이는 탐색 과정을 간소화하고 코드의 이해도를 높입니다. 각 연산자에 대해 남은 횟수만큼만 재귀 호출을 진행하기 때문에, 불필요한 탐색을 줄이고 전체 탐색 과정의 효율성을 증가시킵니다.

효율적인 탐색 방법: 두 번째 코드는 현재 사용 가능한 연산자만을 고려하여 재귀 호출을 진행합니다. 이는 첫 번째 코드와 비교했을 때, 불필요한 반복을 크게 줄이고, 각 단계에서의 연산자 선택을 보다 효율적으로 만듭니다. 예를 들어, 특정 연산자가 더 이상 남아 있지 않다면, 해당 연산자에 대한 탐색 경로는 아예 고려하지 않음으로써 탐색 과정을 빠르게 진행할 수 있습니다.

15649번 코드

1. dfs만 이용한 코드

Python

from sys import stdin

# n은 연산에 사용될 숫자의 개수를 나타냅니다.
n = int(stdin.readline())
# nums는 연산에 사용될 숫자들을 리스트 형태로 저장합니다.
nums = list(map(int,stdin.readline().split()))
# operators_counts는 각 연산자(+, -, *, //)가 사용될 수 있는 횟수를 저장합니다.
operators_counts = list(map(int,stdin.readline().split()))

# operator_exp는 연산자를 문자열 형태로 저장한 리스트입니다. 
# 이는 나중에 연산자를 참조하기 위해 사용됩니다.
operator_exp = ["+","-","*","//"]
# operators는 각 연산자의 인덱스를 operators_counts에 따라 확장한 리스트입니다.
# 예를 들어, operators_counts가 [2, 1, 1, 1]이면 operators는 [0, 0, 1, 2, 3]이 됩니다.
operators = [i for i in range(len(operators_counts)) for j in range(operators_counts[i])]

# top은 계산된 결과 중 최대값을 저장합니다. 초기값은 음의 무한대입니다.
top = float('-inf')
# low는 계산된 결과 중 최소값을 저장합니다. 초기값은 양의 무한대입니다.
low = float('inf')

# 깊이 우선 탐색 함수 정의
def dfs() :
    global top, low
    # operateor_visited에 있는 연산자의 개수가 n-1과 같아지면,
    # 모든 숫자를 사용하여 연산을 완료한 것입니다.
    if len(operateor_visited) >= n-1 :
        temp_re = nums[0]  # 첫 번째 숫자로 시작합니다.
        # 가능한 모든 연산자 조합으로 수식을 계산합니다.
        for j in range(len(operateor_visited)) :
            # operators 리스트와 operateor_visited를 이용하여 현재 연산자를 결정하고, 계산을 수행합니다.
            if operators[operateor_visited[j]] == 0 :
                temp_re += nums[j+1]
            elif operators[operateor_visited[j]] == 1 :
                temp_re -= nums[j+1]
            elif operators[operateor_visited[j]] == 2 :
                temp_re *= nums[j+1]
            else :
                if temp_re < 0 :
                 # 나눗셈 연산에서 음수 처리를 위한 조건입니다.
                    temp_re = -(abs(temp_re) // nums[j+1])
                else : 
                    temp_re //= nums[j+1]

        # 최대값과 최소값 업데이트
        if temp_re > top :
            top = temp_re
        if temp_re < low :
            low = temp_re

        return 
    
    # 가능한 모든 연산자 조합을 탐색
    for i in range(len(operators)) :
        if i not in operateor_visited :
            operateor_visited.append(i)
            dfs()
            operateor_visited.pop() # 현재 연산자를 제거하여 다른 연산자 조합을 시도할 수 있도록 합니다.

# dfs 함수 호출
dfs()
# 최대값과 최소값 출력
print(top)
print(low)

2. 백트래킹을 추가한 코드