Crocodile Tears

[알고리즘] 이진트리(Binary Tree)

* 리스트 구현

1. 이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽(left)과 오른쪽(right)으로 불린다. 이진 트리는 이진 탐색 트리와 이진 힙의 구현에 흔히 쓰인다.( Wiki )

From : http://www.silverwolf.co.kr/algorithm/4810

2. 순회

- 연결 리스트와 1차원 배열과 같은 선형 자료 구조에서는 한 가지의 논리적인 순회 방법만이 존재하지만, 

트리 구조의 순회에는 많은 방법이 존재한다. 

이진 트리의 루트 노드에서 시작해서, 세 가지 주요 단계를 거치며 순회를 진행하는데, 

그 단계에는 현재 노드를 방문하는 것, 

왼쪽 자식 노들 순회하는 것과 오른쪽 자식 노드를 순회하는 것이 있다. 이러한 과정은 재귀로 쉽게 설명할 수 있다.(Wiki)

* Images are from Wiki

A. 전위순회

- 노드 방문 -> 왼쪽 서브 트리를 전위 순회 -> 오른쪽 서브 트리를 전위 순회

B. 중위순회

- 왼쪽 서브 트리를 중위 순회 ->노드 방문 -> 오른쪽 서브 트리를 중위 순회

C. 후위순회

- 왼쪽 서브 트리를 후위 순회 -> 오른쪽 서브 트리를 후위 순회 -> 노드 방문

< BT.h >

#pragma once

typedef int BTData;

typedef struct _bTreeNode
{
	_bTreeNode *left;
	_bTreeNode *right;

	BTData data;
} BTreeNode;

// 노드(트리) 생성
BTreeNode* MakeBTreeNode( void );
// 데이터 반환
BTData GetData( BTreeNode *bt );
// 데이터 설정
void SetData( BTreeNode *bt, BTData data );
// 왼쪽 자식 얻기
BTreeNode* GetLeftSubTree( BTreeNode *bt );
// 오른쪽 자식 얻기
BTreeNode* GetRightSubTree( BTreeNode *bt );
// 왼쪽 자식 설정
void MakeLeftSubTree( BTreeNode *main, BTreeNode *sub );
// 오른쪽 자식 설정
void MakeRightSubTree( BTreeNode *main, BTreeNode *sub );
// 방문시 행할 함수포인터
typedef void VisitFuncPtr( BTData data );
// 전위 순회
void PreorderTraverse( BTreeNode *bt, VisitFuncPtr action );
// 중위 순회
void InorderTrasverse( BTreeNode *bt, VisitFuncPtr action );
// 후위 순회
void PostorderTraverse( BTreeNode *bt, VisitFuncPtr action );
// 트리 삭제
void DeleteTree( BTreeNode *bt );

< BT.cpp >

#include "BT.h"
#include 


BTreeNode* MakeBTreeNode( void )
{
	BTreeNode *node = (BTreeNode*)malloc( sizeof( BTreeNode ) );
	node->left = nullptr;
	node->right = nullptr;
	node->data = 0;

	return node;
}

BTData GetData( BTreeNode *bt )
{
	if ( bt == nullptr ) return -1;

	return bt->data;
}

void SetData( BTreeNode *bt, BTData data )
{
	if ( bt == nullptr ) return;

	bt->data = data;
}

BTreeNode* GetLeftSubTree( BTreeNode *bt )
{
	if ( bt == nullptr ) return nullptr;

	return bt->left;
}

BTreeNode* GetRightSubTree( BTreeNode *bt )
{
	if ( bt == nullptr ) return nullptr;

	return bt->right;
}
/// free하는 노드의 자식들이 있으면 메모리 누수남!
void MakeLeftSubTree( BTreeNode *main, BTreeNode *sub )
{
	if ( main == nullptr ) return;

	/// 이렇게 하면 메모리 누수
	//if ( main->left != nullptr )
	//	free( main->left );
	if ( main->left != nullptr )
		DeleteTree( main->left );

	main->left = sub;
}

void MakeRightSubTree( BTreeNode *main, BTreeNode *sub )
{
	if ( main == nullptr ) return;
	
	/// 이렇게 하면 메모리 누수
	//if ( main->right != nullptr )
	//	free( main->right );
	if ( main->right != nullptr )
		DeleteTree( main->right );

	main->right = sub;
}

void PreorderTraverse( BTreeNode *bt, VisitFuncPtr action )
{
	if ( bt == nullptr )
		return;

	action( bt->data );
	PreorderTraverse( bt->left, action );
	PreorderTraverse( bt->right, action );
}

void InorderTrasverse( BTreeNode *bt, VisitFuncPtr action )
{
	if ( bt == nullptr )
		return;

	InorderTrasverse( bt->left, action );
	action( bt->data );
	InorderTrasverse( bt->right, action );
}

void PostorderTraverse( BTreeNode *bt, VisitFuncPtr action )
{
	if ( bt == nullptr )
		return;

	PostorderTraverse( bt->left, action );
	PostorderTraverse( bt->right, action );
	action( bt->data );
}

void DeleteTree( BTreeNode *bt )
{
	if ( bt == nullptr )
		return;

	DeleteTree( bt->left );
	DeleteTree( bt->right );
	free( bt );
}

< BTMain.cpp >

#include "BT.h"
#include 

//void InorderTraverse( BTreeNode *bt )
//{
//	if ( bt == nullptr )
//		return;
//
//	InorderTraverse( bt->left );
//	printf( "%d \n", bt->data );
//	InorderTraverse( bt->right );
//}
//
//void PreorderTraverse( BTreeNode *bt )
//{
//	if ( bt == nullptr )
//		return;
//
//	printf( "%d \n", bt->data );
//	PreorderTraverse( bt->left );
//	PreorderTraverse( bt->right );
//}
//
//void PostorderTraverse( BTreeNode *bt )
//{
//	if ( bt == nullptr )
//		return;
//
//	PostorderTraverse( bt->left );
//	PostorderTraverse( bt->right );
//	printf( "%d \n", bt->data );
//}

void ShowIntData( int data );

int main( void )
{
	BTreeNode *bt1 = MakeBTreeNode();
	BTreeNode *bt2 = MakeBTreeNode();
	BTreeNode *bt3 = MakeBTreeNode();
	BTreeNode *bt4 = MakeBTreeNode();
	BTreeNode *bt5 = MakeBTreeNode();
	BTreeNode *bt6 = MakeBTreeNode();

	SetData( bt1, 1 );
	SetData( bt2, 2 );
	SetData( bt3, 3 );
	SetData( bt4, 4 );
	SetData( bt5, 4 );
	SetData( bt6, 4 );

	MakeLeftSubTree( bt1, bt2 );
	MakeRightSubTree( bt1, bt3 );
	MakeLeftSubTree( bt2, bt4 );
	MakeRightSubTree( bt2, bt5 );
	MakeRightSubTree( bt3, bt6 );

	PreorderTraverse( bt1, ShowIntData );
	printf( "\n" );
	InorderTrasverse( bt1, ShowIntData );
	printf( "\n" );
	PostorderTraverse( bt1, ShowIntData );

	DeleteTree( bt1 );

	return 0;
}

void ShowIntData( int data )
{
	printf( "%d ", data );
}

From : 열혈 C 자료구조

[알고리즘] 선형검색(linear search)

선형검색(탐색)은 주어진 데이터에서 앞에서부터 순차적으로 

원하는 값을 찾는 방식입니다.

그렇기 때문에 시간복잡도는 O(n)이 됩니다.

구현이 매우 간단하지만, 

많은 데이터에서 검색을 하기에는 좀 부담이 되는 알고리즘 입니다.

데이터가 많을 때에는 이진이나 헤시 탐색등(logN)을 이용하는게 좋습니다.

< [5, 2, 13, 1, 8] 에서 1을 검색하는 과정 >

< 선형검색 코드 >

#include 
using namespace std;

// Using while
int linearSearch(int arr[], int length, int target)
{
	int nIndex = 0;
	while(nIndex < length)
	{
		if(arr[nIndex] == target)
			return arr[nIndex];
		nIndex++;
	}

	return -1;
}

int linearSearchWithFor(int arr[], int length, int target)
{
	for(int nIndex = 0; nIndex < length; nIndex++)
	{
		if(arr[nIndex] == target) return arr[nIndex];
	}

	return -1;
}

int main()
{	
	int arr[] = {5, 2, 13, 1, 8, 55, 29, 33};
	int target = 33;

	int nFound = linearSearch(arr, 8, target);

	if(nFound >= 0)
	{
		cout << "Found!!" << endl;
	}
	else
	{
		cout << "Not found!!" << endl;
	}

	return 0;
}

삽입정렬(Insertion Sort)

삽입정렬(Insertion Sort) 알고리즘은 

배열의 모든 데이터들을 앞에서부터 차례대로 정렬시키면서 나아가는 방식입니다.

즉, 앞에서부터 차례대로 정렬해 나간다고 보면 되겠습니다.

위키 참고하면 많은 도움이 되실꺼에요. <- 클릭하면 이동합니다.

위키를 보시면 memcpy()를 사용했을 때 25~30% 빠르게 처리된다고 합니다.

삽입정렬 알고리즘의 작동 과정은 다음과 같습니다. (Swap을 하여 처리하는 경우입니다)

< [ 4, -8, 3, 1 ] 정렬 >

위 그림을 보시면 앞에서부터 정렬이 되어 갑니다.

이렇게 순차적으로 정렬을 해 나가면서, 

자신과 비교후 조건이 충족되면 자기 자신을 앞에다 삽입을 합니다.

위를 코드로 보시면 다음과 같습니다.

< C++ 코드 >

#include 
using namespace std;

void insertionSort(int arr[], int length)
{
	int i, j, tmp;
	for(i = 1; i < length; i++)
	{
		j = i;
		while(j > 0 && arr[j - 1] > arr[j])
		{
			tmp = arr[j];
			arr[j] = arr[j - 1];
			arr[j -1] = tmp;
			j--;
		}
	}
}

int main()
{
	int values[] = {4, -8, 3, 1};

	cout << "Before sorting" << endl;
	for(int i = 0; i < 4; i++)
	{
		cout << values[i];
		if(i < 3)
			cout << ", ";
		else 
			cout << endl;
	}

	// sort
	insertionSort(values, 4);
	cout << "After sorting" << endl;
	for(int i = 0; i < 4; i++)
	{
		cout << values[i];
		if(i < 3)
			cout << ", ";
		else 
			cout << endl;
	}
}

< 결과 >

잘못된 부분이 있으면 언제든 리플해주시기 바랍니다.

참고 : http://www.algolist.net/Algorithms/Sorting/Insertion_sort

선택정렬(Selection Sort)

선택 정렬(Selection Sort)은 버블정렬(Bubble Sort)와 같은 시간복잡도(O(n2))를 가지지만, 

버블 정렬과는 조금 달리 불안정(Unstable)한 알고리즘 입니다. 무슨말이냐면, 

예를 들어 {8, 7, 5, 5, 6} 이 있을 경우 정렬한 후에 5와 5의 위치가 바뀔수도 있다는 거랍니다.

즉, 같은 내용을 가지는 키 값들이 정렬 후에도 순서가 유지되는걸 말합니다.

선택정렬은 다음과 같은 과정을 거칩니다.

< [ 8, 2, -1, 5, 4 ] 선택정렬 >

선택 정렬(Selection Sort) 알고리즘은 최초 한 값을 선택하고, 다른 값들과 비교한 후 작은 값이 있으면

그 값을 저장하고 마지막까지 갔다면, 최초 선택한 값과 스왑하는 방식입니다.

글로 쓰니까 어렵네요. 그림이 도움이 될꺼에요.(시간상 2, 3회전은 스킵하였습니다)

< C++ 코드 >

#include 
using namespace std;

void selectionSort(int arr[], int n)
{
	int minIndex = 0;
	for(int i = 0; i < n -1; i++)
	{
		minIndex = i;
		for(int j = i + 1; j < n; j++)
		{
			if(arr[minIndex] > arr[j])
				minIndex = j;
		}

		if( minIndex != i)
		{
			int temp = arr[minIndex];
			arr[minIndex] = arr[i];
			arr[i] = temp;
		}
	}
}

int main()
{
	int values[] = {8, 2, -1, 5, 4};

	cout << "Before sorting" << endl;
	for(int i = 0; i < 5; i++)
	{
		cout << values[i];
		if(i < 4)
			cout << ", ";
		else 
			cout << endl;
	}

	// sort
	selectionSort(values, 5);
	cout << "After sorting" << endl;
	for(int i = 0; i < 5; i++)
	{
		cout << values[i];
		if(i < 4)
			cout << ", ";
		else 
			cout << endl;
	}
}

< 결과 >

참고 : http://www.algolist.net/

버블정렬(Bubble Sort)

기본적으로 가장 간단한 정렬이라 생각이 듭니다.

앞 뒤를 비교해서 우선순위를 정해 교체하는 알고리즘이죠.

버블정렬(Bubble Sort)의 시간복잡도는 O(n2)가 됩니다. 분기문을 두번 돌아야 하니까요.

{3, 2, 5, 4, 1} 을 버블정렬을 통해 정렬을 하면 다음과 같은 과정을 거치게 됩니다.

< [ 3, 2, 5, 4, 1] 정렬 >

녹색은 이미 정렬된 상태이므로 그대로 두고, 빨간색은 교체(스왑) 시켜줍니다.

그리고 주황색은 이미 정렬된 상태로 건드리지 않는다는 의미 입니다.

< C++ 코드 >

#include 
using namespace std;

void bubbleSort(int arr[], int n)
{
	bool swapped = true;
	int j= 0;
	int tmp = 0;
	while(swapped)
	{
		swapped = false;
		j++;
		for(int i = 0; i < n - j; i++)
		{
			// 이 조건을 변경하여 오름차순, 내림차순을 설정합니다.
			if(arr[i] < arr[i+1])
			{
				tmp = arr[i];
				arr[i]= arr[i + 1];
				arr[i + 1]= tmp;
				swapped = true;
			}
		}		
	}
}

int main()
{
	int values[5] = {3,2,5,4, 1};

	cout << "Before sorting" << endl;
	for(int i = 0; i < 5; i++)
	{
		cout << values[i];
		if(i < 4)
			cout << ", ";
		else 
			cout << endl;
	}

	// sort
	bubbleSort(values, 5);
	cout << "After sorting" << endl;
	for(int i = 0; i < 5; i++)
	{
		cout << values[i];
		if(i < 4)
			cout << ", ";
		else 
			cout << endl;
	}
}

< 결과 >

참고 : http://www.algolist.net/Algorithms/Sorting/Bubble_sort

주로 Swap을 하게되면 다음과 같은 방법으로 하게됩니다.

< 임시변수를 두고 교체하는 알고리즘 >

void swapB(int &x, int &y)
{	
	int temp = x;
	x = y;
	y = temp;
}

그러나 임시변수를 두지 않고, XOR(비트연산)을 이용하는 방법도 있습니다.

XOR 연산은 두 값의 각 자리수를 비교해, 값이 다르면 1로, 그렇지 않으면 0으로 계산합니다.

< 5와 3의 XOR 예 >

또한 XOR 연산은 다음과 같은 성질을 갖습니다. (출처 : 위키)

• L1. 교환법칙: 
• L2. 결합법칙: 
• L3. 항등원의 존재: 어떤 에 대하여서도, 가 되는 값 이 존재한다.
• L4. 각 원소에 대해 유일한 역원의 존재: 각 에 대하여, 가 되는 가 존재한다.
• L4a. 각 원소의 역원은 사실 자기 자신임: 

C++에서 XOR는 ^ 로 표현합니다.

< XOR을 이용한 교체 알고리즘 >

void swapA(int *x, int *y)
{
	if (x != y)
	{
		*x ^= *y;
		*y ^= *x;
		*x ^= *y;
	}
}

간단히 확인해 보기 위하여 1과 2 교체를 해보도록 하겠습니다.

< 전체 코드 >

#include 
using namespace std;

void swapA(int *x, int *y)
{
	if (x != y)
	{
		*x ^= *y;
		*y ^= *x;
		*x ^= *y;
	}
}

void swapB(int &x, int &y)
{	
	int temp = x;
	x = y;
	y = temp;
}

int main()
{
	int x = 1, y = 2;
	cout << "SwapA" << endl;
	cout << "Initial value : x = " << x << ", y = " << y << endl;
	swapA(&x, &y);
	cout << "swap value : x = " << x << ", y = " << y << endl << endl;
	cout << "SwapB" << endl;
	cout << "Initial value : x = " << x << ", y = " << y << endl;
	swapB(x, y);
	cout << "swap value : x = " << x << ", y = " << y << endl;
}

< 결과 >

실제 XOR을 이용한 방법은 요즘 프로세서에서 임시변수를 두고 사용하는게 더 빠르다고 합니다.(자세한건 위키로)

이런 방법도 있다는것만 알면 될듯 하네요. 

도움되셨길 바랍니다.

보글(Boggle) 게임은 NxM 크기의 알파벳 격자를 가지고 하는 게임인데,

목적은 상하좌우 / 대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것입니다.

(테스트를 위해 전체를 검색하여 존재하는지 여부 판단하도록 함)

// 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 문제.
/* 예를 들어
Y O S
H E K
Q Z W

인 경우 YES를 찾으면 {0, 0}, {1, 1}, {2, 0}을 순서대로 찾으면 된다.

예제의 경우 특정 위치에서 시작하지 않고, 해당 단어가 있는지 판단만 하도록한다.
*/

#include 
#include 
#include 
using namespace std;

class Boggle
{
public:
	// 게임판 정보
	vector board;

	Boggle()
	{
		// 게임판 세팅
		board.push_back("URLPM");
		board.push_back("XPRET");
		board.push_back("GIAET");
		board.push_back("XTNZY");
		board.push_back("HOQRS");
	}

	// 5x5 게임판에서 주어진 단어가 시작하는지 반환.
	bool hasWord(int x, int y, const string& word)
	{
		// 범위를 넘어가면 실패.
		if (x < 0 || y < 0 || x >= 5 || y >= 5) return false;
		// 단어의 첫번째가 안맞으면 실패;
		if (board[x][y] != word[0]) return false;
		// 단어의 첫번째가 맞았는데 길이가 1이면 성공.
		if (word.size() == 1) return true;
		// 현재 위치 중심으로 주변을 검색한다.
		for (int dx = -1;  dx <= 1; dx++)
		{
			for (int dy = -1; dy <= 1; dy++)
			{
				if (hasWord(x + dx, y + dy, word.substr(1)))
					return true;
			}
		}
		return false;
	}
};

int main()
{
	Boggle boggle;

	string target = "";
	cout << "찾을 문자열 입력" << endl;
	cin >> target;
	bool bFound = false;

	for (int x = 0; x < 5; x++)
	{
		for (int y = 0; y < 5; y++)
		{
			if (boggle.hasWord(x, y, target))
			{
				bFound = true;
				break;
			}
		}

		if (bFound)	break;
	}

	cout << "찾을 문자열 " << target << " 존재 : " << (bFound ? "YES" : "NO") << endl;

	system("pause");
}

< 결과 >

 알고리즘문제해결전략

n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘.

// n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘.

/*
예를 들어 N이 7이면 (0, 1,2, 3), (0, 1, 2, 4), (0,1, 2, 5), ....(3, 4, 5, 6).. 이다.

만약 m이 5개면? for문 5번해야함;; 뭔짓임.
*/

void UseFor(int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			for (int k = j + 1; k < n; k++)
			{
				for (int l = k + 1; l < n; l++)
				{
					cout << i << " " << j << " " << k << " " << l << endl;
				}
			}
		}
	}
}

/*
n: 전체 원소의 수
picked : 지금까지 고른 원소들의 번호
toPick : 더 고를 원소의 수
*/
void pick(int n, vector& picked, int toPick)
{
	if (toPick == 0)
	{
		for (int nIndex = 0; nIndex < picked.size(); ++nIndex)
		{
			cout << picked[nIndex] << " ";
		}

		cout << endl;
		return;
	}

	// 고를 수 있는 가장 작은 번호를 계산한다.
	int smallest = picked.empty() ? 0 : picked.back() + 1; 

	// 이 단계에서 원소 하나를 고른다.
	for (int next = smallest; next < n; ++next)
	{
		picked.push_back(next);
		pick(n, picked, toPick - 1);
		picked.pop_back();
	}
}

int main()
{
	int n = 10;

	//UseFor(n);

	vector v;
	pick(n, v, 8);

	getchar();

	return 0;
}

[ 결과 ]

1부터 N까지 합을 구하는 알고리즘.

ex> 1부터 1000까지 합을 구하라.

// 1부터 N까지 합을 계산하는 반복 함수와 재귀함수.

int MethodA(int n);
int MethodB(int n);

int main()
{
	int n = 1000;

	printf("분기문 : %d\n", MethodA(n));

	printf("재귀 : %d\n", MethodB(n));

	getchar();

	return 0;
}

// 일반적인 For문
int MethodA(int n)
{
	int ret = 0;
	for (int nIndex = 0; nIndex <= n; nIndex++)
	{
		ret += nIndex;
	}

	return ret;
}

// 재귀함수 ㅣ용
int MethodB(int n)
{
	if (n == 1) return n;
	else return n + MethodB(n - 1);
}

[ 결과 ]