Top-down DP와 Bottom-up DP
DP를 푸는 방식에는 크게 두 가지 스타일이 있다고 할 수 있습니다.
첫 번째는, Top-down DP로, 큰 부분부터 작은 부분으로 쪼개지며 답을 찾습니다.
두 번째는 Bottom-up DP로, 작은 부분부터 시작해 큰 부분까지 모두 답을 찾습니다.
단순히 구현 방법의 차이라고만 생각할 수도 있겠지만, 의외로 성능 차이가 나는 부분이 있습니다.
Top-down DP의 이점
Top-down DP가 훨씬 유리한 경우가 있습니다. 모든 부분을 다 구하지 않아도 될 때인데, 백준 무한 수열 문제처럼, 수열의 모든 항을 다 구하지 않아도 될 때는 Top-down 방식이 훨씬 유리합니다. Bottom-up DP는 문제를 해결하는 데 있어 필요하지 않은 부분까지 모두 구하다 보니, 메모리나 시간 상 Top-down DP에 밀리게 됩니다.
같은 결과를 내는 코드이지만 성능상 큰 차이가 납니다.
Botton-up 방식은 10¹² 크기의 A 배열을 다 구해서 메모리 초과가 났습니다. 반면, Top-down 방식은 필요한 부분만 구했기 때문에 매우 빠르게 동작하며, 메모리도 많이 차지하지 않습니다.
Bottom-up DP의 이점
Bottom-up DP가 더 유리한 경우가 있습니다. 이전과 반대로, 모든 부분을 다 구해야 할 때는 Bottom-up DP가 유리합니다. Top-down DP는 흔히 재귀함수를 이용해 구현하는데, 이 때문에 불필요한 메모리가 낭비될 수 있습니다. 피보나치 수 4 문제가 예시로 있습니다.
차이가 많이 나진 않지만, Top-down DP가 메모리를 더 먹고 있습니다.
구해야 하는 수가 더 많아질수록, Top-down DP와 Bottom-up DP의 메모리 차이는 더 커집니다.
'백준 & 알고리즘' 카테고리의 다른 글
| [파이썬] 백준 3682번 - 동치 증명 (0) | 2023.10.15 |
|---|---|
| [파이썬] 백준 4013번 - ATM (0) | 2023.10.13 |
| [파이썬] 백준 1111번 - IQ Test 풀이 (0) | 2023.06.23 |
| [파이썬] 백준 1354번 - 무한 수열 2 풀이 (0) | 2023.06.23 |
| [파이썬] 백준 1351번 - 무한 수열 풀이 (0) | 2023.06.23 |
