DP 동적 프로그래밍

DP란? (Dynamic Programming, 동적 프로그래밍)

DP는 Dynamic Programming의 약자로, 동적 프로그래밍이라고 부른다.
하나의 큰 문제를 여러 개의 작은 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 피하는 알고리즘 기법이다.

DP가 필요한 이유

모든 알고리즘은 기존의 문제를 더 효율적으로 해결하기 위해 고안되었다.
DP는 완전탐색, DFS, BFS처럼 모든 경우의 수를 전부 따져야 하는 문제에서 경우의 수가 너무 많아 속도가 느려지는 문제를 개선하고자 만들어진 알고리즘이다.

예전에는 최단 경로나 최적의 점수를 찾으려면 모든 조합을 일일이 계산해야 했지만, DP를 사용하면 수행 시간이 획기적으로 단축된다.

한메모리(배열, 자료구조)를 활용해 중복 연산을 줄이고, 그로 인해 수행 속도를 개선하는 알고리즘

• 메모리를 사용한다 → 배열이나 자료구조에 결과를 저장한다.
• 중복 연산을 줄인다 → 이미 계산한 결과를 재사용한다.

DP는 '기억하기 알고리즘', '기억하며 풀기'라고 번역되기도 하며, 실제로 연산한 내용을 기억해두고 필요할 때 다시 사용하는 것이 핵심이다.

예제: 프로그래머스 정수 삼각형

대표적인 DP 문제로 프로그래머스 - 정수 삼각형이 있다.

DP 문제를 알아보고 구분하는 방법

DP는 특정 유형에만 국한되지 않고, 다양한 문제의 최적화에 활용할 수 있다.
그렇다면 코딩테스트에서 "이건 DP로 풀어야겠다"라고 판단할 수 있는 기준은 무엇일까?

 

DP 적용 판단 기준 2가지

1. DFS/BFS로 풀 수는 있지만 경우의 수가 너무 많은 문제
   예를 들어, 정수 삼각형이 5줄이라면 DFS로도 충분하지만, 500줄이 되면 경우의 수가 2n-1로 폭발적으로 증가해 현실적으로 불가능하다.
2. 경우의 수에 중복 연산이 많은 경우
   이미 계산한 부분 문제의 결과를 여러 번 다시 계산하게 되는 경우, DP로 효율적으로 해결할 수 있다.

DP 문제를 잘 풀려면?
DP는 직접 해결책을 떠올리는 것보다, 다양한 유형을 많이 풀어보는 것이 중요하다.
문제를 풀때 30분 정도 고민해보고, 답이 안 나오면 풀이를 참고해 구현 연습을 하는 것이 효율적

 

 

DP는 여태까지의 최적의 답을 쌓아나가며 연산 횟수를 줄이는 방식으로 접근하면 이해가 쉽다.
다양한 문제를 풀며 감을 익혀야 한다.

 

 

포스팅을 위해 참고한 사이트 : https://www.youtube.com/watch?v=0bqfTzpWySY&t=160s