Develop & Dream

Astar 알고리즘 그리드맵 툴

-그리드 맵 편집 기능

-현재 경로에 있는 맵파일 인식

-Astar 알고리즘을 재현

현재 경로에 있는 맵파일 인식

맵 파일 편집 및 저장

Astar 알고리즘 실행, 최단경로 찾기

경로 찾기 하는 부분에서 버그 발생

Priority Queue(우선 순위 큐)

• ADT(추상 자료형)
• 데이터 입력 순서에 상관 없이 우선 순위 순으로 처리된다.
• 배열 기반 Heap 을 통해 구현
• scheduler, 네트워크 트래픽 제어 등에 쓰임

※ADT(Abstract Data Type)

어떤 자료형이 가지는 기능과 속성만 명시하고 자료형의 구체적인 구현 방법은 명시하지 않은것

Heap(Max Heap, Min Heap)

• 최대값또는 최소값을 빠르게 찾기 위해 쓰인다
• Complete Binary Tree(완전 이진 트리) 이다
• 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있다.
• 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워야 한다.
• 배열로 구현한다
• Max Heap 은 항상 부모 노드의 값이 자식노드의 값보다 크다 그래서 root 노드의 값은 최대값이 온다. 최대 값을 빠르게 구할 수 있다.
• Min Heap 은 항상 부모 노드의 값이 자식노드의 값보다 작다, 최소값을 빠르게 구할 수 있다.
• 노드 개수를 알면, 트리구조는 무조건 확정할 수 있다.

Heapify algorithm

모든 노드의 위치가 heap 구조를 만족하도록, 위치를 조정하는 알고리즘

어떤 노드가 힙 구조(max-heap 이면 부모노드가 항상크다, min-heap 은 그 반대)를 위반하고 있을때, 그 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘, 위치를 바꾼 뒤에도 여전히 자식이 존재하는 경우, 또 자식 중에서 더 큰 자식과 자신의 위치를 바꾸어야 한다. 자식이 더 이상 존재하지 않을 때 까지 이과정은 계속 반복된다.(min-heap 은 반대로 부모 노드가 항상 자식들 보다 작게 위치를 조정한다)

시간 복잡도 :

한 번 자식 노드로 내려갈 때마다 노드의 갯수가 2배씩 증가한다 O(nlogn)

그러나 실제로는 n/2 개수 만큼만 연산을 해줘도 Heapify가 완료 된다 그래서

실제 시간 복잡도는 O(n) 이다

힙 트리 와 배열 인덱스 관계

위 트리 노드의 숫자는 곧 완전 이진트리의 삽입 순서이자, 배열로 힙트리를 표현할때 각각 노드의 인덱스와 동일하다

i번 노드의 부모는 heap[(i / 2)]

i번 노드의 왼쪽 자식은 heap[(2*i)]

i번 노드의 오른쪽 자식은 heap[(2*i) + 1]

Insert(삽입)

1.삽입할 데이터를 가장 마지막 자리에 놓기

2.삽입한 데이터의 값을 부모노드와 비교해서 크면 부모노드와 위치를 바꾼다

이것을 부모노드가 더 클때까지 반복한다(heapify algorithm)

version 1

void Insert(Max_Heap* _heap, int _iData)
{
	int* arr = _heap->iDataArr;
	int* iSize = &_heap->iSize;


	int currentIndex = ++(*iSize); //맨마지막 노드 인덱스 가져오기


	/*
	맨 마지막 노드에 데이터를 삽입, 해당 데이터가 부모 보다 크면 부모와 위치를 바꾸고 아니면 그대로 둠 
	*/
	while ((currentIndex != 1) && (_iData > arr[currentIndex / 2])) //root가 아니다 && 삽입 데이터가 현재노드의 부모보다 크다
	{
		arr[currentIndex] = arr[currentIndex / 2]; // 자식 노드자리에 부모 노드 값을 대입, 부모노드가 작으므로 밑으로 내림
		currentIndex /= 2; // 현재 인덱스에 부모 인덱스 대입
	}
	arr[currentIndex] = _iData; //최종 위치에 삽입
}

version 2

void Insert_2(int* arr2, int key, int input)
{
	arr2[key] = input; // 마지막 노드에 입력값 넣기

	while (key > 1)  //root에 도달할때까지 반복
	{
		if (arr2[key] > arr2[key / 2])  // 부모 노드보다 더 크다면
		{
			Swap_int(&arr2[key], &arr2[key / 2]); // 부모 노드와 자리를 바꿈
			key /= 2; // 부모노드 인덱스로 전환
		}
		else
		{
			break;
		}
	}
}

Pop(가장 첫번째 원소 삭제와 동시에 빼오기) 

Pop은 std::priority_queue 기준으로 삭제만 되게 되어있다. https://en.cppreference.com/w/cpp/container/priority_queue/pop

지금부터 구현하는 Pop함수는 약간 변형해서 반환까지 하게 한것이다.

힙트리 특성상 루트 노드의 값을 반환하게 되어있고, Max Heap 에서는 최대값, Min Heap 에서는 최소값을 꺼내게 되어있다.

1.루트 노드값(최대값, 최소값)을 꺼낸다

2.제일 마지막에 위치한 데이터를 루트로 옮긴다

3.자식 노드중에 가장 큰 값의 자리와 바꾼다

이것을 자식 노드보다 클때까지 반복한다(heapify algorithm)

version 1

int Pop(Max_Heap* _heap)
{
	if (_heap->iSize == 0)
	{
		return 0;
	}

	int ret = _heap->iDataArr[1]; // 꺼내올 데이터(root)
	_heap->iDataArr[1] = _heap->iDataArr[_heap->iSize--]; // root 자리에 맨마지막 위치 데이터 대입
	int parent = 1; //root 부터 시작
	int child = 0;
	
	while (1)
	{
		child = parent * 2; //왼쪽 자식, i번 노드의 왼쪽 자식 == heap[(2*i)]
		if (child + 1 <= _heap->iSize && _heap->iDataArr[child] <= _heap->iDataArr[child + 1]) // 오른쪽 자식 인덱스가 존재한다 && 오른쪽 자식이 왼쪽 자식보다 크거나 같다
		{
			child++; //오른쪽 자식으로 전환
		}

		if (child > _heap->iSize || _heap->iDataArr[child] < _heap->iDataArr[parent]) //자식인덱스가 힙 사이즈보다 크다(범위를 넘어버림) || 부모가 제일 큰 자식 보다 크다 
		{
			break; //중단
		}

		Swap_int(&_heap->iDataArr[parent], &_heap->iDataArr[child]); //부모와 제일 큰 자식 자리를 바꿈
		parent = child; // 자식의 자식들을 비교하기위해, 자식 노드를 부모 노드로 봄
	}
	return ret; // 꺼내올 데이터 리턴
}

version 2

int Pop_2(Max_Heap* _heap)
{
	int result = _heap->iDataArr[1]; //꺼내올 데이터
	
	int* arr = _heap->iDataArr; 
	int* iSize = &_heap->iSize;
	
	Swap_int(&arr[1], &arr[*iSize]); //마지막 노드 데이터와 루트 데이터를 바꿈
	(*iSize)--; //전체 노드 갯수 감소

	int parentIdx = 1; 
	int childIdx = parentIdx * 2;

	if (childIdx + 1 <= *iSize) //오른쪽 자식 노드 인덱스가 노드 전체 갯수를 넘지 않는다, 즉 오른쪽 자식이 존재한다
	{
		childIdx = (arr[childIdx] > arr[childIdx + 1]) ? childIdx : childIdx + 1; //왼쪽 자식, 오른쪽 자식, 둘 중에 큰 노드 선별
	}

	while (childIdx <= *iSize && arr[parentIdx] < arr[childIdx]) //자식 인덱스가 범위를 넘지 않는다 && 자식노드가 부모노드 보다 크다
	{
		Swap_int(&arr[parentIdx], &arr[childIdx]); // 자식 노드와 부모노드 위치 바꾸기

		parentIdx = childIdx; //자식 노드를 부모 노드로 봄
		childIdx *= 2; //왼쪽 자식 노드

		if (childIdx + 1 <= *iSize) //오른쪽 자식 노드 인덱스가 노드 전체 갯수를 넘지 않는다, 즉 오른쪽 자식이 존재한다
		{
			childIdx = (arr[childIdx] > arr[childIdx + 1]) ? childIdx : childIdx + 1; //왼쪽 자식, 오른쪽 자식, 둘 중에 큰 노드 선별
		}
	}
	return result;
}

전체 코드

#include <stdio.h>
#include <stdlib.h>

#define DEFAULT_HEAP_MAXSIZE 7

typedef struct _tagMaxHeap
{
	int* iDataArr;
	int iSize;
} Max_Heap;

void Swap_int(int* _a, int* _b);

void InitHeap(Max_Heap* _heap);
void Insert(Max_Heap* _heap, int _iData);
void Insert_2(int* arr2, int key, int input);
int Pop(Max_Heap* _heap);
int Pop_2(Max_Heap* _heap);

int main()
{
	Max_Heap heap;

	InitHeap(&heap);
	Insert(&heap, 8);
	Insert(&heap, 3);
	Insert(&heap, 15);
	Insert(&heap, 6);
	Insert(&heap, 10);
	Insert(&heap, 2);
	Insert(&heap, 18);
	
	/*	
	Insert_2(heap.iDataArr, ++heap.iSize, 8 );
	Insert_2(heap.iDataArr, ++heap.iSize, 3 );
	Insert_2(heap.iDataArr, ++heap.iSize, 15 );
	Insert_2(heap.iDataArr, ++heap.iSize, 6 );
	Insert_2(heap.iDataArr, ++heap.iSize, 18 );
	Insert_2(heap.iDataArr, ++heap.iSize, 2 );
	Insert_2(heap.iDataArr, ++heap.iSize, 10 );
	*/

	for (int i = 0; i < DEFAULT_HEAP_MAXSIZE; i++)
	{
		printf("%d ", Pop_2(&heap));
	}

	return 0;
}

void InitHeap(Max_Heap* _heap)
{
	_heap->iDataArr = (int*)calloc(DEFAULT_HEAP_MAXSIZE, sizeof(int));
	_heap->iSize = 0;
}


/*
i번 노드의 왼쪽 자식 == heap[(2*i)]
i번 노드의 오른쪽 자식 == heap[(2*i) + 1]
i번 노드의 부모 == heap[(i / 2)]
*/
void Insert(Max_Heap* _heap, int _iData)
{
	int* arr = _heap->iDataArr;
	int* iSize = &_heap->iSize;


	int currentIndex = ++(*iSize); //맨마지막 노드 인덱스 가져오기


	/*
	맨 마지막 노드에 데이터를 삽입, 해당 데이터가 부모 보다 크면 부모와 위치를 바꾸고 아니면 그대로 둠 
	*/
	while ((currentIndex != 1) && (_iData > arr[currentIndex / 2])) //root가 아니다 && 삽입 데이터가 현재노드의 부모보다 크다
	{
		arr[currentIndex] = arr[currentIndex / 2]; // 자식 노드자리에 부모 노드 값을 대입, 부모노드가 작으므로 밑으로 내림
		currentIndex /= 2; // 현재 인덱스에 부모 인덱스 대입
	}
	arr[currentIndex] = _iData; //최종 위치에 삽입
}

void Insert_2(int* arr2, int key, int input)
{
	arr2[key] = input; // 마지막 노드에 입력값 넣기

	while (key > 1)  //root에 도달할때까지 반복
	{
		if (arr2[key] > arr2[key / 2])  // 부모 노드보다 더 크다면
		{
			Swap_int(&arr2[key], &arr2[key / 2]); // 부모 노드와 자리를 바꿈
			key /= 2; // 부모노드 인덱스로 전환
		}
		else
		{
			break;
		}
	}
}



int Pop(Max_Heap* _heap)
{
	if (_heap->iSize == 0)
	{
		return 0;
	}

	int ret = _heap->iDataArr[1]; // 꺼내올 데이터(root)
	_heap->iDataArr[1] = _heap->iDataArr[_heap->iSize--]; // root 자리에 맨마지막 위치 데이터 대입
	int parent = 1; //root 부터 시작
	int child = 0;
	
	while (1)
	{
		child = parent * 2; //왼쪽 자식, i번 노드의 왼쪽 자식 == heap[(2*i)]
		if (child + 1 <= _heap->iSize && _heap->iDataArr[child] <= _heap->iDataArr[child + 1]) // 오른쪽 자식 인덱스가 존재한다 && 오른쪽 자식이 왼쪽 자식보다 크거나 같다
		{
			child++; //오른쪽 자식으로 전환
		}

		if (child > _heap->iSize || _heap->iDataArr[child] < _heap->iDataArr[parent]) //자식인덱스가 힙 사이즈보다 크다(범위를 넘어버림) || 부모가 제일 큰 자식 보다 크다 
		{
			break; //중단
		}

		Swap_int(&_heap->iDataArr[parent], &_heap->iDataArr[child]); //부모와 제일 큰 자식 자리를 바꿈
		parent = child; // 자식의 자식들을 비교하기위해, 자식 노드를 부모 노드로 봄
	}
	return ret; // 꺼내올 데이터 리턴
}

int Pop_2(Max_Heap* _heap)
{
	int result = _heap->iDataArr[1]; //꺼내올 데이터
	
	int* arr = _heap->iDataArr; 
	int* iSize = &_heap->iSize;
	
	Swap_int(&arr[1], &arr[*iSize]); //마지막 노드 데이터와 루트 데이터를 바꿈
	(*iSize)--; //전체 노드 갯수 감소

	int parentIdx = 1; 
	int childIdx = parentIdx * 2;

	if (childIdx + 1 <= *iSize) //오른쪽 자식 노드 인덱스가 노드 전체 갯수를 넘지 않는다, 즉 오른쪽 자식이 존재한다
	{
		childIdx = (arr[childIdx] > arr[childIdx + 1]) ? childIdx : childIdx + 1; //왼쪽 자식, 오른쪽 자식, 둘 중에 큰 노드 선별
	}

	while (childIdx <= *iSize && arr[parentIdx] < arr[childIdx]) //자식 인덱스가 범위를 넘지 않는다 && 자식노드가 부모노드 보다 크다
	{
		Swap_int(&arr[parentIdx], &arr[childIdx]); // 자식 노드와 부모노드 위치 바꾸기

		parentIdx = childIdx; //자식 노드를 부모 노드로 봄
		childIdx *= 2; //왼쪽 자식 노드

		if (childIdx + 1 <= *iSize) //오른쪽 자식 노드 인덱스가 노드 전체 갯수를 넘지 않는다, 즉 오른쪽 자식이 존재한다
		{
			childIdx = (arr[childIdx] > arr[childIdx + 1]) ? childIdx : childIdx + 1; //왼쪽 자식, 오른쪽 자식, 둘 중에 큰 노드 선별
		}
	}
	return result;
}


void Swap_int(int* _a, int* _b)
{
	*_a ^= *_b ^= *_a ^= *_b;
}

실행결과

삽입한 순서에 상관없이 우선 순위(노드 값이 높을 수록 우선순위가 높다고 할때) 순으로 

데이터를 꺼내오고 있다.

Tree

• 계층적 구조를 나타내는 자료구조

• 부모-자식 관계의 노드들로 구성, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태

• 자식 -> 부모, 등으로 순환 할 수 없음, 무조건 부모 -> 자식 방향으로만 뻗어나감

• Linked List의 장점 을 가지고 있음( 데이터 삽입, 삭제시 데이터들을 이동하지 않아도 되는것)

• Linked List의 단점을 보완함(검색시 노드의 처음부터 찾아가야 하는 것, 이진 탐색)

• 노드가 3개 붙으면 ternary tree, 2개 붙으면 binary tree 라고 함, 주로 binary tree를 가장 많이 씀

Tree 용어 정리

• 부모(parent) 노드 : 어떤 노드 바로 위에 연결되어있는 노드

• 자식(child) 노드 : 어떤 노드 바로 아래에 연결되어 있는 노드

• 형제(sibling) 노드 : 같은 부모를 가지는 노드

• 조상(ancestor) : 어떤 노드에서 root 노드에 이르는 경로상에 있는 노드들

• 자손(descendent) : 어떤 노드의 자식 노드를 포함하여, 아래쪽에 있는 노드들

• 루트(root) : 부모가 없는 노드

• 서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리

• 잎(leaf) 노드 : 자식 노드가 하나도 없는 노드, 외부(external) 노드라고도 불림

• 내부(internal) 노드 : 잎노드가 아닌 노드, 자식 노드를 하나라도 가지고 있는 노드

• 수준(level) : 트리의 각 계층에 매겨지는 번호, root 노드의 level 은 1, 한층씩 내려갈 수록 1씩 증가

• 높이(height) : 트리에 속한 노드의 최대 수준, 위 트리의 높이는 4