[코테 합격자 되기] 15장 동적계획법

#동적계획법이란?

복잡한 문제를 단순한 하위 문제로 나눠서 접근하는 방법이고

중복 계산을 줄이기 위해, 이전에 구한 해를 활용한다

 

#동적계획법을 써야 하는 문제의 기준

동적계획법을 사용해야 하는지 판단하는 기준은

아래의 두 조건을 모두 만족하면 동적계획법을 사용하면 된다

1. 최적부분 구조 문제 (Optimal Substructure)

2. 중복부분 문제 (Overlapping Subproblems)

 

최적부분 구조는

문제의 최적 해결책이 하위 문제의 최적 해결책으로

구성되는 경우를 의미한다

예를 들어

현재 해(N의 해)를 구할 때, 이전 해(N-1의 해)로 해결이 가능한 경우이다

 

중복부분 문제는

동일한 하위 해가 여러 번 중복되어 계산되어 활용되는 경우를 의미한다

예를 들어

해를 구할 때마다 이전에 사용했던 해가 중복해서 사용되는 경우이다

 

참고로

만약 최적 부분 구조만 만족하고 중복 부분 문제가 없다면, 

단순한 분할 정복(Divide and Conquer)을 사용하는 것이 적절하다
ex. 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort)

 

만약 중복 부분 문제만 만족하고 최적 부분 구조를 만족하지 않는다면, 

DP를 적용해도 전체 문제의 해를 얻을 수 없다

 

# 동적계획법 판단 예시 1 - 팩토리얼

위의 예시는 최적부분 O, 중복부분 X로

동적계획법으로 풀어도 효율이 좋지 않다

 

# 동적계획법 판단 예시 2- 피보나치 수

위의 예시는 최적부분 O, 중복부분 O로

동적계획법으로 풀면 효율적이다

 

#동적계획법 적용하는 법

동적계획법을 사용할 조건이 만족된 문제라면,

아래의 순서대로 동적계획법을 활용하면 된다

1. 예제의 입력으로 출력을 만드는 과정을 직접 손이나 그림을 그려본다

2. 과정에서 일반화 및 규칙을 찾는다

이때 최종해를 구하는 과정을 이전해를 구하는 과정을 통해 나태낼 수 있는지 확인한다

3. 2번째 과정에서 이전해를 구하는 과정이 중복되는지 확인한다

 

#동적계획법 적용하는 법 - 예시

예시 1 - 계단 오르기

문제)

적용)

 

참고 코드)

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Example/stairproblem_dp.cpp

 

 

예시 2 - 정사각형 개수 세기

문제)

 

적용)

 

근처 3부분의 최소값 + 1이 본인의 값이 된다

 

참고 코드)

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Example/squarecount.cpp

 

 

예시 3 - LIS(최장 증가 부분수열)

예시 문제를 보기 전 알아야할 지식)

부분 수열이란

주어진 수열 중 일부를 뽑아 새로 만든 수열을 의미하고

이때 기존 순서는 유지한다

 

최장 증가 부분 수열이란

주어진 수열 중 일부를 뽑아 새로 만든 부분 수열 중

오름차순을 유지(엄격한 증가)하면서 가장 긴 수열을 의미한다

 

문제)

1, 4, 2, 3, 1, 5, 7, 3을 가지고

최장 증가 부분 수열을 만들기

 

적용)

 

참고 코드)

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Example/lis_iterative.cpp