WoohyunKing의 개발 성장일지

이번 문제는 Dynamic Programming 문제의 대표적인 예제인 정수 삼각형로, 대각선 방향으로만 움직일 수 있을 때 거쳐간 숫자의 합이 최대가 되도록 만드는 문제이다. 단순하게 완전탐색(DFS/BFS)로 풀 순 있겠지만, 이 문제의 경우 삼각형의 높이가 한 층씩 높아질수록 경우의 수 가 2배씩 늘어나는 문제로 단순히 완전탐색 알고리즘으로 풀게 되면 문제의 조건(높이는 1이상 500이하) 때문에 O(2^n)의 시간복잡도로 인해 시간초과가 발생할 것이다. 따라서 모든 경우의 수를 전부 구하는 완전 탐색이 아니라, 별도의 자료구조에 정보들을 저장하면서 중복된 연산을 최대한 줄여주는 DP 알고리즘을 사용하여 풀어야만 한다. 먼저 이전에 포스팅한 DP 알고리즘에 대한 내용을 복습할 겸 이 문제가 왜 DP..

1) Dynamic Programming 이란 ? Dynamic Programming은 또 다른 자료구조(메모리)에 계산한 정보들을 저장함으로써 중복되는 연산을 줄이고, 이로써 프로그램의 수행 속도를 개선하는 알고리즘이다. DP는 완전 탐색(BFS, DFS)과 같이 수많은 경우의 수를 따져보아야 할 때, 경우의 수가 수없이 많을 때 메모리 공간을 사용하여 수행시간을 단축시키는 알고리즘이다. 여러 개의 작은 문제들을 먼저 푼 후에 그 결과를 바탕으로 더 큰 문제를 해결하는 알고리즘으로, 한번 계산한 문제는 다시 계산하지 않도록 메모리에 저장하고, 필요한 경우 다시 계산하지 않고 저장된 값을 사용한다.(매 순간 최적의 값을 저장함) 쉽게 설명하면 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서..