동적계획법(Dynamic Programming)

동적계획법(Dynamic Programming)이라는 것은 알고리즘에서 아주 자주 등장하는 주제입니다. 줄여서 DP라고도 부릅니다.

DP의 특징은 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있습니다. 그래서 "답을 여러 번 계산하는 대신 한번 만 계산한다!" 입니다.  

개인적으로 DP를 보면 항상 먼저 떠오르는게 바로 재활용이라고 생각합니다. 재활용을 통해서 속도를 빠르게 향상 시킬 수 있는 방법입니다.

어떻게 재활용을 할 수 있을까요? 가장 유명한 피보나치 수열을 한 번 보도록 해봅시다. 피보나치의 정의는 아래와 같습니다. 간단합니다.

이 피보나치 수열을 재귀함수로 정의해보겠습니다. 

int fibo(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fibo(n - 1) + fibo(n - 2);
}

이런식으로 정의가 될 것 같네요. 여기서 n은 무조건 양수라고 가정하겠습니다. 음수는 귀찮습니다. 만약 fibo(5)라는 값을 계산하려면 어떤 과정을 거칠까요?

fibo(5) = fibo(4) + fibo(3) 라는 것을 알 수 있고 이제 fibo(4)와 fibo(3)을 더해주기만 하면 됩니다.

그럼 왼쪽 fibo(4)부터 차근 차근히 계산을 해보도록 하겠습니다. 노가다로 해보겠습니다.

fibo(4) = fibo(3) + fibo(2) 

이것도 역시 fibo(3), fibo(2)를 계산해야 되겠군요

fibo(3) = fibo(2) + fibo(1) 이 되겠습니다.

fibo(2) = fibo(1) + fibo(0) 이 되어서 fibo(2) = 1이라는 것을 알게 됩니다.

그렇다면 fibo(3) = fibo(2) + fibo(1) 이니까 1+1 해서 fibo(3) = 2라는 것을 알 수 있겠네요.

fibo(4) = fibo(3) + fibo(2) 랍니다. 여러 분, 이제 슬슬 감이 오고 있나요? 노가다 하기 싫습니다.

fibo(4) = 2 + fibo(2)라는 것이 됩니다. fibo(3)을 방금전에 계산했거든요. 그러면 오른쪽 fibo(2)를 구해보도록 합시다.

fibo(2) = fibo(1) + fibo(0) 으로 fibo(2)=1입니다.

그럼 fibo(4) = 2+ 1 = 3 이라는 결과가 나옵니다. 이제 fibo(4) 구한 겁니다.

이제 fibo(3)을 구해볼까요?

이제 손가락이 아파서 못할 거 같고요

fibo(3) 뭐라고 했지요? 아까 계산했는데 말입니다.

2가 나왔죠?

이 같은 노가다를 막기 위한 것이 바로 DP의 큰 역할이라고 할 수 있겠습니다. 만약 위의 저 코드를 통해서 fibo(40)을 계산한다면 얼마나 걸릴까요? 아마 계산했던 결과를 또 계산하고 앉아있으니 오래 걸릴거라는 걸 짐작할 수 있나요?

네, 오래 걸립니다. 우리는 이제 계산된 값을 재활용 합시다. 이렇게요.

int dp[50];
int fibo(int n) {
	
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (dp[n] != -1) return dp[n];
	return dp[n] = (fibo(n - 1) + fibo(n - 2));
}
int main() {
	memset(dp, -1, sizeof(dp));
	printf("fibo(40)=%d\n", fibo(40));
}

어떻습니까? 맨 처음 초기화값은 -1입니다. memset함수에 주목합시다. 이 함수는 dp라는 배열을 -1이라는 값으로 전부 초기화 시키는 역할을 하는 것이랍니다. 처음 계산하는 값이라면 dp[n]에 -1이라는 값이 들어있을 겁니다. 그렇지 않을까요? 이해 되십니까?

C언어 문자열 처리 함수

문자열 처리는 어느 언어에서나 중요하죠.

우선 C언어에서 문자열을 처리하려면 string.h를 반드시 포함해야합니다. 

※이제부터 설명하는 함수들은 보안적인 취약점이 발견되있는 함수들이 있습니다. 테스트를 해보시기 전에 SDL을 NO로 설정하세요.

Project - [Project Name] Properties - (왼쪽) C/C++ - SDL checks : No
또는 전처리 구문을 사용합니다.

#define _SECURE_CRT_NO_WARNINGS

가장 많이 쓰이는 4개의 함수에 대해서만 우선 알아 보도록 합시다.

● 문자열 길이  size_t strlen(const char *str) 

문자열을 input으로 넣어주면 반환되는 문자열의 길이가 나오게 됩니다. NULL문자

까지가 아닌 순수 문자열의 길이를 반환해주게 됩니다.

ex)

char str[20] = "hello, world";

int len = strlen(str);

● 문자열 연결 char* strcat(char *_Destination, const char* _Source)

문자열을 합치게 됩니다. _Destination 뒤에 _Source를 이어주게 됩니다. 주의해야 할 점은 매개변수로 _Destination은 배열로써 그 크기가 지정되어진 문자열이어야 합니다. 

ex) 

char dst[30]="dst";    //char *dst="dst"; 로 바꾸게 되면 error가 나오게 됩니다.

char src[30]="src";

printf("%s \n", strcat(dst,src));

● 문자열 비교 int strcmp(const char *_Str1, const char *_Str2)

문자열을 비교하게 됩니다.  

_Str1이 _Str2보다 사전순으로 나중에 등장하면 1

_Str1이 _Str2보다 사전순으로 먼저 등장하면 -1

_Str1과 _Str2와 사전순이 같다면 0

보통 문자열을 비교할때 이 함수를 사용하는데 두 문자열이 같다면 0이 나오기 때문에 문자열이 같은 지 if문에서 확인하려면 !strcmp(str1,str2)로 확인해야 합니다. 왜냐면 str1,str2가 같다면 0(FALSE)가 반환되기 때문이죠.

● 문자열 복사 char* strcpy(char *_Dest, const char *_Source)

문자열 _Source를 _Dest에 복사합니다. strcat와 마찬가지로 _Dest는 배열의 형태로 넘겨받습니다. _Dest에 _Source문자열을 합치기 때문에 _Dest는 _Source의 문자열을 포함할 만큼 크기가 커야합니다.

ex)

char _dest[20] = "hello,";

char _src[10] = "world";

strcat(_dest, _src);

위 네 가지 함수를 실제로 적용시켜볼까요??

#include<stdio.h>
#include<string.h>

int main() {

	char country[32] = "korea";
	char south[32] = "south";
	char southkorea[32] = "southkorea";
	char south_korea[32] = "South Korea";

	printf("문자열의 길이 : %d\n", strlen(country));

	strcat(south, country);
	printf("문자열 결합 : %s\n", south);

	printf("문자열 비교 : ");
	if (!strcmp(south, southkorea)) {
		printf("%s = %s\n", south, southkorea);
	}
	else {
		printf("%s != %s\n", south, southkorea);
	}


	strcpy(southkorea, south_korea);
	printf("문자열 복사 : %s\n", southkorea);

}

그리고 그 결과입니다.

이상으로 문자열과 관련해서 자주쓰이는 함수 몇가지를 살펴보았습니다.