📚문제: #4008 숫자 만들기(모의 SW 역량테스트)
전체 코드
시간초과 알고리즘
# 4008. 숫자 만들기
# 순서가 영향을 끼치므로 순열을 구한다.
from math import ceil
# 백트래킹 재귀함수
def Backtracking(n, cal):
# 계산 결과를 담는 배열
global max_val
global min_val
# 계산이 끝나는 조건
if n == N-1:
max_val = max(max_val, cal)
min_val = min(min_val, cal)
return
for i in range(N-1):
# 이미 방문된 연산자면 Skip
if op_visited[i]:
continue
sign = op_code[i]
# 해당 부호 방문처리
op_visited[i] = True
if sign == '+':
Backtracking(n+1, cal+number[n+1])
elif sign == '-':
Backtracking(n+1, cal-number[n+1])
elif sign == '*':
Backtracking(n+1, cal*number[n+1])
elif sign == '/':
if cal >= 0:
Backtracking(n+1, cal//number[n+1])
else:
Backtracking(n+1, ceil(cal/number[n+1]))
# 해당 부호 방문해제
op_visited[i] = False
# 테스트 케이스의 개수 T
T = int(input())
# T개의 테스트 케이스가 주어진다.
for t in range(1, T+1):
# 최대, 최소 변수초기화
max_val = -int(1e10)
min_val = int(1e10)
# 숫자의 개수 N
N = int(input())
# 연산자 카드의 개수가 주어진다.
op_num = list(map(int, input().split()))
# N개의 숫자가 주어진다.
number = list(map(int, input().split()))
# 연산자 리스트
op_code = []
for i in range(4):
if i == 0:
for _ in range(op_num[i]):
op_code.append('+')
elif i == 1:
for _ in range(op_num[i]):
op_code.append('-')
elif i == 2:
for _ in range(op_num[i]):
op_code.append('*')
elif i == 3:
for _ in range(op_num[i]):
op_code.append('/')
# 방문여부 리스트
op_visited = [False] * (N-1)
# 함수 실행
Backtracking(0, number[0])
# 답안 출력
print("#{} {}".format(t, max_val-min_val))통과한 알고리즘
# 4008. 숫자 만들기
# 순서가 영향을 끼치므로 순열을 구한다.
from math import ceil
# 백트래킹 재귀함수
def Backtracking(n, cal):
# 계산 결과를 담는 배열
global max_val
global min_val
# 계산이 끝나는 조건
if n == N-1:
max_val = max(max_val, cal)
min_val = min(min_val, cal)
return
for i in range(4):
# 더 이상 사용할 수 없는 연산자면
if not op_num[i]:
continue
# 사용할 수 있는 연산자면 해당 부호 방문처리
op_num[i] -= 1
# 덧셈
if i == 0:
Backtracking(n+1, cal+number[n+1])
# 뺄셈
elif i == 1:
Backtracking(n+1, cal-number[n+1])
# 곱셈
elif i == 2:
Backtracking(n+1, cal*number[n+1])
# 나눗셈
elif i == 3:
if cal >= 0:
Backtracking(n+1, cal//number[n+1])
else:
Backtracking(n+1, ceil(cal/number[n+1]))
# 해당 부호 방문해제, 원복
op_num[i] += 1
# 테스트 케이스의 개수 T
T = int(input())
# T개의 테스트 케이스가 주어진다.
for t in range(1, T+1):
# 최대, 최소 변수초기화
max_val = -int(1e10)
min_val = int(1e10)
# 숫자의 개수 N
N = int(input())
# 연산자 카드의 개수가 주어진다. 순서대로 덧셈, 뺄셈, 곱셈, 나눗셈 부호의 개수
op_num = list(map(int, input().split()))
# N개의 숫자가 주어진다.
number = list(map(int, input().split()))
# 함수 실행
Backtracking(0, number[0])
# 답안 출력
print("#{} {}".format(t, max_val-min_val))TIL
N의 최대값은 12이기 때문에 순열 개념을 사용했을 때 최대 12!의 부호 순서열이 만들어진다. 이는 시간초과로 이어지므로 순열 대신
백트래킹개념을 사용한다.
백트래킹을 사용했음에도 불구하고 시간초과가 난 부분에 대해서는 아래 설명과 같다.
첫 번째 알고리즘의 문제점
1. 이중 루프 구조 사용: 첫 번째 알고리즘에서 for i in range(N-1)는 잠재적으로 최대 N−1번의 반복을 수행할 수 있습니다. 이는 각 연산자 위치에 대해 모든 가능한 위치를 매번 검사하는 것을 의미합니다. 연산자의 순서가 실제 계산에 큰 영향을 주지 않음에도 불구하고, 모든 위치를 순회하려고 하므로 비효율적일 수 있습니다.
2. 부적절한 방문 처리: op_visited 배열은 각 연산자의 사용 여부를 추적합니다. 그러나 이 배열은 매번 모든 위치를 검사하므로, 매우 많은 중복 검사를 수행하게 됩니다. 이는 특히 N이 크거나 가능한 연산자의 조합이 많을 때 비효율적입니다.
두 번째 알고리즘의 개선점
1. 연산자 기반 루프: 두 번째 알고리즘에서 for i in range(4)는 연산자의 종류(덧셈, 뺄셈, 곱셈, 나눗셈)만을 순회합니다. 이는 실제 사용 가능한 연산자의 수만큼 반복하므로, 각 연산자가 남아있는지만 확인하면 됩니다. 이로 인해 검사의 효율성이 크게 향상됩니다.
2. 실제 사용 가능한 연산자에 초점을 맞춘 방문 처리: op_num 배열은 각 연산자가 남아 있는 수를 직접 추적합니다. 이를 통해 위치(Index) 검사 없이 바로 해당 연산자를 사용할 수 있는지 판단하고, 사용 후에는 원상 복구하는 방식으로 동작합니다. 이 접근법은 필요한 검사만 수행하므로 계산 시간을 줄이는 데 큰 도움이 됩니다.
결론
두 번째 알고리즘은 각 연산자의 사용 가능 여부를 직접적으로 관리함으로써 불필요한 검사를 줄이고, 더 빠르고 효율적인 탐색을 가능하게 합니다. 첫 번째 알고리즘에서 발생할 수 있는 시간 초과는 주로 많은 불필요한 반복과 비효율적인 검사에서 비롯됩니다. 따라서, 특히 복잡하거나 큰 문제에서는 두 번째 알고리즘의 접근 방식이 시간 초과를 방지하는 데 훨씬 유리합니다.
