[BACKJOON] Dynamic programming

HyeonJeong·2023년 3월 6일
0

Baekjoon을 풀어보자

목록 보기
5/5
post-thumbnail

Dynamic programming

동적 프로그래밍이란,

잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말합니다. 여러 개의 하위 문제를 해결하는 과정을 결합하여 최종 목적에 도달하게 됩니다.

문제 해결을 위한 모든 방법을 검토 후 최적의 풀이법을 찾아내는 방법으로
계산 횟수를 줄일 수 있어서 최단 경로 등 최적화에 사용됩니다.

비교 : 그리디 알고리즘

그리디 알고리즘은 동적 프로그래밍의 모든 방법을 고려해야 한다는 단점을 극복했습니다. 항상 최적해를 구하지는 않지만 최소 신장 트리 같은 여러 문제에서 최적해를 구할 수 있다는 것이 입증되었습니다.

가능한 빠른 이동 방식 탐색

  • 동적 프로그래밍 : a -> b까지 이동의 모든 정보를 통해 최적 경로를 탐색
  • 그리디 알고리즘 : 교차로가 보일 때마다 가장 빠른 경로 검색

    => 시간이 걸리는 최적의 값 vs 시간에 비해 효율적인 값

아래 문제는 다이나믹 프로그래밍, 줄여서 DP 유형의 문제로 해당 문제를 푸는 방식으로는 크게 3가지가 있습니다.

백준 - 1463번 1로 만들기 문제(https://www.acmicpc.net/problem/1463)

Bottom up

import sys
n = int(sys.stdin.readline())
d = [0]*(n+1)

for i in range(2,n+1):
    d[i] = d[i-1] + 1
    if i%2 == 0:
        d[i] = min(d[i], d[i//2]+1)
    if i%3 == 0:
        d[i] = min(d[i], d[i//3]+1)
        
print(n)

위 방식은 목표인 1이 되는 방법이 아닌, 1에서 n으로 올라가면서 그 값이 될 수 있는 최소 값을 누적된 값을 이용해서 해결합니다.
해당 문제에서 우리는 2와 3 모두로 나누어 떨어지는 경우, 2 또는 3 중 하나로 나누어 떨어지는 경우에서 최소 횟수가 이용될 수 있게 하였습니다.

Top down

import sys
n = int(sys.stdin.readline())
d = {1:0}

def make_one(n):
    if n in d:
        return d[n]
    if i%2 == 0 and i%3 == 0:
        d[n] = min(rec(n//3)+1, rec(n//2)+1)
    elif i%2 == 0:
        d[n] = min(rec(n-1)+1, rec(n//2)+1)
    elif i%3 == 0:
        d[n] = min(rec(n-1)+1, rec(n//3)+1)
    else:
        d[n] = rec(n-1)+1
    return d[n]
print(n)

위와 달리 n에서 될 수 있는 하위 값을 찾아서 내려가는 방식으로 이용하였습니다. 재귀함수로 하위 값이 dict()에 존재할 수 있도록 조정하여 최소 횟수가 dict()에는 누적되고, 해당 값을 기준으로 목표 값의 횟수를 탐색할 수 있게 됩니다.

deque

import sys
from collections import deque
n = int(sys.stdin.readline())
q = deque([n])
visited = [0]*(n+1)

while q:
    value = q.popleft()
    if value == 1:
        break
    if value%3 == 0 and visited[value//3] == 0:
        q.append(value//3)
        visited[value//3] = visited[value]+1
    if value%2 == 0 and visited[value//2] == 0:
        q.append(value//2)
        visited[value//2] = visited[value]+1
    if visited[value-1] == 0:
        q.append(value-1)
        visited[value-1] = visited[value]+1
print(visited[1])

최소 계산 횟수를 구하는 문제이기 때문에 항상 최단 거리를 보장하는 BFS방식 또한 적용할 수 있습니다. BFS에서는 방문한 노드를 visited = []에 기록해두고, 다음 방문할 노드를 deque에 넣게 됩니다. 방문하지 않은 노드를 찾아가야하기에 모든 다음 단계를 q에 넣기전에는 해당 노드의 방문 여부를 확인합니다.

해당 문제에서는 visited에 방문 횟수를 기록하는 방식을 이용하여, 현재 방문 횟수+1을 q에 넣는 다음 방문 노드의 visited에 넣어서 횟수를 누적해서 넣어둡니다. 그리고 1이 처리되는 경우에는 바로 중지 후 담긴 횟수를 출력하게 하여 가장 최소 횟수가 출력될 수 있습니다.


참고 자료

0개의 댓글