Jinho Tech

브루트포스 알고리즘 & 백트래킹 문제이다.

나누기 처리를 할 때 int(n1 / n2) 또는 -(-n1 / n2) 같은 방식으로 나눠야 하는데,

처음에 이걸 몰라서 계속 틀렸다.

def dfs(res, i, add, sub, mul, div):
    global N
    if i == N:
        res_li.append(res)
    else:
        if add:
            dfs(res + nums[i], i+1, add-1, sub, mul, div)            
        if sub:
            dfs(res - nums[i], i+1, add, sub-1, mul, div)
        if mul:
            dfs(res * nums[i], i+1, add, sub, mul-1, div)
        if div:
            dfs(int(res / nums[i]), i+1, add, sub, mul, div-1)          
    
N = int(input())
nums = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
res_li = []

dfs(nums[0], 1, add, sub, mul, div)
print(max(res_li))
print(min(res_li))

단순한 백트래킹 문제이다.

def dfs(depth):
    if depth == 6:
        print(*li)
        return ;
    for i in range(n):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        for j in range(i+1, n):
            check[j] = 0
        
while 1:
    t = list(map(int, input().split()))
    n, nums = t[0], t[1:]
    if n == 0:
        break
    li = []
    check = [0]*n
    dfs(0)
    print()

그냥 백트래킹 형식으로 쉽게 풀었다. 

def dfs(depth):
    if depth == k:
        s.add(''.join(map(str, li)))
        return ;
    for i in range(n):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        check[i] = 0
        
n, k = int(input()), int(input())
nums = [int(input()) for _ in range(n)]
li, s = [], set()
check = [0]*n
dfs(0)
print(len(s))

기본적인 백트래킹 문제이다. 15663번 N과 M (9)와 비슷한 문제이다.

def dfs(depth):
    if depth == M:
        s = ' '.join(map(str, li))
        if s not in d:
            d[s] = 1
            print(s)
        return ;
    for i in range(N):
        if depth == 0 or li[-1] <= nums[i]:
            li.append(nums[i])
            dfs(depth+1)
            li.pop()

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
d = {}; li = []
dfs(0)

기본적인 백트래킹 문제이다. 15663번 N과 M (9)와 비슷한 문제이다.

def dfs(depth):
    if depth == M:
        s = ' '.join(map(str, li))
        if s not in d:
            d[s] = 1
            print(s)
        return ;
    for i in range(N):
        li.append(nums[i])
        dfs(depth+1)
        li.pop()

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
d = {}; li = []
dfs(0)

기본적인 백트래킹 문제이다. 15663번 N과 M (9)과 비슷한 문제이다. 

def dfs(depth):
    if depth == M:
        s = ' '.join(map(str, li))
        if s not in d:
            d[s] = 1
            print(s)
        return ;
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        for j in range(i+1, N):
            check[j] = 0

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
d = {}; li = []
check = [0]*N
dfs(0)

기본적인 백트래킹 문제이다. 그냥 리스트를 사용해서 중복인지 아닌지 확인하면 무조건 시간초과가 나와서,

딕셔너리(해시)를 사용해서 풀었다. 해시는 진짜 진짜 진짜 엄청 빠르다!!

def dfs(depth):
    if depth == M:
        s = ' '.join(map(str, li))
        if s not in d:
            d[s] = 1
            print(s)
        return ;
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        check[i] = 0

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
d = {}; li = []
check = [0]*N
dfs(0)

브루트포스 알고리즘 & 백트래킹 문제이다. PyPy3로 제출해야 통과된다.

depth > 1 and li[depth-2] == li[depth-1] == i(현재 선택한 답과 그 전의 2개의 답이 같음) 조건을 성립하지 않는

답을 추가하고, 정답을 10개 다 선택했다면 점수를 확인하고 3 이상이라면 cnt를 올려주면 된다. 

def dfs(depth):
    global cnt
    if depth == 10:
        s = 0
        for j in range(10):
            if li[j] == ans[j]:
                s += 1
        if s >= 5:
            cnt += 1
        return ;
    for i in range(1, 6):
        if depth > 1 and li[depth-2] == li[depth-1] == i:
            continue
        li.append(i)
        dfs(depth+1)
        li.pop()
        
ans = list(map(int, input().split()))
li, cnt = [], 0
dfs(0)
print(cnt)

브루트포스 알고리즘 & 백트래킹 문제이다. 현재 근육량 + 현재 운동 키트 중량 - K가 0 이상일 때만 재귀 함수로

진입하고 depth(운동 일수)가 성공적으로 N이 되었다면 cnt를 올려주면 된다.

def dfs(depth, t):
    global cnt
    if depth == N:
        cnt += 1
        return ;
    for i in range(N):
        if check[i] or t+nums[i]-K < 0:
            continue
        check[i] = 1
        dfs(depth+1, t+nums[i]-K)
        check[i] = 0
        
N, K = map(int, input().split())
nums = list(map(int, input().split()))
check, cnt = [0]*N, 0
dfs(0, 0)
print(cnt)

수학 & 백트래킹 문제이다. 그런데 백트래킹을 써서 푸니까 시간 초과가 나온다.

시간 초과가 뜰 만 한 코드이긴 한데 어떻게 해결해야 할지 모르겠어서 일단 반복문을 사용해서 해결했다.

반복문 풀이(통과)

N = int(input())
s = set()
for i in range(N+1):
    for j in range(N+1 - i):
        for k in range(N+1 - i - j):
            t = N-i-j-k
            n = i + 5*j + 10*k  + 50*t
            s.add(n)

print(len(s))

백트래킹 풀이(시간 초과)

def dfs(depth, s):
    if depth == N:
        check[s] = 1
        return ;
    for i in range(4):
        dfs(depth+1, s+nums[i])
        
N = int(input())
nums = [1, 5, 10, 50]
check = [0]*(50*20+1)
dfs(0, 0)
cnt = 0
for i in check:
    if i:
        cnt += 1
print(cnt)

기본적인 백트래킹 문제이다.

def dfs(depth):
    if depth == M:
        print(*li)
        return ;
    for i in range(N):
        if depth == 0 or li[-1] <= nums[i]:
            li.append(nums[i])
            dfs(depth+1)
            li.pop()
        
N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
li = []
dfs(0)

기본적인 백트래킹 문제이다.

def dfs(depth):
    if depth == M:
        print(*li)
        return ;
    for i in range(N):
        li.append(nums[i])
        dfs(depth+1)
        li.pop()

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
li = []
dfs(0)

기본적인 백트래킹 문제이다.

def dfs(depth):
    if depth == M:
        print(*li)
        return ;
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        for j in range(i+1, N):
            check[j] = 0

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
li = []
check = [0]*N
dfs(0)

브루트포스 알고리즘 & 백트래킹 문제이다.

def dfs(depth):
    if depth == N:
        res.append(sum(abs(li[i+1]-li[i]) for i in range(N-1)))
        return ;
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        check[i] = 0

N = int(input())
nums = list(map(int, input().split()))
li, res = [], []
check = [0]*N
dfs(0)
print(max(res))

브루트포스 알고리즘 & 백트래킹 문제이다. PyPy3로 제출해야 통과된다.

def dfs(depth, k):
    if depth == k and sum(li) == S:
        s.append(li)
        return ;
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1, k)
        li.pop()
        for j in range(i+1, N):
            check[j] = 0

N, S = map(int, input().split())
nums = list(map(int, input().split()))
li, s = [], []
for i in range(1, N+1):
    check = [0]*N
    dfs(0, i)
print(len(s))