Jinho Tech

간단한 브루트포스 알고리즘 or 다이나믹 프로그래밍 문제이다.

브루트포스 알고리즘 풀이

a, b, c, n = map(int, input().split())
res = 0
for i in range(0, n+1, a):
    for j in range(0, n-i+1, b):
        for k in range(0, n-i-j+1, c):
            if i+j+k == n:
                res = 1
print(res)

다이나믹 프로그래밍 풀이

a, b, c, n = map(int, input().split())
li = [a, b, c]
dp = [0]*(n+1)
dp[0] = 1
for i in range(1, n+1):
    for t in li:
        if i-t >= 0 and dp[i-t]:
            dp[i] = 1
print(dp[n])

기본적인 다이나믹 프로그래밍 문제이다. 현재 포도주를 마시지 않는 경우, 앞에 포도주를 마시고 현재 포도주를

마시는 경우, 앞에 포도주를 마시지 않고 현재 포도주를 마시는 경우로 총 세 가지를 고려해주면 된다.

-> dp[i] = max(dp[i-1], dp[i-3]+li[i-1]+li[i], dp[i-2]+li[i])

n = int(input())
li = [0] + [int(input()) for _ in range(n)]
dp = [0]*(n+1)
dp[1] = li[1]
if n > 1:
    dp[2] = li[1] + li[2]
for i in range(3, n+1):
    dp[i] = max(dp[i-1], dp[i-3]+li[i-1]+li[i], dp[i-2]+li[i])
print(max(dp))

다이나믹 프로그래밍 or 그래프 탐색 문제이다.

다이나믹 프로그래밍 풀이

N = int(input())
dp = [[0, []] for _ in range(N+1)]
dp[1][0] = 0
dp[1][1] = [1]
for i in range(2, N+1):
    dp[i][0] = dp[i-1][0] + 1
    dp[i][1] = dp[i-1][1] + [i]
    if i%2 == 0 and dp[i//2][0]+1 < dp[i][0]:
        dp[i][0] = dp[i//2][0] + 1
        dp[i][1] = dp[i//2][1] + [i]
    if i%3 == 0 and dp[i//3][0]+1 < dp[i][0]:
        dp[i][0] = dp[i//3][0] + 1
        dp[i][1] = dp[i//3][1] + [i]
print(dp[-1][0])
print(*dp[-1][1][::-1])

그래프 탐색(BFS) 풀이

입력이 1일 때만 주의해서 잘 처리해주면 된다.

from collections import deque

def bfs(node, dp):
    q = deque()
    q.append((node, dp))
    while q:
        node, dp = q.popleft()
        for n in [node+1, node*2, node*3]:
            if n <= N and check[n] == 0:
                if n == N:
                    return check[node]+1, dp+[n]
                q.append((n, dp+[n]))
                check[n] = check[node]+1

N = int(input())
if N == 1:
    print(0)
    print(1)
else:
    check = [0]*(N+1)
    cnt, dp = bfs(1, [1])
    print(cnt)
    print(*dp[::-1])

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

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

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

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

def dfs(n):
    if n == M:
        print(*li)
        return
    for i in range(N):
        li.append(i+1)
        dfs(n+1)
        li.pop()

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

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

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

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

백트래킹(Backtracking)이란 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾아가는 방법을 말한다. 

방식에 따라서 깊이우선탐색(Depth-first search, DFS)과 너비우선탐색(Breadth-first search, BFS)으로 나눌 수 있다.

깊이우선탐색(Depth-first search, DFS) jinho-study.tistory.com/865?category=999578

너비우선탐색(Breadth-first search, BFS) jinho-study.tistory.com/866?category=999578

백트래킹 문제로는 대표적인 예시로 여덟 퀸 문제가 있다.

백준 9663번 N-Queen)

def check(n):
    for i in range(n):
        if row[n] == row[i] or abs(row[n]-row[i]) == n-i:
            return 0
    return 1
        
def dfs(n):
    global res
    if n == N:
        res += 1
    else:
        for i in range(N):
            row[n] = i
            if check(n):
                dfs(n+1)

N = int(input())
row = [0]*N
res = 0
dfs(0)
print(res)

백준 알고리즘 문제 풀이)

jinho-study.tistory.com/979

jinho-study.tistory.com/985

jinho-study.tistory.com/987

jinho-study.tistory.com/988

jinho-study.tistory.com/989

jinho-study.tistory.com/993

jinho-study.tistory.com/1032

jinho-study.tistory.com/1034

jinho-study.tistory.com/1035

jinho-study.tistory.com/1036

jinho-study.tistory.com/1037

jinho-study.tistory.com/1038

jinho-study.tistory.com/1040

jinho-study.tistory.com/1041

jinho-study.tistory.com/1042

jinho-study.tistory.com/1043

jinho-study.tistory.com/1044

jinho-study.tistory.com/1045

jinho-study.tistory.com/1047

jinho-study.tistory.com/1070

https://jinho-study.tistory.com/1095

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

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

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

단순 수학 문제이다. 뭔가 문제가 좀 어려워 보이는데, 3개를 기준으로 뒤집으면 가운데 숫자는 그대로고 양 옆의 숫자만

바뀐다는 점을 활용하면 생각보다 엄청 쉽게 풀 수 있는 문제이다.

홀수번째 값(1번째, 3번째, ...)이 모두 홀수이면 정렬이 가능하고, 아니라면 정렬이 불가능하다. 

EX) 2 1 3 4 5 -> 어떤 식으로 정렬을 해도 1은 맨 처음에 위치할 수가 없다.

N = int(input())
li = list(map(int, input().split()))
ok = 1
for i in range(N):
    if i%2:
        if li[i]%2:
            ok = 0
print("YES" if ok else "NO")

단순 문자열 문제이다. 1은 앞에서부터, 0은 뒤에서부터 지워주면 된다.

li = list(input())
zero, one = li.count('0')//2, li.count('1')//2
for _ in range(zero):
    li.pop(-li[::-1].index('0')-1)
for _ in range(one):
    li.pop(li.index('1'))
print(''.join(li))

단순 문자열 문제이다. 맨 앞글자가 모두 같은지를 확인해주면 된다.

N = int(input())
li = input().split()
s = set()
for i in range(N):
    s.add(li[i][0])
print(1 if len(s) == 1 else 0)

S에서 시작해서 1부터 N까지 순서대로 들렀을 때의 최단거리를 구해야 되는 BFS 문제이다.

1에 들러야 된다고 해서 2를 지나가면 안 된다는 것은 아니다. 

목적지(1, 2, ... N)에 도착할 때마다 시작점부터 이동한 거리를 res에 더하고,

시작점과 목적지를 업데이트, 맵을 초기화하는 방식으로 해결했다.

EX) 시작점 S에서 목적지 1에 도착 -> res += 거리, 시작점 1, 목적지 2, 맵 초기화 

from collections import deque
from copy import deepcopy

def clear(target):
    for i in range(H):
        for j in range(W):
            if graph[i][j] == 'X':
                t[i][j] = -2
            else:
                t[i][j] = -1

def bfs(y, x, target):
    q = deque()
    q.append((y, x))
    clear(target)
    t[y][x] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < H) and (0 <= X < W) and t[Y][X] == -1:
                if graph[Y][X] == target: 
                    return t[y][x] + 1, Y, X
                else:
                    t[Y][X] = t[y][x] + 1
                    q.append((Y, X))
        
H, W, N = map(int, input().split())
graph = [list(input()) for _ in range(H)]
t = deepcopy(graph)
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = 0
for i in range(H):
    for j in range(W):
        if graph[i][j] == 'S':
            y, x = i, j
            for n in range(1, N+1):
                z, y, x = bfs(y, x, str(n))
                res += z 
print(res)

그냥 set을 사용해서 풀었다. 딕셔너리를 사용해서 풀어도 똑같다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
s = set([input() for _ in range(N)])
cnt = 0
for _ in range(M):
    t = input()
    if t in s:
        cnt += 1
print(cnt)

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

row[n] == row[i] -> 같은 열 확인, abs(row[n]-row[i]) == n-i -> 대각선 확인

def check(n):
    for i in range(n):
        if row[n] == row[i] or abs(row[n]-row[i]) == n-i:
            return 0
    return 1
        
def dfs(n):
    global res
    if n == N:
        res += 1
    else:
        for i in range(N):
            row[n] = i
            if check(n):
                dfs(n+1)

N = int(input())
row = [0]*N
res = 0
dfs(0)
print(res)

난이도가 있는(시간 초과) 수학 문제이다. 0부터 시작해서 제곱 값들을 확인하면

무조건 시간 초과가 나오기 때문에 a보다 크거나 같은 제곱수들만 확인해야 한다. 

a, b = map(int, input().split())
li = [1]*(b-a+1)
for i in range(2, int(b**0.5)+1):
    t = i**2
    for j in range(a//t*t, b+1, t):
        if j-a >= 0 and li[j-a]:
            li[j-a] = 0
print(li.count(1))