Week4

DP

DP는 Dynamic programming으로 동적 계획법을 뜻합니다. 문제를 작게 나누어서 해결하는 기법입니다. DP는 다음 두 가지 조건을 만족하여야합니다.

• Optimal substructure

1. 작은 문제들을 이용하여 전체 문제를 해결할 수 있는 경우.
2. 풀고자 하는 문제의 답은 해당 문제를 작게 나눈 문제들의 답들을 포함.

• Overlapping subproblem

1. 작은 문제들이 중복해서 나타나는 경우.
2. 분할 정복 역시 문제를 작은 문제로 나눠서 해결.
3. 분할 정복과 DP의 차이 중 하나는 똑같이 문제를 나누지만 중복해서 나타나는가의 여부.(DP는 중복해서 나타남)
4. 분할 정복은 한번에 해결하기 어려운 문제를 작게 나눠 해결하지만 큰 문제는 작은 문제에 의존적X.
5. DP은 큰 문제를 해결하기 위해 문제를 작게 나눠 해결하며 작게 나눈 문제의 답에 의존적.

Memoization

DP는 필연적으로 중복된 계산이 일어날 수 밖에 없는 구조입니다. 이러한 중복 계산을 피하기 위해 사용하는 기법이 Memoization입니다. 어떤 작은 문제를 해결한 뒤에 그 문제의 답을 메모하는 식으로 이루어집니다. 그리고 이후에 다시 같은 문제를 해결해야만 하는 경우 미리 저장해둔 답을 가져다 쓰는 것 입니다.

PLUS) DP

DP는 문제마다 해결하는 방법이 다르기 때문에 정형화된 코드가 존재하지 않습니다. 문제를 쉽게 해결하기 위해서는 문제를 최대한 요약하는 것이 매우 좋은 방법입니다.(+ DP의 시간 복잡도는 보통 O(NT)입니다. N은 해결해야 하는 부분 문제의 수, T는 부분 문제를 해결하기 위해 필요한 연산 횟수를 뜻합니다.) DP는 다음 두 가지의 문제 접근 방법이 존재합니다.

• Top-down

1. 전체 문제에서 시작하여 문제를 나눠가며 해결.
2. 주로 재귀함수를 이용하여 해결.

• Bottom-up

1. 작은 문제부터 차례로 문제를 해결하여 최종적으로 전체 문제를 해결.

나머지 연산의 성질

• (A+B)%p = ((A%p)+(B%p))%p
• (AxB)%p = ((A%p)X(B%p))%p
• (A-B)%p = ((A%p)-(B%p)+p)%p
• 나누기에 대해서는 성립하지 않는다.