DP 뽀개기 (1)

DP를 이해하기 위해 재귀 호출을 이해해보자!

재귀 사용시 주의사항
1. 재귀에는 항상 종료 조건이 있어야 한다.
2. 재귀 함수는 전체 작업의 일부만 수행하고 나머지는 재귀 호출에 위임

n의 팩토리얼을 반환하는 함수

#include <iostream>
using namespace std;

int fac(int n){
    if(n<=0) return 0;
    if(n==1) return 1;
    return fac(n-1)*n;
}

--
재귀 이용 X

int fac(int n){
    int sum = 1;

    for(int i=1;i<=n;i++){
        sum*=i;
    }
    return sum;
}

배열값 갱신하기

#include <iostream>
#include <string>
using namespace std;

int dp[10]={0};
int arr[10];

void addition(int arr[], int index){
    if(index==7){
        return;
    }
    
    addition(arr,index+1);
    for(int i=index;i>=0;i--){
        arr[index]+=arr[i-1];
    }

}

함수 작성 시의 네 가지 주의 사항

1. 목적 지향적 -> 의도한 대로 동작
2. 수행되는 데 필요한 시간은 짧을수록 좋다
3. 함수가 사용하는 메모리의 크기는 작을수록 좋다
4. 이해하기 쉬워야 한다. 문서나 주석이 없더라도 이해할 수 있어야 한다.

재귀함수로 구구단 프린트하기

#include <iostream>
using namespace std;

void table(int n, int i){
    if(i==10){
        return;
    }

    cout<<n<<'*'<<i<<'='<<n*i<<endl;
    table(n,i+1);
    -> 2*1 부터 나온다
    
    만약에
    table(n,i+1);
    cout<<n<<'*'<<i<<'='<<n*i<<endl;
    
    이 순서라면 2*9 부터 역순으로 
}

int main(){
    table(2,1);
}