No Limitation
[Back Tracking] 연산자 끼워넣기 - 백준 본문
https://www.acmicpc.net/problem/14888
백트래킹 문제는 보통 모든 경우를 시뮬레이션 하여 Brute force하게 문제를 풀어나가는 방법으로 접근을 시도.
퍼즐 문제를 푸는 유형들이 그러하였고 이 문제 역시 연산자들의 input 경우의 수가 많고 랜덤하기에 수많은 경우를 무식하게 때려박아 보는 방법으로 접근을 시도할 수 있다.
즉, 수많은 경우의 수를 가지고 문제를 풀어야 할 경우
Brute Force하게 접근을 해야하며 백트래킹 문제는 이를 Recursion을 활용하여 잘 구현을 해야한다.
또한 문제를 푸는 것만큼 중요한 게 이 문제가 바로 Back Tracking 유형인 지를 먼저 파악할 줄 아는 연습이 필요하다.
Solution
문제 풀이는 다음과 같이 접근을 시도.
주어진 숫자의 배열은 일정하고 연산자의 수는 (수의 갯수-1)만큼 이므로 연산자를 숫자들 사이에 랜덤하게 끼워 맞출 때 가장 값을 크게하는 경우와 작게 하는 경우를 찾는 알고리즘이다.
문제의 조건을 보면 숫자의 경우 2~11개 사이이고 수의 값은 1~100 이내의 값이다.
경우의 수를 보면
숫자가 N개 주어지고 연산자가 N-1개 주어진다고 하면
최악의 경우 N-1개를 N-1개 자리에 하나씩 넣어보는 시뮬레이션을 돌려야 하므로 (N-1)!의 경우의 수가 나오게 됨. 즉, O(n!)의 알고리즘이 나오므로 매우 경우의 수가 많은 문제라는 것을 파악.
→ 즉 이 문제는 백트래킹으로 브루트 포스하게 풀어야 함...!
우선 3번째 행은 각각 덧셈, 뺄셈, 곱셈, 나눗셈의 수를 나타내므로 이를 사용할 수 있는 연산자 형태로 바꾸어주었다.
예를 들어
[ 2, 0, 1, 2 ] 이렇게 주어진다고 하면
덧셈이 0, 뺄셈이 1, 곱셈이 2, 나눗셈이 3으로 labeling을 하면
[ 0, 0, 2, 3, 3 ] → 이렇게 갯수를 구해주어 새로운 연산자 배열 oper_list를 만들어준다.
이렇게 되면 연산자의 목록을 재정의하고 주어진 숫자 배열 num에서 랜덤하게 넣어보는 시뮬레이션을 구현하면 된다.
시뮬레이션은 다음과 같다.
다음 테스트 케이스를 생각해보자
이 경우 oper_list는 다음과 같이 정의되고
숫자 배열이 다음과 같이 정의가 되서 숫자들 사이에 연산자를 배치하는 과정을 거친다.
처음의 경우 맨 첫번째 연산자인 0(더하기)을 집어넣는다고 가정하면
다음과 같이 덧셈을 수행하고
덧셈을 수행한 결과는 새로운 first로 갱신이 된다.
oper_list 역시 처음 연산자 0을 사용하였으므로 그것을 제외한 나머지를 새로운 oper_list의 파라미터로 넘기게 된다. 여기서 재귀 함수를 시행해준다.
여기까지는 단순한 DFS 논리랑 비슷한데
중요한 점은 연산자 0이 처음 1과 2 사이에만 들어가라는 법이 없다.
즉 처음 연산자 0은 3이나 4 혹은 5나 6 사이에도 들어갈 수 있다.
이런 모든 경우의 수를 고려하기 위해
for 반복문을 통해 처음 0이 1과 2만이 아닌
3과 4 사이에도 들어가 recursion를 시작하는 방법을 통해 문제를 풀었다.
그렇게 하여 가장 Max, Min인 경우를 찾아주어 문제를 풀었다.
또한 문제에서 boundary를 -10억부터 10억까지 설정해주었으므로 Min, Max를 초기에 다음과 같이 설정해주었다.
문제 풀이 코드는 다음과 같다.
### input 처리
# 숫자의 갯수
N = int(input())
# 숫자 배열
num = [int(x) for x in input().split()]
# 연산자 수
oper = [int(x) for x in input().split()]
### 연산자의 리스트로 변환 과정 -- 숫자의 갯수를 n이라고 할 때 O(4(n-1))
oper_list = [i for i in range(len(oper)) for _ in range(oper[i])]
# 숫자 목록에서 다음 연산할 숫자를 가리키는 index
limit = 0
### 연산 수행 함수
def do_operate(first, second, op) :
if op == 0 : return first+second
elif op == 1 : return first-second
elif op == 2 : first*second
else :
if first < 0 :
return (first*(-1))//second)*(-1)
return first//second
### Do back tracking - O(n!) in worst case
def operate(first, second, op_list, limit, Max, Min) :
for idx range(len(op_list)) :
new = do_operate(first, second, op_list[idx])
# 연산할 수가 2개밖에 없는 경우
if limit == len(num)-2 :
return new, new
if idx < len(op_list) -1 :
result = operate(new, num[limit+2], op_list[:idx]+op_list[idx+1:], limit+1, Max, Min)
else : # 연산자가 마지막 한개 남은 경우
result = operate(new, num[limit+2], op_list[:idx], limit+1, Max, Min)
if Max < result[1] :
Max = result[1]
if Min > result[0] :
Min = result[0]
return Min, Max
mins, maxs = operate(num[limit], num[limit+1], oper_list, limit, -1000000000,1000000000)
print(maxs)
print(mins)
Time compleixty
최악의 경우 O(n!)이 아닐까 싶음
'프로그래밍' 카테고리의 다른 글
[구현, 시뮬레이션] 2개 이하로 다른 비트 - 프로그래머스 (0) | 2022.02.12 |
---|---|
[Back Tracking, 완전탐색] 약수의 갯수와 덧셈 - 프로그래머스 (0) | 2022.02.12 |
[Graph, DP] 점프 - 백준 (0) | 2022.02.12 |
[Graph, DFS, DP] 내리막길 - 백준 (0) | 2022.02.12 |
[Graph, BFS] 벽 부수고 이동하기 - 백준 (0) | 2022.02.12 |