Jinho Tech

기본적인 다이나믹 프로그래밍 문제이다. 처음에 풀 때 dp에 문자열(EX: "BA")을 저장했는데

메모리 초과가 나와서 그냥 숫자로 해결했다.

k = int(input())
dp = [0]*(k+1)
dp[1] = 1
for i in range(2, k+1):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[k-1], dp[k])

기본적인 이분 탐색 문제이다.

while 1:
    n = int(input())
    if n == 0:
        break
    s, e = 1, 50
    while s <= e:
        m = (s+e)//2
        print(m, end=' ')
        if m == n:
            break
        elif m < n:
            s = m+1
        else:
            e = m-1
    print()

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 'w'
    cnt = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < N) and (0 <= X < N) and graph[Y][X] == '-':
                q.append((Y, X))
                graph[Y][X] = 'w'
                cnt += 1
    return cnt

for _ in range(int(input())):
    N = int(input())
    graph = [list(input()) for _ in range(N)]
    d = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-1, 0), (1, 0), (0, -1), (0, 1)]
    res = 0
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 'w':
                res += bfs(i, j)
    print(res)

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < 8) and (0 <= X < 8) and graph[Y][X] == -1:
                q.append((Y, X))
                graph[Y][X] = graph[y][x]+1

sy, sx = map(int, input().split())
ey, ex = map(int, input().split())
graph = [[-1]*8 for _ in range(8)]
d = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2), (1, 2)]
bfs(sy-1, sx-1)
print(graph[ey-1][ex-1])

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < M) and (0 <= X < N):
                if graph[Y][X] == '4':
                    return graph[y][x]+1
                if graph[Y][X] == '1':
                    q.append((Y, X))
                    graph[Y][X] = graph[y][x]+1

M, N, M1, M2 = map(int, input().split())
graph = [input().split() for _ in range(M)]
d = [(-M1, -M2), (-M1, M2), (M1, -M2), (M1, M2), (-M2, -M1), (-M2, M1), (M2, -M1), (M2, M1)]
for i in range(M):
    for j in range(N):
        if graph[i][j] == '3':
            print(bfs(i, j))

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < N) and (0 <= X < M):
                if graph[Y][X] == 'H':
                    return graph[y][x]+1
                if graph[Y][X] == '.':
                    q.append((Y, X))
                    graph[Y][X] = graph[y][x]+1

M, N = map(int, input().split())
graph = [list(input()) for _ in range(N)]
d = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2), (1, 2)]
for i in range(N):
    for j in range(M):
        if graph[i][j] == 'K':
            print(bfs(i, j))
            break

기본적인 이분 탐색 문제이다.

def bs(li, m):
    if li[1]-li[0] > m:
        return 0
    if li[-1]-li[-2] > m:
        return 0
    for i in range(1, len(li)-2):
        if (li[i+1]-li[i])/2 > m:
            return 0
    return 1

N, M = int(input()), int(input())
li = [0] + list(map(int, input().split())) + [N]
s, e = 0, N
res = 0
while s <= e:
    m = (s+e)//2
    if bs(li, m):
        e = m-1
        res = m
    else:
        s = m+1
print(res)

기본적인 해시 문제이다.

import sys

N, M = map(int, sys.stdin.readline().rstrip().split())
d = {}
for _ in range(N):
    u, v = sys.stdin.readline().rstrip().split()
    d[u] = v
for _ in range(M):
    print(d[sys.stdin.readline().rstrip()])

기본적인 다이나믹 프로그래밍 문제이다. 11726번 2×n 타일링과 비슷한 문제이다.

n = int(input())
dp = [0, 1, 3]
for i in range(3, n+1):
    dp.append(dp[i-2]*2+dp[i-1])
print(dp[n]%10007)

기본적인 다이나믹 프로그래밍 문제이다. 두 가지 경우만 고려하면 쉽게 풀 수 있다.

1. 2*(n-1) -> 2*n: 타일이 한 개 들어가는 경우밖에 없기 때문에 2*(n-1) 크기의 직사각형에 타일을 배치하는 방법의 수만큼만 더해주면 된다.

2. 2*(n-2) -> 2*n: 타일이 두 개가 들어갈 수 있는데 타일을 세워서 배치하는 경우는 1번과 겹치기 때문에 넘어가고,

가로로 두 개 배치되는 경우만큼만 더해주면 된다.

정리하면 dp[i] = dp[i-2] + dp[i-1], (i > 2)과 같다.

n = int(input())
dp = [0, 1, 2]
for i in range(3, n+1):
    dp.append(dp[i-2]+dp[i-1])
print(dp[n])

기본적인 다이나믹 프로그래밍 문제이다.

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

생각보다 쉬운 BFS 문제이다. 변환된 숫자와 여태까지 사용한 명령어를 큐에 같이 append, pop 해주면 된다.

변환된 숫자와 B가 같다면 여태까지 사용한 명령어(res)를 리턴하면 끝이다.

from collections import deque

def bfs(A, B):
    q = deque()
    q.append((A, ""))
    while q:
        n, res = q.popleft()
        D = n*2 % 10000
        if D == B: return res+'D'
        elif check[D] == 0:
            check[D] = 1
            q.append((D, res+'D'))
        S = n-1 if n > 0 else 9999
        if S == B: return res+'S'
        elif check[S] == 0:
            check[S] = 1
            q.append((S, res+'S'))
        L = (n%1000)*10 + n//1000
        if L == B: return res+'L'
        elif check[L] == 0:
            check[L] = 1
            q.append((L, res+'L'))
        R = (n%10)*1000 + n//10
        if R == B: return res+'R'
        elif check[R] == 0:
            check[R] = 1
            q.append((R, res+'R'))

for _ in range(int(input())):
    A, B = map(int, input().split())
    check = [0]*10000
    print(bfs(A, B))

기본적인 문자열 문제이다.

N = int(input())
M = int(input())
s = input()
i = cnt = p = 0 
while i < M-2:
    if s[i] == 'I' and s[i+1] == 'O' and s[i+2] == 'I':
        i += 2
        p += 1
        if p == N:
            p -= 1
            cnt += 1    
    else:
        i += 1
        p = 0
print(cnt)

기본적인 다이나믹 프로그래밍 문제이다. li와 dp를 미리 선언하고 풀어야 런타임 에러가 안 나온다.

마지막 계단의 전 계단을 밟은 경우와, 밟지 않은 경우 2가지를 고려해서 풀면 된다.

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

기본적인 해시 문제이다. dict가 확실히 속도가 빠른 것 같다. 그냥 리스트로 풀면 통과가 안된다. 

import sys

N, M = map(int, sys.stdin.readline().rstrip().split())
d1, d2 = {}, {}
for i in range(1, N+1):
    s = sys.stdin.readline().rstrip()
    d1[s] = i
    d2[i] = s
    
for _ in range(M):
    s = sys.stdin.readline().rstrip()
    if s.isdigit():
        print(d2[int(s)])
    else:
        print(d1[s])