함수
재귀함수 Recursive Function
#include <iostream>
void Test(int& _Data)
{
// 종료되는 시점을 꼭 정하고 return시켜야 한다
if (_Data >= 100)
{
return;
}
// 함수의 실행메모리 크기는 변수의 크기에 영향을 받는다
// 따라서, 같은 크기의 스택 메모리라고 가정했을 때,
// Arr가 없는 경우보다 Arr가 있을 때 Stack Overflow가 발생할 때까지의
// Test 실행 횟수가 적다
int Arr[100];
Arr[0] = _Data;
std::cout << _Data << std::endl;
++_Data;
Test(_Data); // 재귀함수
}
int main()
{
int Value = 0;
Test(Value);
}자료구조
💡 자료구조의 분류
기준 | 컨테이너 | 메모리형태(참고) ----- | ----- | ----- vector | 시퀀스 | 배열 list | 시퀀스 | 노드 map | 연관 | 노드(트리) string | 어댑터 | stack | 어댑터 | queue | 어댑터 |
map
/*
[Map]
노드(트리)를 사용하는 연관 컨테이너
- std::map은 레드블랙 바이너리 서치 트리이다.
- root로부터 나무모양처럼 뻗어나간다고 해서 노드 형식 중 트리 구조이다.
Node > Tree > (이진, 삼진, ...) + (서치, ...)
- 트리 구조 중, 자식의 갯수가 2개일 경우 이진 트리 구조이다. => binary tree
- 트리 구조 중, 자식 끼리 크기비교를 하게 되면 서치 트리 구조이다. => search tree
(+)
탐색과 정렬에 특화되어 있는 자료구조이다.
- 탐색 시, 최대 트리의 depth만큼의 연산만 필요하다.
- 데이터를 추가할 시, 자동으로 정렬된다.
(-)
탐색과 정렬에 특화되어 있다곤 하지만...
- 웬만큼 규모가 크지 않은 경우엔 속도에 특화되어 있는 벡터에게 탐색을 시키면
좀 더 빠르긴 하다(...)
- 그런데 심지어 배열보다 용량도 몇배다 크다.
- 특히 언리얼은 배열형 자료구조를 선호하는 편이다.
한쪽에만 치우쳐 있는 편향트리가 생길 수 있다.
- 레드블랙 알고리즘은 스핀이라는 알고리즘을 통해 적절한 노드에게 루트를 배정하여
트리의 균형을 잡아준다.
*/
#include <iostream>
#include <Windows.h>
#include <assert.h>
#include <map>
typedef int KeyType;
typedef int DataType;
class MyPair
{
public:
MyPair()
{
}
MyPair(KeyType _first, DataType _second)
: Key(_first), Value(_second)
{
}
KeyType Key = KeyType();
DataType Value = DataType();
};
// template<typename KeyType, typename ValueType>
class MyMap
{
private:
class MapNode
{
public:
MyPair Pair;
MapNode* Parent = nullptr;
MapNode* LeftChild = nullptr;
MapNode* RightChild = nullptr;
void insertNode(MapNode* _Node)
{
if ( _Node->Pair.Key < this->Pair.Key)
{
if (this->LeftChild == nullptr)
{
this->LeftChild = _Node;
return;
}
this->LeftChild->insertNode(_Node);
}
if (_Node->Pair.Key > this->Pair.Key)
{
if (this->RightChild == nullptr)
{
this->RightChild = _Node;
return;
}
this->RightChild->insertNode(_Node);
}
return;
}
bool containsNode(const KeyType& _Key)
{
if (_Key == this->Pair.Key)
{
return true;
}
if (_Key < this->Pair.Key)
{
if (this->LeftChild != nullptr)
{
/*
[꼬리 재귀]
리턴과 동시에 재귀함수를 호출하는 것
- 컴파일러가 (가능하다면) while문 형식으로 바꿔준다.
- inline함수와 비슷한 경우로, 최적화에 도움이 된다.
*/
return this->LeftChild->containsNode(_Key);
}
}
if (_Key > this->Pair.Key)
{
if (this->RightChild != nullptr)
{
return this->RightChild->containsNode(_Key);
}
}
return false;
}
MapNode* findNode(const KeyType& _Key)
{
if (_Key == this->Pair.Key)
{
return this;
}
if (_Key < this->Pair.Key)
{
if (this->LeftChild != nullptr)
{
return this->LeftChild->findNode(_Key);
}
}
if (_Key > this->Pair.Key)
{
if (this->RightChild != nullptr)
{
return this->RightChild->findNode(_Key);
}
}
return nullptr;
}
// Parent 쪽에서 나와의 연결 해제
void Release()
{
if (Parent != nullptr)
{
// 내가 LeftChild일 경우
if (this == Parent->LeftChild)
{
Parent->LeftChild = nullptr;
}
// 내가 RightChild일 경우
if (this == Parent->RightChild)
{
Parent->RightChild = nullptr;
}
}
}
// 전위 순회
void firstOrderPrint()
{
std::cout << Pair.Key << std::endl; // 할일
if (LeftChild != nullptr)
{
LeftChild->firstOrderPrint();
}
if (RightChild != nullptr)
{
RightChild->firstOrderPrint();
}
return;
}
// 중위 순회
void midOrderPrint()
{
if (LeftChild != nullptr)
{
LeftChild->midOrderPrint();
}
std::cout << Pair.Key << std::endl; // 할일
if (RightChild != nullptr)
{
RightChild->midOrderPrint();
}
return;
}
// 후위 순회
void lastOrderPrint()
{
if (LeftChild != nullptr)
{
LeftChild->lastOrderPrint();
}
if (RightChild != nullptr)
{
RightChild->lastOrderPrint();
}
std::cout << Pair.Key << std::endl; // 할일
return;
}
// 후위 순회와 유사한 구조이다
// this를 delete하기 전에 필요한 일을 모두 마쳐야하기 때문
void clearNode()
{
if (this->LeftChild != nullptr)
{
LeftChild->clearNode();
}
if (this->RightChild != nullptr)
{
RightChild->clearNode();
}
delete this;
return;
}
MapNode* minnode()
{
if (this->LeftChild == nullptr)
{
return this;
}
return LeftChild->minnode();
}
MapNode* maxnode()
{
if (this->RightChild == nullptr)
{
return this;
}
return RightChild->maxnode();
}
// 재귀함수로도 가능
MapNode* SmallParent()
{
MapNode* PNode = Parent;
while (PNode)
{
// 나의 Parent의 Key값이 나의 Key값보다 작다면,
if (Pair.Key > PNode->Pair.Key)
{
// Parent가 반환되어 PrevNode가 된다
return PNode;
}
// 그렇지 않다면, Parent의 Parent를 탐색
PNode = PNode->Parent;
}
return nullptr;
}
// 재귀함수로도 가능
MapNode* OverParent()
{
MapNode* PNode = Parent;
while (PNode)
{
// 나의 Parent의 Key값이 나의 Key값보다 크다면,
if (Pair.Key < PNode->Pair.Key)
{
// Parent가 반환되어 NextNode가 된다
return PNode;
}
// 그렇지 않다면, Parent의 Parent를 탐색
PNode = PNode->Parent;
}
return nullptr;
}
MapNode* PrevNode()
{
// LeftChild가 존재할 경우
if (this->LeftChild != nullptr)
{
return this->LeftChild->maxnode();
}
// LeftChild가 존재하지 않을 경우, 부모를 탐색
return SmallParent();
}
MapNode* NextNode()
{
// RightChild가 존재할 경우
if (this->RightChild != nullptr)
{
return this->RightChild->minnode();
}
// RightChild가 존재하지 않을 경우, 부모를 탐색
return OverParent();
}
bool IsLeaf()
{
return nullptr == LeftChild && nullptr == RightChild;
}
};
public:
class iterator
{
friend MyMap;
public:
iterator()
{
}
iterator(MapNode* _CurNode)
: CurNode(_CurNode)
{
}
MyPair* operator->()
{
MyPair& MapPair = CurNode->Pair;
return &MapPair; // -> 연산자는 주소값을 반환한다
}
bool operator!=(const iterator& _Other)
{
return CurNode != _Other.CurNode;
}
void operator++()
{
CurNode = CurNode->NextNode();
return;
}
private:
MapNode* CurNode = nullptr;
};
~MyMap()
{
clear();
}
/*
Tip
인자는 레퍼런스로 받는게 이득이다.
어짜피 인자는 8byte씩 할당되기 때문에 bool이라도 레퍼런스가 이득이다.
*/
/*
map은 자료가 무작위일때, 다른 자료구조에 비해 높은 효율을 자랑한다.
자료가 이미 특정 기준 하에 정렬된 상태로 들어간다면 대부분의 경우,
다른 자료구조들이 map보다 빠르다.
*/
void insert(const MyPair& _Value)
{
MapNode* NewNode = new MapNode();
NewNode->Pair = _Value;
// 트리에서 최초 노드는 무조건 뿌리 노드가 된다
if (Root == nullptr)
{
Root = NewNode;
return;
}
Root->insertNode(/*Root, */NewNode);
}
bool contains(const KeyType& _Key)
{
if (Root == nullptr)
{
return false;
}
return Root->containsNode(_Key);
}
iterator find(const KeyType& _Key)
{
if (Root == nullptr)
{
return end();
}
return iterator(Root->findNode(_Key));
}
iterator erase(iterator& _Iter)
{
iterator Return;
if (_Iter.CurNode == nullptr)
{
MessageBoxA(nullptr, "유효하지 않은 원소를 삭제하려고 했습니다.", "치명적 에러", MB_OK);
assert(false);
return Return;
}
// erase()하는 노드의 NextNode를 반환
Return.CurNode = _Iter.CurNode->NextNode();
/*
상황 1. 자식이 없는 리프노드일 경우
- 대체할 노드가 필요하지 않다
- Parent 노드에게 알려야 한다
*/
if (_Iter.CurNode->IsLeaf() == true)
{
// 삭제할 노드의 부모와 연결 끊기
_Iter.CurNode->Release();
delete _Iter.CurNode;
return Return;
}
/*
상황 2. 자식이 있는 노드일 경우
- LeftChild의 maxnode 또는 RightChild의 minnode가 대체한다
- 둘 중 어느것이든 괜찮기 때문에 코드 짜는 사람이 선택 가능하다
*/
MapNode* ChangeNode = nullptr; // 대체할 노드
MapNode* CurNode = _Iter.CurNode; // 삭제할 노드
// RightChild의 minnode를 대체할 노드로 지정
ChangeNode = CurNode->RightChild->minnode();
if (ChangeNode == nullptr)
{
// 안될 경우, LeftChild의 maxnode를 대체할 노드로 지정
ChangeNode = CurNode->LeftChild->maxnode();
if (ChangeNode == nullptr)
{
MessageBoxA(nullptr, "체인지 노드 에러.", "치명적 에러", MB_OK);
assert(false);
return Return;
}
}
// 대체할 노드의 부모와 연결 끊기
ChangeNode->Release();
// 삭제할 노드의 자식과 연결 끊기, 대체할 노드를 새로운 자식과 연결
MapNode* LeftChild = CurNode->LeftChild;
MapNode* RightChild = CurNode->RightChild;
/*
if (LeftChild != nullptr)
{
LeftChild->Parent = nullptr;
}
if (RightChild != nullptr)
{
RightChild->Parent = nullptr;
}
*/
if (LeftChild != nullptr)
{
LeftChild->Parent = ChangeNode;
if (LeftChild != ChangeNode)
{
ChangeNode->LeftChild = LeftChild;
}
}
if (RightChild != nullptr)
{
RightChild->Parent = ChangeNode;
if (RightChild != ChangeNode)
{
ChangeNode->RightChild = RightChild;
}
}
// 삭제할 노드의 부모와 연결 끊기, 대체할 노드를 새로운 부모와 연결
ChangeNode->Parent = CurNode->Parent;
MapNode* Parent = ChangeNode->Parent;
if (Parent != nullptr && Parent->LeftChild == CurNode)
{
Parent->LeftChild = ChangeNode;
}
if (Parent != nullptr && Parent->RightChild == CurNode)
{
Parent->RightChild = ChangeNode;
}
// 삭제할 노드가 root였을 경우
if (Root == CurNode)
{
Root = ChangeNode;
}
delete CurNode;
return Return;
}
iterator begin()
{
if (Root == nullptr)
{
return end();
}
return iterator(Root->minnode());
}
iterator end()
{
return iterator(nullptr);
}
void firstOrderPrint()
{
Root->firstOrderPrint();
return;
}
void midOrderPrint()
{
Root->midOrderPrint();
return;
}
void lastOrderPrint()
{
Root->lastOrderPrint();
return;
}
void clear()
{
Root->clearNode();
Root = nullptr;
return;
}
private:
MapNode* Root = nullptr;
};
int main()
{
_CrtSetDbgFlag(_CRTDBG_LEAK_CHECK_DF | _CRTDBG_ALLOC_MEM_DF);
{
std::cout << "std::map" << std::endl;
// [선언] key, value
std::map<int, int> NewMap = std::map<int, int>();
/*
[자료 추가] 방법이 네가지나 있다
1. pair
NewMap.insert(std::pair<int, int>(1, 123456789));
2. make_pair
NewMap.insert(std::make_pair(1, 123456789));
3. 배열 연산자
NewMap[3] = 1;
4. value_type
NewMap.insert(std::map<int, int>::value_type(7, 10));
// std::map<int, int>::value_type == std::pair<int, int>
*/
NewMap.insert(std::pair<int, int>(10, 0));
NewMap.insert(std::pair<int, int>(5, 0));
NewMap.insert(std::pair<int, int>(15, 0));
NewMap.insert(std::pair<int, int>(12, 0));
NewMap.insert(std::pair<int, int>(3, 0));
NewMap.insert(std::pair<int, int>(7, 0));
// 자동으로 오름차순 정렬이 된다
// 3, 5, 7, 10, 12, 15
/*
[탐색]
1. contains() (C++20 에서만 사용 가능)
존재하는지 여부를 bool로 반환
NewMap.contains(15);
if (NewMap.contains(15) == true)
{
// 존재한다
}
2. find()
탐색한 결과를 iterator로 반환
*/
std::map<int, int>::iterator FindIter = NewMap.find(15);
if (FindIter != NewMap.end())
{
// 존재한다
}
// [자료 삭제]
NewMap.erase(FindIter);
// [순회]
// map은 노드의 갯수가 많아질수록 순회를 돌리는 과정이 효율적이지 못하다
// 무수한 반복문 또는 재귀함수를 호출해야 하기 때문
std::map<int, int>::iterator StartIter = NewMap.begin();
std::map<int, int>::iterator EndIter = NewMap.end();
for (; StartIter != EndIter; ++StartIter)
{
std::cout << "Key : " << StartIter->first << std::endl;
// std::cout << "Value : " << StartIter->second << std::endl;
}
}
{
std::cout << "MyMap" << std::endl;
// 선언
MyMap NewMap = MyMap();
// 자료 추가
NewMap.insert(MyPair(10, 0));
NewMap.insert(MyPair(5, 0));
NewMap.insert(MyPair(15, 0));
NewMap.insert(MyPair(12, 0));
NewMap.insert(MyPair(3, 0));
NewMap.insert(MyPair(7, 0));
// 탐색
NewMap.contains(12);
MyMap::iterator FindIter = NewMap.find(12);
// 삭제
// NewMap.erase(FindIter);
// 순회
MyMap::iterator StartIter = NewMap.begin();
MyMap::iterator EndIter = NewMap.end();
for (; StartIter != EndIter; ++StartIter)
{
std::cout << StartIter->Key << std::endl;
//std::cout << StartIter->second << std::endl;
}
std::cout << "first" << std::endl;
NewMap.firstOrderPrint(); // 10 5 3 7 15 12
std::cout << "mid" << std::endl;
NewMap.midOrderPrint(); // 3 5 7 10 12 15
std::cout << "last" << std::endl;
NewMap.lastOrderPrint(); // 3 7 5 12 15 10
}
}
⋆꙳⊹⋰ 𓇼⋆ 𝑻𝑰𝑳 𝑨𝑹𝑪𝑯𝑰𝑽𝑬 ⸝·⸝⋆꙳⊹⋰