다이나믹 알고리즘_타일 채우기 [1/2]

[ 다이나믹 알고리즘이란? ]

• 반복되는 작업 없이 알고리즘 수행
• 이미 한 번 계산한 경우 그 값을 어딘가에 저장해뒀다가 재활용하는 구조​

의미만 보면 간단합니다. 재귀함수같이 동일 알고리즘을 arguments만 바꿔가면서 계속 수행할 때, 이전 값의 결과를 가져와서 수행할 수 있도록 만들어준다는 것이죠. 사실 뭔가 거창한 이름이지만 이제까지 해왔던 로직들과 그리 다를 건 없는 것 같습니다. 최대한 효율적으로 수행한다 정도로 이해하면 될 것 같습니다.

​

그럼 타일채우기 문제를 한 번 풀어보도록 하겠습니다.

과제는 유투브 '동빈나'님의 알고리즘 강의를 참고하였습니다.

 

---

 

그려보니 [1,2] 로 시작하는 피보나치 수열이 나옵니다. 간단한건데 한참을 고민했네요..

오른쪽으로 한칸 늘어나면 (n -1) 경우의 수와 똑같습니다. 양 옆으로 두 번 보낼 수 있지 않겠느냐 할 수 있겠지만 그 모양은 어차피 (n-1)에 있어서요. 그럼 두 칸이 늘어나면 한칸 늘어날 때 보다 위 아래 타일 모양 하나의 경우밖에 없으니 또 이건 (n-2) 경우의 수와 같습니다. 그래서 (n-1)의 결과와 (n-2)의 결과를 합쳐주면 n의 경우의 수가 나오게 됩니다.

​

이 경우는 바닥 넓이와 타일의 높이가 같을 때의 문제라 쉬운 듯하네요. 바닥이 n * n으로 늘어난다거나 하면 또 골치가 아파질 것 같은 느낌이..

 

 

---

 

일반적인 배열로 풀어본 방식입니다.

 

#include <stdio.h>
#define FLOOR 10

void main()
{
	int tile_arr[FLOOR] = { 1,2 };	// 초반 두 개는 수기로 써줘야 함
		
	for (int i = 2; i < FLOOR; i++)
		tile_arr[i] = tile_arr[i - 1] + tile_arr[i - 2];
	
	for (int i = 0; i < FLOOR; i++)
		printf("\n 타일넓이 : 2 * %d, 경우의 수 : %d\n", 
			i + 1, tile_arr[i]);
}

 

---

 

재귀함수를 사용한 방식입니다.

 

 

재귀함수 아래 순서대로 생각하면 편하게 사용할 수 있습니다.

1. 탈출 조건 작성 (변화하는 arguments 기준으로 언제 탈출할 것인지)
2. 수행할 내용
3. 재귀함수 (새로운 arguments 제공)
4. 리턴

또는 아래에서처럼 2와 3번 순서를 바꿔서 일단 재귀함수를 타고 끝까지 내려가서 하나씩 빠져나오면서 함수 내용을 실행시키고 리턴하는 방법이 있습니다.

 

#include <stdio.h>
#define FLOOR 10
void tile_find(int* arr, int i);

void main()
{
	int tile_arr[FLOOR] = { 0 };	// 모두 0으로 초기화
	
	tile_find(tile_arr, FLOOR - 1);

	for (int i = 0; i < FLOOR; i++)
		printf("\n 타일넓이 : 2 * %d, 경우의 수 : %d",
			i + 1, tile_arr[i]);

	printf("\n");
}

void tile_find(int* arr, int i)
{
	if (i < 0)
		return;
	tile_find(arr, i - 1);
	if (i == 0)
	{
		arr[i] = 1;
		return;
	}
	else if (i == 1)
	{
		arr[i] = 2;
		return;
	}	
	arr[i] = arr[i - 1] + arr[i - 2];
}

 

---

 

강의 코드입니다. 수행 횟수는 동일하지만 조금 더 코드가 간략해졌습니다. 다만 해당 코드는 arr[0]과 arr[1]에는 실제로 값이 배열에 입력되지 않기 때문에 마지막 값을 뽑을 때만 유효합니다. 물론 출력만 하는거라면 함수와 출력 부분을 조금만 수정해서 같은 결과를 뽑을 수는 있습니다.

 

 

저처럼 처음에 재귀함수 사용을 어려워하는 사람이 있을까봐 설명 추가..

 

#include <stdio.h>
#define FLOOR 10
int tile_find(int* arr, int i);

void main()
{
	int tile_arr[FLOOR] = { 0 };	// 모두 0으로 초기화
	
	tile_find(tile_arr, FLOOR - 1);

	for (int i = 0; i < FLOOR; i++)
		printf("\n 타일넓이 : 2 * %d, 경우의 수 : %d",
			i + 1, tile_arr[i]);

	printf("\n");
}

int tile_find(int* arr, int i)
{
	if (i == 0)
		return 1;
	if (i == 1)
		return 2;
	if (arr[i] != 0)
		return arr[i];
	return arr[i] = tile_find(arr, i - 1) + tile_find(arr, i - 2);
}

 

---

 

사실 간단한 규칙(결과가 규칙적)에 의해서 움직이는 반복문은 재귀함수보다는 일반 반복문이 더 효율적인 것 같습니다. 경험상(아주 짧지만..) 재귀함수는 복잡한 계산결과(결과가 불규칙)가 다시 해당 함수의 arguments로 들어가야할 때 더 효율적인 것으로 판단됩니다.