[알고리즘][다이나믹(동적 계획법) 기초] 숫자 삼각형 (백준)

다이나믹 (동적 계획법) 알고리즘 기초 문제 : 숫자 삼각형 (백준)

첫 문제를 풀고나서 푸니까 확실히 시간이 단축된다.

원리에 좀 더 익숙해진다면 점점 더 단축되리라 믿는다.

다이나믹(동적 계획법) 알고리즘 기초 : 숫자 삼각형

RGB 거리라는 비슷한 문제를 풀고

바로 풀어서 그런지 시간이 15분 밖에 안걸렸다.

RGB와 같은 원리지만 위에서 아래로 향했던 것과 달리

이 문제는 아래에서 위로 계산하며 올라가야 한다.

다시한번 말하지만 다이나믹(동적 계획법) 알고리즘의 핵심은

구해놓은 답을 활용하여 현재의 답을 차근차근 찾아 나가는 것!!

꼭 기억하고 문제를 푼다면 더욱 이해하기 쉬울 것이다.

가장 밑의 바로 위층 부터 시작해서

(가장 밑 층의 데이터를 이용하여 밑의 바로 위층을 갱신하기 때문에 여기부터 시작한다.)

최대 값만을 골라 그 위치에 더하면서 갱신한다.

그렇다면 현재층의 모든 숫자는 아래층으로부터 올라온 최대값을 골라서 더하게 되며,

결국 꼭대기에서는 가장 최대값만을 골라서 더한 값이 저장되게 된다.

다이나믹(동적 계획법) 알고리즘은 코드의 크기는

DFS, BFS보다 훨씬 간결하다. 하지만 두 알고리즘 보다

훨씬 많은 고민을 해야하는 것은 분명한 사실인듯 하다.