문제 자체는 정말 간단하지만, 풀이는 그렇지 못한 것...😭
숫자가 주어지면, 수 들 사이에 주어진 연산자들의 갯수만큼 연산자를 끼워넣는 문제이다.
그래서 나올 수 있는 최댓값과 최솟값을 구하는 문제인데, 뭔가 for문으로 N중 노가다를 해서 구할 수 있을 거 같아서 그럴까?! 했다가 백트래킹 연습 중이라 백트래킹으로 구현해보았다.
(사실, 스도쿠 문제 풀다가 화나서 쉬는 겸 이 문제 먼저 시도했는데, 얘도 만만하지 않아서 더 화가 났다는거...)
백트래킹의 구조
다시 기초로 돌아가서 백트래킹의 구조를 한번 생각해보겠다.
우리가 사용하는 백트래킹은 기본적으로, 분기의 끝이 존재한다.
예를 들면, N개의 수열을 골라낸다 라고 하면 N번째 단계의 수를 고르면 그 분기는 끝이 나고 이전 분기로 돌아가야 한다.
그래서 그 분기의 끝에 도달했을 때, 값을 추가 해주고 진행을 해야하는 것이다.
그래서 백트래킹의 구조를 나는
function:
if (분기의 끝단계인가?):
해당하는 값 추가
return
[분기를 진행시킬 반복문]
[분기 탈출 시,
즉 이전 단계로 돌아올 시
분기의 진행에 쓰였던 변수의 원상복구]대략적으로 이런 구조를 가지고 있다고 생각한다.
그걸 토대로 이 문제를 생각하고 풀어보았다
풀이
생각보다 문제 자체는 어려운게 아니라서, 되게 이상한 부분에서 틀린거말고는 코드를 잘 써내려간 것 같다.
선언한 변수들을 보자
N : 입력받을 수의 갯수
num_list : 입력받을 수들 배열
operator : 입력받을 연산자들 배열
sum_list : 분기의 끝단계에 도달했을 때, 합쳐진 값을 저장할 배열
sum : 분기마다의 합으로 쓰일 변수
tmp : 분기가 끝나고, 원상복구 시켜주기 위한 변수
이제 코드를 보자
def func(num):
global sum
if num == N:
sum_list.append(sum)
return
for i in range(len(operator)):
if operator[i] != 0:
if i == 0:
tmp = sum
sum += num_list[num]
operator[i] -= 1
func(num+1)
operator[i] += 1
# sum -= num_list[num]
sum = tmp
elif i == 1:
tmp = sum
sum -= num_list[num]
operator[i] -= 1
func(num+1)
operator[i] += 1
# sum += num_list[num]
sum = tmp
elif i == 2:
tmp = sum
sum *= num_list[num]
operator[i] -= 1
func(num+1)
operator[i] += 1
# sum = sum // num_list[num]
sum = tmp
elif i == 3:
tmp = sum
if sum < 0:
sum = (abs(sum) // num_list[num]) * (-1)
else:
sum = sum // num_list[num]
operator[i] -= 1
func(num+1)
operator[i] += 1
sum = tmp
N = int(input())
num_list = list(map(int, input().split(" ")))
operator = list(map(int, input().split(" ")))
tmp = 0
sum_list = []
sum=num_list[0]
func(1)
print(max(sum_list))
print(min(sum_list))입력을 받고, 처음 sum에는 이미 첫번째 숫자인 num_list[0]이 들어가 있다.
그러한 이유는 연산자를 넣을 때 맨앞자리는 넣을 필요가 없기에, 맨앞자리 이후부터 생각하기 위해서이다.
함수 안에서는 sum을 전역변수로 선언하여 사용해주고, 함수를 시행한다.
맨 처음부터 보자,
위에서 말한 기본적인 구조에 맞게,
if num == N:
sum_list.append(sum)
return인덱스로 들어갈 수(num)가 숫자들의 끝(N)에 도달하게 되면, 지금까지 계산해왔던 sum을 sum_list에 넣는 조건문을 구성했다.
두번째는, operator에 들어간 숫자들은, 연산자들의 갯수이다.
각각의 수 들은
+, - *, ÷ 순서로 갯수가 지정되어있다.
케이스들에 대해서 반복을 돌아보자 이제
for i in range(len(operator)):
if operator[i] != 0:
if i == 0:
tmp = sum
sum += num_list[num]
operator[i] -= 1
func(num+1)
operator[i] += 1
# sum -= num_list[num]
sum = tmpfor반복문을 통해서, operator 배열을 다 돌아준다.
opreator에 들어온 값이 0 이 아니면, 즉 연산자의 갯수가 0이 아니면, 아래를 시행하자.
위에서 말했던, index에 따라서 연산하는 방법이 다르니, 인덱스에 따른 조건문을 만들어주고 그 케이스에 맞게 수행해줘야한다.
일반적으로 구현하는 내용은 같으니 덧셈을 할 때를 보겠다.
i = 0 일 때,
tmp = sum 을 먼저 해준다.
sum이 들어오면 일단 저장을 해주는 것이다.
왜냐하면 재귀를 빠져나왔을 때, 원래의 값으로 돌아오기 위해서인데, 그 방법에는
- 들어온 값을 저장해놓았다가, 다시 배정해주는 법
- 연산을 한 것의 역연산을 통해 구하는 법
이 두가지 방법이 있다. 하지만 첫번째의 방법을 택한데는 다 이유가 있다.
그건 좀 나중에 설명하겠다.
그리고 이제 그 후로 sum += num_list[num] 을 통해서 sum에다가 해당하는 인덱스의 수를 더해준다.
연산을 했기에, operator[i] -= 1을 통해서 해당 연산자의 갯수를 하나 줄여준다.
그 후 func(num+1)을 통해서 다음 인덱스의 수에 대한 재귀를 넘겨준다.
재귀를 빠져나온 후로는, 원상복귀의 과정이 필요한데operator[i] += 1를 통해 해당 인덱스의 연산자의 갯수를 하나 더해주고
아까 저장해두었던, 임시변수 tmp의 값을 sum에 다시 대입해준다.
다시 처음에 쓴 코드인
if num == N:
sum_list.append(sum)
return를 통해서 끝에 도달하면, sum에 추가하고 끝낸다.
문제점
다른 연산들은 다 괜찮았지만, 자꾸 나누기가 포함된 연산을 하게 되면 답이 오차가 엄청 크게 나오는 것이었다.
디버깅을 해도 도대체 문제가 없이 계산이 잘 나와서, 무엇이 틀린지 몰랐는데 문제를 다시 잘 읽어봤더니
나눗셈은 정수 나눗셈으로 못만 취한다. 음수를 양수로 나눌 때는, 양수로 바꿔주고 몫을 취하고 그 몫을 음수로 바꿔준다.
라는 C++ 나눗셈의 방식을 이용한다고 나와있었다.
그래서 이게 다르게 나오나 해서 파이썬에서 음수의 나눗셈을 해보니, 파이썬은 다르게 하더라..ㅋ
예를 들어 파이썬 같은 경우는
으로 계산한다. 아마 일반적인 계산과 같이, 나머지가 양수인 케이스로 생각을 해서 계산하는 것 같았다.
그런데 저 계산법으로 구현을 하면
이런 계산 결과가 나오게 된다.
그래서 나눗셈 과정에서 다른 방법이 필요하였다.
elif i == 3:
tmp = sum
if sum < 0:
sum = (abs(sum) // num_list[num]) * (-1)
else:
sum = sum // num_list[num]
operator[i] -= 1
func(num+1)
operator[i] += 1
sum = tmp나눗셈을 위한 인덱스가 넘어가게 되면(i=3)
sum 값이 음수인지 양수인지부터 판단한다.
양수이면, 나눗셈의 몫연산을 그냥 하지만
음수이면, sum의 절댓값을 몫연산을 해주고, 음의 부호를붙여주는 방식으로 하였다.
이 과정에서 역연산이 되게 복잡하기 때문에, 위에서 언급했던 임시변수tmp를 통해서 sum을 저장해두었다가, 나중에 다시 대응시켜주는 방식으로 해결한 것이었다.
마치며
요즘 백트래킹 연습차 문제를 풀어보고 있는데, 어렵다...
이 문제도 고민을 조금 오래 하게 된 것같다.
고민을 하면서, 백트래킹이 어떤식으로 돌아가는지 모르겠으면, 절차마다 필요한 변수들을 출력해보는 디버깅을 통해서 여러번 관찰해보는 것이 중요한 것 같다.
감이 잡히지않을 때, 확실히 디버깅을 하면 머리속에 구조가 그려지는 것 같다.
Python3랑 PyPy3 로 둘 다 넣어봤는데, Python이 훨씬 빠르게 나왔다. 참고..
