[Algorithm] 동적계획법(Dynamic Programming)과 재귀함수(Recursion)를 통해 피보나치 수열 구하기

n번째 피보나치 수열을 동적계획법 그리고 재귀함수를 통해서 각각 구현해보자


환경

  • C, C++
  • 동적계획법(Dynamic Programming)에 대한 이해
  • 재귀함수(Recursion)에 대한 이해


재귀함수란?

  • 재귀함수 : 재귀함수란 자신의 함수를 재호출하여 실행하는 함수를 의미합니다. 주로 분할정복과 같이 문제를 작은 부분으로 나누어서 문제를 해결할 때 많이 사용합니다.


동적계획법이란?

  • 동적계획법(DP) : 동적계획법이란 문제를 작게 쪼개서 작은 문제부터 하나하나 해결한 해를 통해 모아서 큰 문제를 해결하는 방법을 의미합니다.


재귀함수(Recursion)로 구하기

  • Top-down 방식 : 큰 문제를 작은 문제로 나누면서 해결하는 방식

fibonacci_by_recursion.c


#include <stdio.h>

int fibonacci_recursion(int n){

	if (n == 0){
		return 1;
	}

	else if(n == 1){
		return 1;
	}

	else{
		return fibonacci_recursion(n-1) + fibonacci_recursion(n-2);
	}


}

int main(){

	int i;

	for(i=0; i<20; i++){
		printf("%d ",fibonacci_recursion(i));
	}
	printf("\n");

    return 0;
}


동적계획법(Dynamic Programming)으로 구하기

  • Bottom-up 방식 : 작은 문제부터 하나씩 해결해 올라가는 방식

fibonacci_by_dp.c


#include <stdio.h>

int dp_array[100];

void fibonacci_dp(int n){

	int i;

	dp_array[0] = 1;
	dp_array[1] = 1;

	for(i=2; i< n; i++){
		dp_array[i] = dp_array[i-1] + dp_array[i-2];
	}

}


int main(){

	int i;

	fibonacci_dp(20);

	for(i=0; i<20; i++){
		printf("%d ", dp_array[i]);
	}
	printf("\n");

    return 0;
}


[Docker] 도커(Docker) 이미지 이름과 태그 목록 가져오기

> 도커(Docker) 이미지 이름과 태그 목록을 awk과 tail 명령어를 이용해 가져오는 방법을 알아보자## 환경- Linux 기반 시스템- Bash shell(/bin/bash)- Docker- awk, tail 명령어## 도커(Docker...… Continue reading