DP

🌿 개념

동적 계획법 (dynamic programming)

"점화식의 정의를 스스로 찾는 연습을 해야 한다!"

🌿 사용 조건

1. optimal substructure (최적 부분구조)
   작은 문제의 정답을 통해 큰 문제의 정답을 구할 수 있다.

2. overlapping subproblem (겹치는 부분문제)
   작은 문제의 정답을 여러 번 사용한다.

if(조건 1){
	if(조건 2){
    	"dynamic programming"
    }
    else{
    	"divide and conquer"
    }
}

🌿 구현 방식

🌱 종류

1. Top-down (재귀)
   • 큰 문제를 작은 문제로 나눈다.
   • 작은 문제를 푼 후, 큰 문제로 돌아간다.

2. Bottom-up (반복문)
   • 크기가 작은 문제부터 점차 크기를 키워나가며 문제를 해결한다.

🌱 주의사항

1. 둘 중 무엇의 시간 복잡도가 좋다고 확언할 수 없다.

2. 특정 방법만으로 풀 수 있는 문제가 있지만, 현재 수준에서 다룰 내용은 아니다.
   (이 문제를 접할 쯤에는, 둘 다 능숙해 질 것)

그러므로 우선 한 가지 방법에 익숙해질 때까지 그 방법을 숙달해보자!

🌿 시간 복잡도

함수의 시간 복잡도 = 문제의 개수 * 한 문제를 푸는데 걸리는 시간