📌 DP 알고리즘(Dynamic Programming)이란
✨ 목적
: 다이나믹 프로그래밍은 완전 탐색, DFS, BFS와 같이 수많은 경우의 수를 모두 따져봐야하는데, 그 경우의 수가 너무 많아서 속도가 느려지는 문제를 개선하고자, 수행시간을 단축하기 위해 만들어진 알고리즘
- DP 알고리즘이 없었을 때에는 최단 경로를 찾거나 최고 점수를 만드는 등의 문제를 풀려면 모든 조합을 만들어보는 수 밖에 없었음
- DP 알고리즘이 만들어진 이후에는 수행시간을 현저하게 줄일 수 있었음
✨ 예제 (프로그래머스_정수 삼각형)
-
DFS 사용 할 경우
: 7-3-8-2-4 를 더해서 24라는 숫자를 구해 max라는 변수를 갱신하고,
: 7-3-8-2-5 를 더해서 25라는 숫자로 max를 갱신하고,
: 이 동작을 반복해서 모든 경우의 수를 다 따져보면 30이라는 값이 최댓값이라는 것을 알 수 있음
-> 5줄 짜리 삼각형이면 전혀 지장이 없지만, 500줄 짜리 삼각형 이라면 경우의 수가 너무 많아짐
-> 중복적인 연산이 많음
-> 연산 횟수를 어떻게 줄이고 빠르게 푸는 방법은 ? -
DP 사용할 경우
: 컴퓨터가 보기 쉽게 직각 삼각형 형태로 바꿈
: 한 숫자에서 내려갈 수 있는 길은 왼쪽, 오른쪽이 아닌 밑으로 가거나 내 밑의 오른쪽으로 가거나 두 가지 경우의 수가 있음
: 연산을 줄이기 위해서는 한 번 수행한 연산의 결과를 저장해둬야 함 -> 이 삼각형과 동일하게 생긴 배열 하나 더 만듦
: 원본 삼각형은 문제에서 주어졌던 값을 그대로 갖고 있음
: DP 삼각형은 해당 위치까지 올 수 있는 최댓값을 저장하는 배열
: 최종 DP 삼각형을 통해 마지막 줄만 참고했을 때, 30이라는 답을 도출해 낼 수 있음
✨ DP의 목적
- 메모리를 사용해 중복 연산을 줄이고, 중복 연산을 줄여서 수행 속도를 개선한다
- 메모리를 사용한다 = 또 하나의 배열 혹은 자료구조를 만든다
- 중복 연산을 줄인다 = 한 번 연산한 결과를 배열에 담아 다시는 같은 연산을 다시 하지 않는다
✨ DP 문제를 알아보고 구분하는 방법
- DP는 특정 유형에만 국한되지 않고 다양한 유형의 문제를 최적화 할 때 고려될 수 있는 알고리즘
1) DFS/BFS로 풀 수는 있지만 경우의 수가 너무 많은 문제
2) 경우의 수들에 중복적인 연산이 많은 경우
✨ 문제 해결 접근 방법
- 최대한 많은 문제들을 풀어보고 풀이를 참고하면서 DP 사고방식을 키우는게 중요함 !
둉이닝