입 달린 감자의 코딩 블로그

자 사진을 보자

 어렸을 때 집에 있었는데 이게 하노이 타워이다.

 원반은 한 번에 하나씩만 옮길 수 있고 작은 원반의 위에 큰 원반이 있으면 안된다는 규칙을 가지면서 첫번째 막대기에서 세번째 막대기로 옮기면 된다.

자 어떻게 할 것인가?  일단 3개를 가지고 해보자.

그림이 불편하게 생겼지만 대충 알아 먹을만 할 것이다.

그림에서 규칙을 찾아보면 쉽게 재귀적으로 표현 가능할 것이다.

1. 일단 제일 큰 원반 위에 있는 작은 원반들은 모두 두 번째 막대기로 이동시킨다.

2. 그 다음 제일 큰 원반은 세 번째 막대기로 이동시킨다.

3. 두 번째 막대기에 있던 작은 원반들을 세 번째 원반으로 이동시킨다.

규칙은 찾았고 이제 프로그래밍 해보자.

#include <stdio.h>

void Hanoi(int n, char from, char by, char to) {
	if (n == 1)
		printf("%d 번째 원반 %c에서 %c로 이동\n",n,from,to);
	else {
		Hanoi(n - 1, from, to, by); //1번 규칙
		printf("%d 번째 원반 %c에서 %c로 이동\n", n, from, to); //2번 규칙
		Hanoi(n - 1, by, from, to); //3번 규칙
	}
}

int main() {
	Hanoi(3, 'A', 'B', 'C');  //A,B,C는 막대기
}

조금 어렵다. 설명이 부족했나?

"윤성우의 열혈 자료구조" 이 책을 한번 사서 봐라. 자료구조 기본기 공부하기엔 참 좋은 책인 것 같다.

오늘은 피보나치 수열에 대해 알아보자.

점화식에 대한 정의는 F(0)​=0, F(1)​=1, F(n+2)​=F(n+1​)+F(n)​ 과 같다.

(0) 1 1 2 3 5 8 13 21 ... 과 같이 나타내며 다음 항은 13 + 21 로 34가 나옴을 알 수 있다.

피보나치 수열도 재귀함수로 표현하면 간단하지만 그 전에 반복문으로 한번 프로그래밍 해보자~

#include <stdio.h>

int Fibo(int n) {
	int arr[100];

	arr[0] = 0; arr[1] = 1;

	for (int i = 2; i <= n; i++) {
		arr[i] = arr[i - 1] + arr[i - 2]; //점화식 활용
	}

	return arr[n];
}

자 보시다시피 반복을 통해 다음 항을 구하는 방식이다. 다음은 재귀적으로 구현해보자

#include <stdio.h>

int Fibo(int n) {
	if (n == 0)
		return 0;  //0번째 항은 0
	else if (n == 1)
		return 1;  //1번째 항은 1
	else
		return Fibo(n - 1) + Fibo(n - 2);  //점화식 활용
}

반복문 보다 간단하다는 것을 알 수 있다.

재귀함수의 예제는 다양하게 있다. 그 중에 팩토리얼, 피보나치 수열, 하노이 타워 정도 프로그래밍 해볼것이며 오늘은 팩토리얼에 대해 구현해보겠다.

재귀함수란 자기 자신을 참조하는 함수 이다. 자 바로 예를 들어보자.

n! 은 n 팩토리얼로 n x (n-1) x (n-2) x ... x 1 을 계산한다. 자 처음보는 경우 나라면 반복문으로 접근할 것 같다. 이런 식으로 말이다.

#include <stdio.h>

int Factorial(int n) {
	int sum = 1;

	for (int i = n; i > 0; i--) {
		sum *= i;
	}

	return sum;
}

하지만 우리가 배우고 있는 것은 재귀함수 이므로 자기 자신을 참조하게 프로그래밍 해보겠다.

#include <stdio.h>

int Factorial(int n) {
	if (n == 0)
		return 1;
	else
		return n * Factorial(n - 1);
}

return n * Factorial(n-1); 에서 자기 참조가 일어났다. 이러한 특성을 가진 함수를 재귀함수라고 하는 것이다.

비교적 반복문 보다 간단한 것을 알 수 있다.

다음 시간엔 재귀함수의 다른 예제들을 가지고 돌아오겠다. ㅂㅇㅂㅇ

BFS는 너비 우선 탐색으로 가까운 노드부터 탐색하는 알고리즘이다. 

자 또 그림을 한번 보자.

DFS 할 때와 같은 그래프이다. 위 그림과 같이 BFS 는 큐를 사용하고 방문 후 숫자를 큐에 저장한다. 그 후 enqueue 된 숫자가 dequeue 되면서 연결된 다음 숫자를 enqueue 해준다.

아래는 코드이다.

#include <stdio.h>
#include <queue>
#include<vector>

using namespace std;

bool visited[9];
vector<int> graph[9];

void BFS(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		printf("%d ", x);

		for (int i = 0; i < graph[x].size(); i++) {
			int y = graph[x][i];
			if (!visited[y]) {
				q.push(y);
				visited[y] = true;
			}
		}
	}
}

int main() {
	graph[1].push_back(2);
	graph[1].push_back(6);
	graph[1].push_back(7);

	graph[2].push_back(1);
	graph[2].push_back(8);

	graph[3].push_back(8);

	graph[4].push_back(8);

	graph[5].push_back(6);
	graph[5].push_back(7);

	graph[6].push_back(1);
	graph[6].push_back(5);

	graph[7].push_back(5);
	graph[7].push_back(1);

	graph[8].push_back(3);
	graph[8].push_back(4);

	BFS(1);
}

DFS는 깊이 우선 탐색으로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그냥 한 우물만 판다? 이런 느낌으로 생각하고 들어가자.

자 나름 이해를 돕기 위해 허접(?)하지만 그림을 그려 이해 해보자. 

이해가 쏙쏙 되지 않은가?????? 아니겠지? 나름 수고스럽게 그렸다.

이제 위 과정을 코딩해보자.

#include <stdio.h>
#include <stack>
#include <vector>

using namespace std;

bool visited[12];
vector<int> graph[12];

void DFS(int start) {
	stack<int> s; //그림에서 숫자 들어간 바구니 
	s.push(start); 
	visited[start] = true;
	printf("%d ", start);

	while (!s.empty()) {
		int x = s.top();
		s.pop();

		for (int i = 0; i < graph[x].size(); i++) {
			int y = graph[x][i];
			if (visited[y] == false) {
				printf("%d ", y);
				visited[y] = true;

				s.push(x);
				s.push(y);
				break;
			}
		}
	}
}

int main() {
	graph[1].push_back(2); //여기서부터
	graph[1].push_back(6);
	graph[1].push_back(7);

	graph[2].push_back(1);
	graph[2].push_back(8);

	graph[3].push_back(8);

	graph[4].push_back(8);

	graph[5].push_back(6);
	graph[5].push_back(7);

	graph[6].push_back(1);
	graph[6].push_back(5);

	graph[7].push_back(5);
	graph[7].push_back(1);

	graph[8].push_back(3);
	graph[8].push_back(4); //여기까지는 그래프를 구현

	DFS(1); //DFS 실행
	
}

뭐 반복문을 활용하여 DFS를 구현해보았다. 그런데 재귀를 사용하면 더 간단하게 코딩할 수 있지 않을까 하는 의구심에 재귀로도 표현해보았다.

void RecursiveDFS(int x) {
	visited[x] = true;
	printf("%d ",x);

	for (int i = 0; i < graph[x].size(); i++) {
		int y = graph[x][i];
		if (!visited[y])
			RecursiveDFS(y);
	}
}

편안...

나도 공부하는 입장이기 때문에 설명하는 것에 부족함이 있을 수도 있다. 앞으로 개선해가야징~

Partial Order Relation 은 부분순서관계로 반사관계, 반대칭관계, 추이관계가 성립하는 관계이다.

1  1  1

0  1  1

0  0  1

위 행렬을 보자

반사관계인가?      맞다

대칭관계인가?      아니다        반대칭관계인가? 맞다

추이관계인가?      맞다

이 조건을 만족하면 부분순서관계가 성립한다. 위의 관계들은 모두 앞서서 구현해보았다.

자 앞서서 했던 것들 다 불러 모으자~

반사관계

int SymmetricRelation(int arr[][3]) {
	int a = 0;

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (arr[i][j] == arr[j][i])
				a++;
		}
	}

	if (a == 9)
		return 2; //대칭
	else if (a == 3)
		return 1; //반대칭
	else
		return 0;  //둘 다 아님

}

대칭관계

int ReflexiveRelation(int arr[][3]) { //크기가 3인 정사각행렬로 가정
	int a = 0;
	int b = 0;
	int c = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == j && arr[i][j] == 1)
				a++;
			else if (i == j && arr[i][j] == 0)
				b++;
		}
	}
	if (a == 3)
		return 2; //반사
	else if (b == 3)
		return 1; //비반사
	else
		return 0; //둘 다 아님

}

추이관계

void MatrixMul(int mul[][3], int arr1[][3], int arr2[][3]) {//행렬의 곱셈을 논리곱으로 표현
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				mul[i][j] |= arr1[i][k] & arr2[k][j];
			}
		}
	}

}

int TransitiveRelation(int arr[][3]) {//행렬의 논리곱을 활용하여 추이관계 표현
	int result[3][3] = { 0 };
	MatrixMul(result, arr, arr);
	MatrixMul(result, result, arr); //R^3의 표현
	int a = 0;

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (arr[i][j] == 1 || result[i][j] == arr[i][j]) //포함관계 이므로 R이 1이거나 R과 R^3 같다면 a를 추가하는 방식으로 구현해보았다.
				a++;
		}
	}

	if (a == 9)
		return 1; //추이
	else
		return 0; //추이 아님
}

반환값이 있게끔 약간 수정했다.

자 다 모으니 아주 간단하게 코딩할 수 있다.

부분순서관계

void PartialOrderRelation(int arr[][3]) {
	if (ReflexiveRelation(arr) == 2 && SymemetricRelation(arr) == 1 && TransitiveRelation(arr) == 1) {
		printf("부분순서관계!");
	}
	else {
		printf("부분순서관계아님!");
	}
}

int main() {
	int arr[][3] = { {1,1,1},{0,1,1},{0,0,1} };

	PartialOrderRelation(arr);
}

써놓으니 드래곤볼 마냥 모아서 완성품을 만드네... 뿌듯