잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말합니다. 여러 개의 하위 문제를 해결하는 과정을 결합하여 최종 목적에 도달하게 됩니다.
문제 해결을 위한 모든 방법을 검토 후 최적의 풀이법을 찾아내는 방법으로
계산 횟수를 줄일 수 있어서 최단 경로 등 최적화에 사용됩니다.
그리디 알고리즘은 동적 프로그래밍의 모든 방법을 고려해야 한다는 단점을 극복했습니다. 항상 최적해를 구하지는 않지만 최소 신장 트리 같은 여러 문제에서 최적해를 구할 수 있다는 것이 입증되었습니다.
아래 문제는 다이나믹 프로그래밍, 줄여서 DP 유형의 문제로 해당 문제를 푸는 방식으로는 크게 3가지가 있습니다.
백준 - 1463번 1로 만들기 문제(https://www.acmicpc.net/problem/1463)
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 중 하나로 나누어 떨어지는 경우에서 최소 횟수가 이용될 수 있게 하였습니다.
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()에는 누적되고, 해당 값을 기준으로 목표 값의 횟수를 탐색할 수 있게 됩니다.
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이 처리되는 경우에는 바로 중지 후 담긴 횟수를 출력하게 하여 가장 최소 횟수가 출력될 수 있습니다.
참고 자료