[BOJ] #14888. 연산자 끼워넣기 (Python)

mingguriguri·2022년 10월 30일

DFS python 백준 알고리즘

Python으로 공부하는 Algorithm

목록 보기

4/10

#14888. 연산자 끼워넣기

링크: https://www.acmicpc.net/problem/14888
유형: 백트래킹, 브루트 포스(완전탐색)
작성일시: 2022년 10월 28일 오후 7:23

📃문제 : #14888. 연산자 끼워넣기

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.
- 1+2+3-4×5÷6
- 1÷2+3+4-5×6
- 1+2÷3×4-5+6
- 1÷2×3-4+5+6
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.
- 1+2+3-4×5÷6 = 1
- 1÷2+3+4-5×6 = 12
- 1+2÷3×4-5+6 = 5
- 1÷2×3-4+5+6 = 7
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 최댓값과 최솟값이 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

문제분석

앞서, 이 문제는 재귀함수 개념을 잡기 좋은 문제

📍 수와 수 사이에 연산를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 순서를 바꾸면 안된다.

1+2+3-45/6
1/2+3+4-56

피연산자와 연산자의 배치로 해야 함.
피연산자는 고정되어야 함
연산자는 고정 필요 없음
- 순열과 조합 [우리에게 순서가 필요한가??]
  - 순열 : 순서 필요
  - 조합 : 순서 필요 X
순열이란?
서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것
조합이란?
서로 다른 n개의 원소에서 r개를 중복과 순서에 상관없이 선택 혹은 나열

⇒ 우리는 순서가 상관이 있음. 연산을 한 후, 최대 최소를 구해야 하기 때문

우리는 순서가 상관이 있으나, 모든 경우의 수를 다 고려해야 함.

📍 연산자 우선 순위를 무시하고 앞에서부터 진행한다. 📍 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구해야 한다.

마지막에 max(), min()을 이용해야 한다.

입력

N (입력개수) → int num

A1~An (원소) → nums (피연산자) → list로 구현

공백을 둔 채로 받아야 함 → split()

+, -, *, / 개수 → int list(연산자)

마찬가지로 split()필요

번외 ) 실제로 코딩테스트에서 많이 쓰는 리스트화 : list(map(int, input().split()))

입력

띄어쓰기로 구분된 여러 개의 문자 입력값을 리스트에 넣고 싶은 경우 list()이용
```
s = list(input().split())
print(s)
```
띄어쓰기로 구분된 여러 개의 숫자 입력값을 리스트에 넣고 싶은 경우 map()
```
num = list(map(int, input().split()))
print(num)
```
엔터로 구분된 여러 개의 문자(or 단어) 입력값을 리스트에 넣는 경우, for문 사용
```
N = 5
list1 = []
for i in range(N):
	list1.append(input())

print(list1)
```

map()을 왜 쓰는가?

하나의 값을 다른 값으로 대응시키는 의미. 지도를 뜻하는 map에서 나온 말이다.

지도에 표시한 정보가 현실세계와 1:1로 대응하듯이, 매핑을 통해 하나의 값을 다른 값으로 1:1 대응시킨다.

출처 : http://wiki.hash.kr/index.php/매핑

출력

(-10억≤n≤10억)

cf.

1e9 = $1*10^9$ = 1000000000
2e9 = $2*10^9$ = 2000000000
- int형에서 무한대값을 나타내기 위해 사용

최댓값 → max_value = -1e9

최솟값 → min_value = 1e9

💭과정

일단 해보자!

백트래킹이 뭐야?

모든 경우의 수를 전부 고려하는 알고리즘 (일종의 트리 탐색 알고리즘)
장점 : 생각을 하지 않아도 짤 수 있음 (DFS를 사용하면 답이 나옴)
방식
- 깊이우선탐색( Depth First Search, DFS) : 자식 노드 먼저 탐색 (ex. 미로탈출)
- 너비우선탐색(Breath First Search, BFS) : 형제 노드 먼저 탐색 (ex. 최단거리 탐색)
- 최선 우선 탐색(Best First Search) → 거의 사용X

반복문이 너무 많이 생길 것 같을 때 → 백트래킹 이용

백트래킹 풀이법

재귀함수 종료시점 지정
대체로 종료시점 이후 for문 등장함
for문 안에 각각의 경우에 대해 값을 바꿔가며 재귀호출
시간 초과를 막기 위해 모든 for문을 돌지 않고, 특정 경우에만 실행하도록 가지치기

DFS (Depth First Search)

탐색 트리에서 특정 노드를 방문해 확인한 후, 바닥에 도달할 때까지 한 쪽 방향으로만 내려간다. 그 후 더 이상 방문할 곳이 없으면 이전 상태로 되돌아가는 탐색방법이다.
이때 탐색과정이 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용한다.
깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 부모노드로 되돌아(백트래킹 backtracking)와서, 부모노드에서 이전과는 다른 자식노트를 선택해 방문한다.
넓게 탐색하기 전에 ‘깊게’ 탐색한다.
- ex. 미로찾기
- 한 방향으로 가다가 막다른 길에 도착하면(트리의 바닥에 도착) 왔던 길을 돌아가 다른 방향으로 감 -> 목표지점이 나올 때까지 반복
사용하는 경우 : 모든 노드를 방문(브루트 포스, Brute Force)하고자 할 때!
- 간단 : DFS > BFS
- 속도 : DFS < BFS
구현
- 재귀함수 or 스택(재귀함수가 익숙하지 않을 경우)
- 즉, LIFO(Last In First Out)구조
기본원리 : "앞으로 찾아야 가야할 노드"와 "이미 방문한 노드"를 기준으로 데이터를 탐색

BFS (Breath First Search)

모든 분기점을 다 검사하면서 진행하는 방식
깊게 탐색하기 전에 ‘넓게’ 탐색한다.
ex. 중범과 은지가 계단에서 가위바위보 게임을 할 때, 은지가 원하는 지점에 갈 수 있는 최소 승리 횟수는?
- DFS는 무한대로 빠져버림 + 시간 오래걸림
- BFS는 모든 분기를 검색하며 상태공간 탐색
최단거리 계산에 사용
구현 : 큐
- 검사하면서 발생하는 새로운 경우 → 큐
- 검사한 원소는 큐에서 뺌
가지치기를 제대로 안하면 DFS보다 더 빨리 오버플로우될 수 있음!

최선우선탐색(Best First Search)

BFS에서 발전한 방식
우선순위 큐로 구현
현재 가장 최적인 경우를 우선적으로 검사함

우리는 무엇을 써야할까? DFS? BFS?

DFS!

모든 경우의 수를 고려해야 한다.

구현 방법

1. 재귀함수

/*************재귀 호출을 이용한 DFS 코드*******************/
void DFS(int k){ //k번째 정점에 대해 탐색
	visited[k] = true; //방문 체크
	for(int i = 1; i <= n; i++){
		if(G[k][i] && !visited[i]){ //이웃 정점에 대해 방문하지 않은 노드 탐색
		DFS(i); //마지막으로 탐색한 노드부터 다시 탐색
		}
	}
	return; //k정점의 모든 인접 정점을 방문한 경우, 백트랙
}
출처: https://jjudrgn.tistory.com/8 [jjudrgn's note:티스토리]

2. 스택

/*************스택 구조를 이용한 DFS 코드*******************/
void DFS(int k){

	stackClass<int> DFS;
	DFS.pust(root); // 시작점 push
	visited[root] = 1;

	while(!DFS.isEmpty() && k != stack.GetTop()){
		if(All Adjacent Cities Are Visited){   // 인접 노드를 모두 방문한 경우
			stack.pop();
		}
		else{
			//인접 노드 중 하나를 선택
			stack.push(New);
			visited[New] = 1;
		}
	}
	if(stack.isEmpty()) cout<<"NO";
	else cout<<"YES"; 
}
출처: https://jjudrgn.tistory.com/8 [jjudrgn's note:티스토리]

알고리즘 문제 중 DFS 활용하는 문제를 풀어야할때 아래와 같은 기초 바탕 코드 사용하면 좋음

void dfs() {
	if(모든 조건 충족) {				//1
		결과 계산
	} else { 
	dfs()						//2
}

void dfs() {
	if(모든 조건 충족) {				//1
		결과 계산
	} else {
	arr[] = 					//2
	dfs()						//3
	arr[]==
}

void dfs() {
	if(모든 조건 충족) {				//1
		결과 계산
	} else {
	for() {	
		arr[] =					//2 
		dfs()					//3
		arr[]==
	}
}
출처: https://jjudrgn.tistory.com/8 [jjudrgn's note:티스토리]

💡힌트

함수의 매개변수에 무엇이 들어가야 할까 생각해보자!
재귀함수 종료조건은 무엇일지 생각해보자

🎯결과

DFS를 통해 구현해보자

내가 한 방법

import sys
# 수의 개수 입력받기
N = int(input())
# 수열 입력받기
nums = list(map(int, input().split()))
# 연산자 개수 입력받기
op = list(map(int, input().split()))

# 최댓값, 최솟값 초기화하기
max_value = -1e9
min_value = 1e9

# dfs 함수 정의
def solution(num, idx, add, sub, mul, div):

    global max_value, min_ans
		# 연산자를 모두 사용했을 경우, 다 탐색했기 때문에 최대최소 비교
		# 종료 조건에 해당
    if idx == N:
        max_value = max(max_value, num)
        min_value = min(min_value, num)
        return 

    # 연산자, 모든 경우 고려
		# 더하기
    if add > 0:
        solution(num + nums[idx], idx + 1, add - 1, sub, mul, div)
		# 빼기
    if sub > 0:
        solution(num - nums[idx], idx + 1, add, sub - 1, mul, div)
		# 곱하기
    if mul > 0:
        solution(num * nums[idx], idx + 1, add, sub , mul -1, div)
		# 나누기
		if div > 0:
        solution(int(num / nums[idx]), idx + 1, add, sub, mul, div -1)

# dfs 함수 호출
solution(nums[0], 1, op[0], op[1], op[2], op[3])
# 최댓값과 최솟값 결과 출력
print(max_value)
print(min_value)

다른 방법도 있나?

다른풀이#1. DFS 다른 풀이

import sys

# 수의 개수 입력받기
n = int(input())
# 수열 입력받기
data = list(map(int, input().split()))
# 연산자 개수 입력받기
add, sub, mul, div = map(int, input().split())

# 최댓값, 최솟값 초기화하기
max_value = -1e9
min_value = 1e9

# dfs 함수 정의
def dfs(i, arr):
    global add, sub, mul, div, max_value, min_value
		# 연산자를 모두 사용했을 경우, 다 탐색했기 때문에 최대최소 비교
		# 종료 조건에 해당
    if i == n:
        max_value = max(max_value, arr)
        min_value = min(min_value, arr)
        return 
    else: 
    # 연산자, 모든 경우 고려
		# 더하기
        if add > 0:
            add -= 1
            dfs(i+1, arr + data[i])
            add += 1
		# 빼기
        if sub > 0:
            sub -= 1
            dfs(i+1, arr - data[i])
            sub += 1        
        # 곱하기
        if mul > 0:
            mul -= 1
            dfs(i+1, arr * data[i])
            mul += 1		
        # 나누기
		if div > 0:
            div -= 1
            dfs(i+1, int(arr / data[i]))
            div += 1

# dfs 함수 호출
dfs(1, data[0])

# 최댓값과 최솟값 결과 출력
print(max_value)
print(min_value)

출처 : https://data-flower.tistory.com/72

다른풀이 #2. 순열을 이용한 방법

# 순열 (Python3 시간초과 / PyPy3는 통과)
import sys
from itertools import permutations

input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
op_num = list(map(int, input().split()))  # +, -, *, /
op_list = ['+', '-', '*', '/']
op = []

for k in range(len(op_num)):
    for i in range(op_num[k]):
        op.append(op_list[k])

maximum = -1e9
minimum = 1e9

def solve():
    global maximum, minimum
    for case in permutations(op, N - 1):
        total = num[0]
        for r in range(1, N):
            if case[r - 1] == '+':
                total += num[r]
            elif case[r - 1] == '-':
                total -= num[r]
            elif case[r - 1] == '*':
                total *= num[r]
            elif case[r - 1] == '/':
                total = int(total / num[r])
	
        if total > maximum:
            maximum = total
        if total < minimum:
            minimum = total

solve()
print(maximum)
print(minimum)

출처 :

[BOJ 14888] 연산자 끼워넣기 (Python)

순열의 경우, 시간이 오래걸림

🧐회고

재귀함수의 개념 자체는 쉽게 느껴졌는데, 막상 문제에 적용해보니까 이해하는데 오래걸렸다. 매개변수가 여러 개로 늘어나고 연산을 하니까 헷갈렸다. 그리고 동시에 진행된다는 것을 이해를 못했었다. 그래도 이 문제를 통해 재귀함수에 대한 개념을 잡은 것 같다.
(실제로 이 문제가 재귀함수에 대한 개념을 잡기 좋은 문제라고 한다.)
이번 주에 내가 준비해 간 이 문제는 팀원들에게 개념과 문제가 잘 이해되지 않은 상태에서 힌트도 구체적으로 주지 않아 문제 푸는 것에 어려움이 있었던 것 같다. 다음부터는 스터디 구성을 1) 어떻게 해야 이해하기 쉬운 방향으로 갈지, 2) 힌트는 어떻게 구체적으로 줄지 고민해봐야겠다.
(불필요한 설명은 다 빼기)

mingguriguri

To be "irreplaceable"

이전 포스트

[BOJ] #9655. 돌게임1 (Python)

다음 포스트