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

🚀DP(Dynamic Programming, 동적 계획법)

DP는 1) 큰 문제를 작은 문제로 나눌 수 있거나, 작은 문제를 모아 큰 문제에 대한 해결이 가능할 때, 2) 동일한 작은 문제를 반복적으로 해결하는 경우에 사용할 수 있다.
top-down은 보통 재귀 호출을 이용한다. bottom-up은 보통 반복문을 이용한다.

🚗TOP-DOWN

큰 문제를 해결하려고 작은 문제를 호출하는 방식이다. 일반적으로 점화식을 이해하기 쉽다는 장점을 갖고 있다.

+) 메모이제이션 : 재귀를 돌리는 경우, 미리 한 번 구해진 것을 여기다 기록하여 다음에 호출될 때 cut edge하는 것이다. 즉, 불필요한 재귀 호출을 방지한다.

🛬 Top-down(재귀, 메모이제이션) 예제, 네트워크 선 자르기

▣ 문제설명
현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다.
예를 들어 4m의 네트워크 선이 주어진다면

1) 1m+1m+1m+1m
2) 2m+1m+1m
3) 1m+2m+1m
4) 1m+1m+2m
5) 2m+2m

의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다.
그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요?

▣ 입력설명
첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다.

▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

▣ 입력예제 1
7

▣ 출력예제 1
21

using namespace std;
int dy[101];
int DFS(int n){

//메모이제이션 : 처음 dy[n]은 0으로 초기화되어 있을 것이다.
//이미 구했다면 dy[n] 값이 0을 초과할 것이므로, 그런 경우, cut
	if(dy[n]>0) return dy[n];
    
	if(n==1 || n==2) return n;
    else return dy[n] = DFS(n-1) + DFS(n-2);

}

int main(){
	ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    cout<<DFS(n);
    return 0;
}

🚓BOTTOM-UP

가장 작은 문제부터 답을 구하며 큰 문제의 답을 찾는 방식이다. 재귀 호출을 하지 않아 메모리 사용량 감소를 기대할 수 있다.

문제가 묻는 내용은 유지하며, 아주 작은 문제 크기 단위로 변경한다.

🛬 Bottom-up 예제, 네트워크 선 자르기

(위 TOP-DOWN의 예제와 같은 문제)

#include<bits/stdc++.h>
using namespace std;
int dy[50];
int main(){
	ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    dy[1]=1;
    dy[2]=2;
    for(int i=3;i<=n;i++){
    	dy[i]=dy[i-2]+dy[i-1];
    }
    cout<<dy[n];
    return 0;
}