알고리즘 DP 정리

DP?

• Dynamic Programming
• 문제를 해결할 때, 큰 문제를 작은 문제로 분할하여 푸는 방법.
• 분할 정복 알고리즘과 유사.
• DP는 계산했던 결과를 저장하여 불필요한 연산 제외.
• 크게 Top-Down, Button-Up 방법 존재.
• 메모이제이션 (Memoization) : 계산한 값 저장하는 것

특성

1. Overlapping Subproblems : 큰 문제 --> 작은 문제 --> ...
2. OPtimal Structure : 작은 문제의 결과값(return) --> 큰 문제의 결과값 --> ...

문제풀이

#include <stdio.h>

int main(){
    int n;
    int a=0,b=1,result=0;
    scanf("%d", &n);
    if(n==1) {
        printf("1");
        return 0;
    }
    for(int i=1;i<n;i++){
        result=a+b;
        a=b;
        b=result;
    }
    printf("%d" , result);
             
    return 0;
}

int FTP(int n) {
  if(fibo[n] == -1)
    fibo[n] = FTD(n-1) + FTD(n-2);
  return fibo[n];
}
//Top-Down

int FBU(int n) {
  for (int i=2;i<=n;i++)
    fibo[i] = fibo[i-1] + fibo[i-2];
  return fibo[n];
}
//Bottom-Up

BOJ 2747  피보나치 수

 

#include <stdio.h>
#include <algorithm>
using namespace std;

long long p[1001];
long long waterrr(int n){
	if(p[n] == -1){
		p[n] = waterrr(n-2) + waterrr(n-3);
	}
	return p[n];
}

int main(){
	int c, n;
	scanf("%d", &c);
	
	fill(&p[0], &p[1000], -1);
	p[1]=1; p[2]=1; p[3]=1;

	for(int i=0;i<c;i++){
		scanf("%d", &n);
		printf("%lld\n", waterrr(n));
	}
}
//점화식 : F(n) = F(n-2) + F(n-3)

BOJ 9461 파도반 수열

 

 

#include <stdio.h>
#include <algorithm>
using namespace std;

int x[20];

int makeOTT(int n){
	if(x[n] == -1){
		x[n] = makeOTT(n-1)+makeOTT(n-2)+makeOTT(n-3);
	}

	return x[n];
}

int main(){
	int c, n;
	fill(x, &x[11], -1);
	x[1]=1; x[2]=2; x[3]=4;

	scanf("%d", &c);

	for(int i=0;i<c;i++){	
		scanf("%d", &n);
		printf("%d\n", makeOTT(n));
	}

	return 0;
}
//점화식 : F(n) = F(n-1)+F(n-2)+F(n-3)

BOJ 9095 1,2,3 더하기

 

#include <stdio.h>
#include <algorithm>
#define MOD 10007
using namespace std;

int x[1005];
int tiling(int n){
	if(x[n] == -1){
		x[n] = tiling(n-1) + tiling(n-2);
	}

	return x[n]%MOD;
}

int main(){
	int n;
	scanf("%d", &n);
	fill(x, &x[1001], -1);
	x[1] = 1, x[2] = 2;

	printf("%d\n", tiling(n));

}
//점화식 : F(n) = F(n-1)+F(n-2)

BOJ 11726 2xn 타일링