[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;
}


[Linux] 쉘 스크립트에서 멀티프로세스(혹은 스레드) 기능 사용하기

> 백그라운드로 명령어를 실행해서 병렬적으로 실행되는 멀티 프로세스 환경을 만들어보자.## 환경- Linux 기반 시스템- Bash shell(/bin/bash)## 멀티프로세스? 병렬처리? 멀티스레드? 백그라운드 프로세스?- 여기서 진행할 방식...… Continue reading