[기본문제풀이] dynamic_programming

풀이 일시 : 2020-08-08

​

다이나믹프로그래밍 :

하나의 문제는 단 한번만 풀도록 하는 알고리즘으로 효율성을 개선하는 알고리즘이다.

가정1 - 큰 문제를 작은 문제로 나눌 수 있다.

가정2 - 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 작동한다.

이미 계산한 결과는 배열에 저장함으로써 나중에 꺼내서 쓰기만 하면 되게끔 한다.

​

문제 :

dp로 피보나치 구현

 

풀이 : 

#include <stdio.h>

int d[100] = { 0, }; //배열 선언 및 전체 0으로초기화

int fibonacci(int x) {
	if (x == 1) return 1; //1과 2는 피보나치에서 뭘 더해서 나오는 수가 아니기때문에 거른다
	if (x == 2) return 1;
	if (d[x] != 0){ 
        return d[x]; //목표치 배열이 생성됐으면 값반환
    }
	return d[x] = fibonacci(x - 1) + fibonacci(x - 2); //구한 값을 배열 d에 저장
}

int main() {
	printf("%d", fibonacci(50));
}

 

참고 개념정리

dbstndi6316.tistory.com/35

[개념정리] DP 동적프로그래밍