[개념정리] 동적 프로그래밍(Dynamic Programming)

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

동적 프로그래밍(Dynamic Programming)은 작은 하위 문제로 나누어 그 결과를 저장해가며, 전체 문제를 해결하는 알고리즘 설계 기법입니다. 이를 통해 중복 계산을 줄여 계산 속도를 높이고 효율적으로 계산할 수 있습니다.

 

 

DP 기법을 적용시킬 수 있는 조건

1. 중복되는 부분 문제(Overlapping Subproblems)

동일한 작은 문제들이 반복하여 나타나는 경우, 반복적으로 같은 문제를 해결하는 성질입니다.

2. 최적 부분 구조(Optimal Substructure)

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 성질로, 작은 문제의 최적해를 통해 큰 문제의 최적해를 구할 수 있습니다.

 

 

DP 문제 풀이 방법

1. 하위 문제 

하위 문제로 분할하여 하위 문제를 재귀적으로 해결합니다.

2. 결과 저장
하위 문제의 결과를 저장하고 이를 이용하여 큰 문제를 해결합니다.

 

DP 문제 해결 방식

1. Bottom-Up (Tabulation 방식) - 반복문 사용 / 최적 부분 구조
   Bottom-Up 방식은 작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결하는 방식입니다. 작은 문제들의 결과값을 저장함으로써 동일한 계산을 반복하지 않아 시간 복잡도가 감소합니다. 일반적으로 더 직관적이고 이해하기 쉽지만 결과값을 임의로 저장해 둘 공간이 필요합니다.
2. Top-Down (Memoization 방식) - 재귀 사용
   큰 문제를 작은 부분 문제로 나누어 해결하는 방식입니다. 중복 계산을 피하기 위해 이전에 계산한 값을 저장하는 Memoization을 활용하며, 시간 복잡도가 감소합니다. 하지만 초기값 설정 및 작은 문제들의 결과값을 저장해둘 공간이 필요합니다.

 

DP 장단점

장점

• 중복 계산을 줄일 수 있습니다.
• 효율적인 시간 복잡도를 가질 수 있습니다.

단점

• 메모리 사용량이 큽니다. DP는 중간 결과를 저장하기 위해 추가적인 메모리를 사용합니다. 따라서 문제의 크기가 커질수록 필요한 메모리도 증가할 수 있습니다.

 

최장 증가 부분 수열(Longest Increasing Subsequence, LIS)이란?

주어진 수열에서 일부 항목을 선택하여 만들 수 있는 부분 수열 중에서, ‘원소의 크기가 증가하는 순서대로 정렬’되어 있는 가장 긴 수열을 찾는 문제

 

 

https://chanhuiseok.github.io/posts/algo-49/

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘