동적 계획법, 동적 프로그래밍, Dynamic programming에 대해 알아보자
동적 계획법이란?
동적 계획법(Dynamic programming, DP)은 문제를 작은 문제들로 나눈 후 해결된 작은 문제들을 이용하여 더 빠르게 문제를 해결하는 방법을 말한다. 입력을 탐색해야 할 경우, 같은 값을 여러번 탐색하는 것을 메모리에 저장하여 더 빠른 속도로 계산을 완료할 수 있도록 한다.
사실 처음에 말로 들으면 이해가 잘 안되니 밑의 예시를 보면서 알아가보자.
DP를 이용한 알고리즘 예제 풀이
문제: 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요
제한사항
- 삼각형의 높이는 1 이상 500 이하입니다.
- 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
프로그래머스의 정수 삼각형 문제
DP를 사용하지 않을 경우
이 문제를 푸는 간단한 방법으로는 leaf node에 도달할 때 까지의 모든 경우의 수를 더해보며 계산하는 방법이 있다.
위와 같이 7+3+1 한 값과 7+8+1 을 한 후에 큰 값을 고르는 방식을 leaf node에서 진행하면 간단히 위 문제를 풀 수 있다.
앞에서 DP에 대해 설명한 바와 같이 메모리를 이용하는데 위의 경우처럼 얕은 depth를 확인할 경우에는 괜히 연산도 적은데 메모리를 사용하면 손해 아니에요?! 라고 할 수 있다. 그런 생각이 든다면, 밑의 경우로 넘어가 보자
한단계 더 depth가 내려갈 경우에는 7+3+8+7,7+3+1+7, 7+8+1+7 처럼 depth가 늘어날 수록 연산해야하는 +의 수가 늘어나고, 해당 node로 도착할 수 있는 경우의 수도 늘어난다. 따라서 위와같은 방식으로 진행할 경우 필요한 연산량과 경우의 수는 매우 늘어난다. 단순히 생각하고 싶다면...! 화살표의 개수가 수행해야 되는 연산이라고 생각해보자.
'매우 늘어난다' 는 대표적으로 피보나치 수열 연산에서, 과 정도의 차이를 보인다.
위의 문제의 경우 DP를 사용하지 않을 경우인 완전 탐색으로 해결할 경우에는 이고, DP를 사용할 경우에는 정도로 n의 크기 차이에 따라 매우 큰 차이를 보인다.
부모노드까지 오는 방법 을 구하기 위해 부모노드의 부모노드를 구하기위해 부모노드의부모노드의부모노드의... 어질어질하다... 어질어질한 방법으로 푸는게 완전 탐색 풀이이다.
DP를 사용한 풀이법
전공자라면, 위와같은 문제를 대학 시험문제에서 접할 경우 숫자를 써가며 알고리즘문제를 풀어간 경우가 있을것이다. 전공자가 아니어도 위의 문제를 풀어나갈 때, 노드 옆에 합한 숫자를 써가면서 손으로 풀어나가는게 가장 쉬운 방법중 하나일 것이다. 그게 가장 직관적인 DP의 예시이다.
해당 그림의 과정이 복잡한 문제를 나누어서 작은 문제로 나눈 것이다.
위의 경우 복잡한 문제란 leaf node까지 도달할 때 모든 경우의수를 계산하여 해당 값들중 가장 큰 값을 고르는 것 이고,
작은 문제를 통한 해결이란 부모노드까지 도달하는 값을 저장(메모) 하여 해당 값들중 큰 값을 자신의 값과 더하는 것이다.
위 그림에서는 부모노드까지 오는값들중 가장 큰 값을 비교하여 적어놓고, 해당 값들중 큰 값을 자기 자신과 더하면 된다.
해당 방식으로 문제를 해결하기 위해서, 입력과 같은 모양의 빈 트리를 생성해 준후 지금까지의 부모노드에 해당하는 값을 넣은 새로운 트리를 만들면 된다.
새로운 트리를 만들면 위와 같은 형태가 될것이다.
해결 코드
def solution(triangle):
answer = 0
dy_pyra = [[0 for __ in range(len(triangle[_]))] for _ in range(len(triangle))]
for depth in range(len(triangle)):
for idx in range(len(triangle[depth])):
if idx == 0 and depth == 0:
dy_pyra[0][0] = triangle[0][0]
elif idx == 0:
dy_pyra[depth][idx] = dy_pyra[depth-1][0] + triangle[depth][idx]
elif idx == len(triangle[depth])-1:
dy_pyra[depth][idx] = dy_pyra[depth-1][len(triangle[depth])-2] + triangle[depth][idx]
else:
dy_pyra[depth][idx] = max(dy_pyra[depth-1][idx-1],dy_pyra[depth-1][idx]) + triangle[depth][idx]
return max(dy_pyra[len(triangle)-1])필자는 reculsion을 상당히 좋아하는 편이었지만, 개발을 하다보니 reculsion을 쓰면 욕을 먹는다는 것을 깨달았다.
위의 코드에서는 head node일 경우, 부모가 하나밖에 없을 경우(양 끝 값으로 이동할 경우), 부모가 모두 존재할 경우로 나누어서 문제를 해결하였다. 해당 문제에서는 부모에 해당하는 값을 비교한 후 새로 만든 배열에 큰 값과 자기자신 값을 더하여 문제를 해결하였다.
문제에서 함수들의 호출을 줄일 방법이 분명히 있겠지만, 알고리즘 문제를 설명하고, 푸는 과정에서 가독성이 나
쁘면 내가 내 코드에 속아넘어가는 경우가 많아 그냥 쓰기로 했다.
번외
import copy
copy.deepcopy(array)를 할경우에 깊은 복사로 간단하게 배열을 복사할 수 있다고 한다.
해당 문제에서는 가장 큰 값을 구하는 것이 목표이므로 0으로 생성된 배열을 만드는게 바람직하다.
