[boj 14888.python] '연산자 끼워넣기' 파이썬 풀이 (feat. 브루트포스, DFS 비교)

Algorithm/BaekJoon

[boj 14888.python] '연산자 끼워넣기' 파이썬 풀이 (feat. 브루트포스, DFS 비교)

쉬지마 이굥진 2024. 12. 3. 18:41

https://www.acmicpc.net/problem/14888

문제

출력

문제 접근

문제 난이도 자체는 어렵지 않은 문제였다.

처음에는 브루트포스(완탐)와 DFS 사이에서 고민하다가, DFS로 구현하려면 각 연산자를 선택하는 과정을 재귀 호출로 구현해야 할 것 같았다. 아직 그 부분은 미흡해서 브루트포스로 풀 수 있을까? 하고 고민했는데 ,,

그래서 시간 복잡도를 계산해 봤다. N - 1개의 연산자에 대해 가능한 모든 순열을 생성해야 하니까, 경우의 수는 (N - 1)!과 같을거다.

'입력'에서 N의 조건을 보면 N의 최대값은 11 이다. 즉, 최대 경우의 수는 10! = 3,628,800이라는 말 ! 그래서 이 문제의 경우는 브루트포스로도 충분히 풀 수 있을 거라고 판단해 브루트포스 방법을 채택해서 문제를 풀기로 했다.

구현 코드 (브루트포스)

from itertools import permutations

# 입력 받기
n = int(input())
numbers = list(map(int, input().split())) # 숫자 리스트
operator_count = list(map(int, input().split())) # 연산자 갯수: [+, -, *, /]

# 연산자 리스트 생성
operators = []
for i, op in enumerate(["+", "-", "*", "/"]):
    operators.extend([op] * operator_count[i])

# 모든 연산자 순열 생성
operator_permutations = set(permutations(operators, n - 1))

# 계산 함수
def calculate(numbers, operators):
    result = numbers[0]
    for i in range(len(operators)):
        if operators[i] == "+":
            result += numbers[i + 1]
        elif operators[i] == "-":
            result -= numbers[i + 1]
        elif operators[i] == "*":
            result *= numbers[i + 1]
        elif operators[i] == "/":
            # 나눗셈은 정수 몫만 취함
            if result < 0:
                result = -(-result // numbers[i + 1])
            else:
                result //= numbers[i + 1]
    return result

# 최댓값과 최솟값 계산
max_result = -float('inf')
min_result = float('inf')

for ops in operator_permutations:
    result = calculate(numbers, ops)
    max_result = max(max_result, result)
    min_result = min(min_result, result)

# 결과 출력
print(max_result)
print(min_result)

코드 설명

입력 처리: 일단 N 개의 숫자와 N - 1개의 연산자 개수를 입력받는다.
연산자 순열 생성:
- 주어진 연산자 개수( ["+", "-", "*", "/"])를 바탕으로 연산자를 리스트로 생성한다.
- itertools.permutations 라이브러리를 사용해서 가능한 모든 연산자 순열을 생성한다.
수식 계산:
- 이제 calculate 메서드를 따로 만들어서, 각 연산자 순열에 대해 숫자 리스트를 순차적으로 계산한다.
- 나눗셈 연산은 문제 조건에 따라 C++ 방식으로 처리했다.
최댓값 및 최소값 갱신:
- 계산 결과를 비교해서 최대값 및 최소값을 갱신해줬다.
- 최대값은 음수 무한대를 이용해서 초기화해줬고, 최소값은 양의 무한대를 이용해서 초기화했다.

결과

깔끔하게 통과!

디벨롭

통과를 하고 나서 생각해보니, 역시 브루트포스로 풀면 시간복잡도 측면에서 매우 불리한 코드가 된다.

시간 복잡도는 최악의 경우를 기준으로 순열의 개수를 (n - 1)! 로 쳤을 때,

O((n - 1) * (n - 1)! 이 된다.

▪️n = 5인 경우
4 * 4! = 4 * 24 = 96

▪️ n = 10인 경우
9 * 9! = 9 * 362,880 = 3,265,920

그니까 다시 말하면, n이 커지면 커질수록 팩토리얼의 증가율로 인해서 시간 복잡도가 매우 빠르게 커진다는 점 .. 이 문제의 경우 n <= 11과 같은 제한 조건이 있었기 때문에 실행 가능한 수준으로 유지된 것이지 n의 제한 조건이 없다면 비효율적인 풀이 방법이란 소리다.

리팩토링

그럼 아까 문제 접근 단계에서 생각만 해봤던 DFS를 적용해보자. (재귀 호출이 아직은 익숙치않아서 리팩토링을 하다가 구글링 및 짱피티의 도움을 받았다)DFS (Depth-First Search)는 트리 또는 그래프를 깊이 우선 탐색으로 탐색하는 알고리즘이고, 재귀적 또는 스택 기반으로 구현된다. 위에서 permutations를 사용해 완전 탐색으로 푼 방법을 여기에서는 재귀 호출로 각 연산자를 선택하는 과정을 구현했다고 생각하면 될 것 같다.

구현 코드 (DFS)

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

max_result = -float('inf')
min_result = float('inf')

def dfs(idx, current_result, plus, minus, multiply, divide):
    global max_result, min_result
    if idx == n:  # 모든 숫자를 다 사용했으면 결과 갱신
        max_result = max(max_result, current_result)
        min_result = min(min_result, current_result)
        return

    # 각 연산자를 사용해 다음 재귀 호출
    if plus > 0:
        dfs(idx + 1, current_result + numbers[idx], plus - 1, minus, multiply, divide)
    if minus > 0:
        dfs(idx + 1, current_result - numbers[idx], plus, minus - 1, multiply, divide)
    if multiply > 0:
        dfs(idx + 1, current_result * numbers[idx], plus, minus, multiply - 1, divide)
    if divide > 0:
        dfs(idx + 1, int(current_result / numbers[idx]), plus, minus, multiply, divide - 1)

# DFS 시작
dfs(1, numbers[0], operator_count[0], operator_count[1], operator_count[2], operator_count[3])

print(max_result)
print(min_result)

숫자 리스트와 남은 연산자의 개수를 기반으로, 재귀를 통해 하나씩 연산을 수행한다. 연산 결과를 넘기며 다음 연산자로 분기하는데, 현재 상태에서 가능한 경우만 탐색하고 재귀 호출을 통해 순차적으로 계산하는 것이 특징이다. 코드의 자세한 설명이 필요하다면 아래 코드 설명 칸을 보시라!

코드 설명

💡dfs 함수 정의

def dfs(idx, current_result, plus, minus, multiply, divide):
    global max_result, min_result
    if idx == n:  # 모든 숫자를 사용했으면 결과 갱신
        max_result = max(max_result, current_result)  # 최댓값 갱신
        min_result = min(min_result, current_result)  # 최솟값 갱신
        return

idx: 현재 계산할 숫자의 인덱스.
- 예를 들어, numbers[idx]는 현재 계산에서 사용할 숫자다.
current_result: 지금까지 계산한 결과.
plus, minus, multiply, divide: 각 연산자의 남은 개수.
종료 조건: 모든 숫자(numbers)를 사용했으면(idx == n), 계산 결과를 최댓값과 최솟값으로 갱신하고 종료한다.

💡 재귀 호출

    # 각 연산자를 사용해 다음 재귀 호출
    if plus > 0:
        dfs(idx + 1, current_result + numbers[idx], plus - 1, minus, multiply, divide)
    if minus > 0:
        dfs(idx + 1, current_result - numbers[idx], plus, minus - 1, multiply, divide)
    if multiply > 0:
        dfs(idx + 1, current_result * numbers[idx], plus, minus, multiply - 1, divide)
    if divide > 0:
        dfs(idx + 1, int(current_result / numbers[idx]), plus, minus, multiply, divide - 1)

현재 남아 있는 연산자의 개수를 확인한다. 연산자가 남아 있다면 그 연산자를 적용한 결과로 다음 재귀 호출을 진행한다.
각 연산자의 동작:
1. 덧셈 (+): current_result + numbers[idx]를 계산한 뒤, plus 개수를 하나 줄이고 DFS 호출.
2. 뺄셈 (-): current_result - numbers[idx]를 계산한 뒤, minus 개수를 하나 줄이고 DFS 호출.
3. 곱셈 (*): current_result * numbers[idx]를 계산한 뒤, multiply 개수를 하나 줄이고 DFS 호출.
4. 나눗셈 (/): 정수 나눗셈을 적용하며, Python의 나눗셈 처리에 맞게 양수와 음수를 다르게 처리:
  - int(current_result / numbers[idx]): 나눗셈 결과를 정수로 강제 변환.
  - 음수일 경우 Python에서는 자동으로 올림을 수행하므로 이를 고려했다.

💡 dfs 호출 시작

dfs(1, numbers[0], operator_count[0], operator_count[1], operator_count[2], operator_count[3])

시작은 idx=1로 두고, 첫 번째 숫자(numbers[0])를 초기 결과값으로 설정한다.
남아 있는 연산자 개수는 입력받은 연산자 개수를 그대로 사용한다.

결과

가히 충격적이었다 .. ㅋㅋ 브루트포스로 풀었을 때와 dfs로 풀었을 때 시간 차이가 거의 10배가 났다.

브루트포스 방식에선 모든 가능한 연산 순서를 명시적으로 생성하고 반복문으로 모두 탐색하는데 반해 DFS 방식에서는 현재 상태에서 가능한 경우만 탐색하기 때문에 이렇게 차이가 나는 것 같다.

시간 복잡도 비교

방식	시간 복잡도	효율 (입력 크기 증가에 따른 변화)
브루트포스	O((n - 1)! * n)	느림 (순열 생성이 비효율적이고 큰 n에서 급격히 느려짐)
DFS	O(4^(n - 1))	비교적 효율적 (분기가 4로 고정. 즉 큰 n에서도 덜 급격히 증가)

결론

연산자 끼워넣기 문제를 브루트포스와 DFS로 풀어보면서 느낀 점은 ..

브루트포스:
- 단순하고 구현이 쉬운 방식.
- n이 작을 때 적합.
- n이 커지면 순열 생성과 계산 비용이 급격히 증가.
DFS:
- n이 클 때 더 효율적.
- 중간 결과를 활용할 수 있어 계산 비용 절감 가능.
- 구현 난이도가 상대적으로 높다. (연습하자..)

N(입력값)의 최댓값을 따져보고, 브루트포스로는 풀리지 않을 문제가 분명 있으니 DFS을 통한 재귀 탐색 구현을 익혀두자! 오늘의 교훈.

'Algorithm > BaekJoon' 카테고리의 다른 글

[boj 2109.python] 백준 '순회강연' 풀이 (파이썬 런타임에러(ValueError) 해결) (2)	2024.12.20
[boj 2164.python] '카드2' 풀이 (시간초과 해결) (0)	2024.12.18
[boj 1092.python] '배' 풀이 (feat. 언어만 바꿔도 통과, Python3와 PyPy3의 차이) (0)	2024.09.23
[boj 1244.python] '스위치 켜고 끄기' 풀이 (0)	2024.01.15
[boj 1966.python] 프린터 큐 풀이 (1)	2024.01.04

현재글[boj 14888.python] '연산자 끼워넣기' 파이썬 풀이 (feat. 브루트포스, DFS 비교)

최고의 백엔드 개발자 (예정)