Winwoo's Story

1. sin, cos, tan는 직각삼각형에서만 해당된다.

2. 삼각형에서 제일 큰 변은 제일 큰 각과 마주보고 있는 변이다.
(그래서 직각삼각형에선 제일 큰 각은 90도이며 90도와 마주보고있는 빗변이 제일 길다.)

3. arcsin, arccos, arctan를 사용하면 값으로 부터 대응하는 각도(θ)를 구할 수 있다.
 ex) θ = arcsin(sinθ)
      θ = arccos(cosθ)
      θ = arctan(tanθ)

4. 단위원

5. 단위원 풀이
단위원의 반지름이 r일경우
sinθ = b/r -> r·sinθ = b
cosθ = a/r -> r·cosθ = a
점(a,b) = (r·cosθ, r·sinθ)

피타고라스의 정리를 사용하면,
r² = a² + b²
r² = (r·cosθ)² + (r·sinθ)²
r² = r²·cos²θ + r²·sin²θ
1 = cosθ + sinθ

6. 삼각함수 사이의 관계
tanθ = sinθ / cosθ
sin²θ + cos²θ = 1

7. 삼각함수의 값의 부호

6.삼각함수의 특수각

// ABCharacter.h
UCLASS()
class ARENABATTLE_API AABCharacter : public ACharacter
{
	GENERATED_BODY()

public:
	// Sets default values for this character's properties
	AABCharacter();

protected:
	...

	float ArmLengthTo;
	FRotator ArmRotationTo;
	float ArmLengthSpeed;
	float ArmRotationSpeed;
public:	
	...

	UPROPERTY(VisibleAnywhere, Category = Camera)
	USpringArmComponent* SpringArm;

	UPROPERTY(VisibleAnywhere, Category = Movement)
	UCameraComponent* Camera;
    
    ...

private:
	virtual void Jump() override;
	void UpDown(float NewAxisValue);
	void LeftRight(float NewAxisValue);
	void LookUp(float NewAxisValue);
	void Turn(float NewAxisValue);
    
	...

};

// ABCharacter.cpp

// 생성자
AABCharacter::AABCharacter()
	: ArmLengthTo(0.0f)
	, ArmRotationTo(FRotator::ZeroRotator)
	, ArmLengthSpeed(0.0f)
	, ArmRotationSpeed(0.0f)
{
    // Set this character to call Tick() every frame.  You can turn this off to improve performance if you don't need it.
    PrimaryActorTick.bCanEverTick = true;

    //카메라 관련 컴포넌트 가져오기
    SpringArm = CreateDefaultSubobject<USpringArmComponent>(TEXT("SPRINGARM"));
    Camera = CreateDefaultSubobject<UCameraComponent>(TEXT("CAMERA"));

    ...

    //SpringArm은 캐릭터에 붙이고, 카메라는 SpringArm에 붙착 돼서 SpringArm의 움직임을 기준으로 카메라가 비추게 된다.
    SpringArm->SetupAttachment(GetCapsuleComponent());
    Camera->SetupAttachment(SpringArm);

    ...

    //SpringArm 길이, 위치 설정
    SpringArm->TargetArmLength = 400.0f;
    SpringArm->SetRelativeRotation(FRotator(-15.0f, 0.0f, 0.0f));

    ...
    //3인칭 카메라 모드 설정(GTA 카메라 시점)
    SetControlMode(EControlMode::GTA);
    //SpringArm 속도 설정
    ArmLengthSpeed = 3.0f;
    ArmRotationSpeed = 10.0f;

    //캐릭터 점프력 설정
    GetCharacterMovement()->JumpZVelocity = 400.0f;

    ...
}

// Called to bind functionality to input
void AABCharacter::SetupPlayerInputComponent(UInputComponent* PlayerInputComponent)
{
    Super::SetupPlayerInputComponent(PlayerInputComponent);

    PlayerInputComponent->BindAction(TEXT("Jump"), EInputEvent::IE_Pressed, this, &AABCharacter::Jump);
    PlayerInputComponent->BindAxis(TEXT("UpDown"), this, &AABCharacter::UpDown);
    PlayerInputComponent->BindAxis(TEXT("LeftRight"), this, &AABCharacter::LeftRight);
    PlayerInputComponent->BindAxis(TEXT("LookUp"), this, &AABCharacter::LookUp);
    PlayerInputComponent->BindAxis(TEXT("Turn"), this, &AABCharacter::Turn);
}


void AABCharacter::SetControlMode(EControlMode ControlMode)
{
    UCharacterMovementComponent& CharacterMovement = *GetCharacterMovement();

    ArmLengthTo = 450.0f;
    SpringArm->bUsePawnControlRotation = true;
    SpringArm->bInheritPitch = true;
    SpringArm->bInheritRoll = true;
    SpringArm->bInheritYaw = true;
    SpringArm->bDoCollisionTest = true;
    bUseControllerRotationYaw = false;
    CharacterMovement.bOrientRotationToMovement = true;
    CharacterMovement.bUseControllerDesiredRotation = false;
    CharacterMovement.RotationRate = FRotator(0.0f, 720.0f, 0.0f);
}

void AABCharacter::Jump()
{
    // 공격 모션중엔 점프를 못한다.
    if (IsAttacking == true)
   	 return;

    Super::Jump();
}

// SpringArm의 Rotation 값은 옵션에 의해 ControlRotation값과 동일하므로 ControlRoation 값이 곧 카메라가 바라보는 방향이다.
// ControlRotation의 값으로부터 회전 행렬을 생성 한 후, 원하는 방향 축을 대입해 캐릭터가 움직일 방향 값을 가져올 수 있다.
// 시선 방향 X축, 우측 방향 Y축
void AABCharacter::UpDown(float NewAsixValue)
{
    // 공격 모션중엔 움직이지 못한다.
    if (IsAttacking == true)
    	return;

    switch (CurrentControlMode)
    {
      case EControlMode::GTA:
      	AddMovementInput(FRotationMatrix(GetControlRotation()).GetUnitAxis(EAxis::X), NewAsixValue);
      	break;
    }
}

void AABCharacter::LeftRight(float NewAsixValue)
{
	// 공격 모션중엔 움직이지 못한다.
    if (IsAttacking == true)
    return;

    switch (CurrentControlMode)
    {
      case EControlMode::GTA:
      	AddMovementInput(FRotationMatrix(GetControlRotation()).GetUnitAxis(EAxis::Y), NewAsixValue);
      	break;
    }
}

void AABCharacter::LookUp(float NewAsixValue)
{
    switch (CurrentControlMode)
    {
      case EControlMode::GTA:
      	AddControllerPitchInput(NewAsixValue);
      	break;
    }
}

void AABCharacter::Turn(float NewAsixValue)
{
    switch (CurrentControlMode)
    {
    case EControlMode::GTA:
      AddControllerYawInput(NewAsixValue);
      break;
    }
}

프로젝트에 대한 코드는 [UE4 카테고리]에 올라갑니다.

※본 프로젝트는 [이득우의 언리얼 c++ 게임 개발 정석] 서적을 참고하여 개발중입니다.

크기의 제한이 있는 Vector를 만들었다.

FixedBoolVector는 메모리를 효율적으로 사용하기 위해 uint32 배열 한칸 당 bool값 32개를 넣을 수 있도록 했다.

(bool은 1bit만으로도 표현이 가능하기 때문에 uint32 한개당 32개의 bool을 담을 수 있다.)

#pragma once

namespace lab8
{
	template <typename T, size_t N>
	class FixedVector
	{
	public:
		FixedVector();
		FixedVector(const FixedVector<T, N>& other);
		~FixedVector();
		FixedVector<T, N>& operator=(const FixedVector<T, N>& other);

		bool Add(const T& t);
		bool Remove(const T& t);
		const T& Get(unsigned int index) const;
		T& operator[](unsigned int index);
		int GetIndex(const T t) const;
		size_t GetSize() const;
		size_t GetCapacity() const;

	private:
		size_t mSize;
		T mArray[N];
	};

	template<typename T, size_t N>FixedVector<T, N>::FixedVector()
		: mSize(0)
	{
		memset(mArray, 0, sizeof(T) * N);
	}

	template<typename T, size_t N>FixedVector<T, N>::FixedVector(const FixedVector<T, N>& other)
		: mSize(other.mSize)
		, mArray(other.mArray)
	{
		memset(mArray, 0, sizeof(T) * N);
	}

	template<typename T, size_t N>FixedVector<T, N>::~FixedVector()
	{
	}

	template<typename T, size_t N>
	FixedVector<T, N>& FixedVector<T, N>::operator=(const FixedVector<T, N>& other)
	{
		mSize = other.mSize;
		mArray = other.mArray;
	}

	template<typename T, size_t N>
	bool FixedVector<T, N>::Add(const T& t)
	{
		if (mSize >= N)
			return false;

		mArray[mSize] = t;
		mSize++;

		return true;
	}

	template<typename T, size_t N>
	bool FixedVector<T, N>::Remove(const T& t)
	{
		bool bRemove = false;
		for (size_t i = 0; i < mSize; i++)
		{
			if (bRemove == true)
			{
				mArray[i - 1] = mArray[i];
				continue;
			}

			if (bRemove == false && mArray[i] == t)
			{
				bRemove = true;
			}
		}

		if (bRemove == true)
		{
			mSize--;
			mArray[mSize] = NULL;
		}

		return bRemove;
	}

	template<typename T, size_t N>
	const T& FixedVector<T, N>::Get(unsigned int index) const
	{
		return mArray[index];
	}

	template<typename T, size_t N>
	T& FixedVector<T, N>::operator[](unsigned int index)
	{
		return mArray[index];
	}

	template<typename T, size_t N>
	int FixedVector<T, N>::GetIndex(T t) const
	{
		for (size_t i = 0; i < mSize; i++)
		{
			if (mArray[i] == t)
			{
				return static_cast<int>(i);
			}
		}
		return -1;
	}

	template<typename T, size_t N>
	size_t FixedVector<T, N>::GetSize() const
	{
		return mSize;
	}

	template<typename T, size_t N>
	size_t FixedVector<T, N>::GetCapacity() const
	{
		return N;
	}
}

#pragma once
#include <cstdint>
using namespace std;
namespace lab8
{
	template <size_t N>
	class FixedVector<bool, N>
	{
	public:
		FixedVector();
		FixedVector(const FixedVector<bool, N>& other);
		~FixedVector();
		FixedVector<bool, N>& operator=(const FixedVector<bool, N>& other);

		bool Add(const bool& b);
		bool Remove(const bool& b);
		bool Get(unsigned int index);
		bool operator[](unsigned int index);
		int GetIndex(const bool b) const;
		size_t GetSize() const;
		size_t GetCapacity() const;

		void Print() const;

	private:
		enum
		{
			MAX_BIT = 32
		};
		size_t mSize;
		uint32_t mArray[((N - 1) / MAX_BIT) + 1];
	};

	template<size_t N>FixedVector<bool, N>::FixedVector()
		: mSize(0)
	{
		memset(mArray, 0, sizeof(mArray));
	}

	template<size_t N>FixedVector<bool, N>::FixedVector(const FixedVector<bool, N>& bOther)
		: mSize(bOther.mSize)
		, mArray(bOther.mArray)
	{
		memset(mArray, 0, sizeof(mArray));
	}

	template<size_t N>FixedVector<bool, N>::~FixedVector()
	{
	}

	template<size_t N>FixedVector<bool, N>& FixedVector<bool, N>::operator=(const FixedVector<bool, N>& bOther)
	{
		mSize = bOther.mSize;
		mArray = bOther.mArray;
	}

	template<size_t N>
	bool FixedVector<bool, N>::Add(const bool& b)
	{
		if (mSize >= N)
			return false;

		const unsigned int index = mSize / MAX_BIT;
		unsigned int size = mSize % MAX_BIT;

		if (b == true)
		{
			mArray[index] |= (1 << size);
		}
		else
		{
			mArray[index] &= ~(1 << size);
		}
		mSize++;
		return true;
	}

	template<size_t N>
	bool FixedVector<bool, N>::Remove(const bool& b)
	{
		bool bRemove = false;
		const unsigned int maxIndex = ((mSize - 1) / MAX_BIT) + 1;

		for (size_t i = 0; i < maxIndex; i++)
		{
			if (bRemove == true)
			{
				uint32_t n = (mArray[i] & 1); // 이전으로 보낼 첫 비트
				uint32_t n2 = (n << (MAX_BIT - 1)); // 이전으로 보내기 위해 맨뒤로 민다.

				mArray[i - 1] |= n2; // 이전의 맨뒤로 합친다.
				mArray[i] >>= 1; // 한개 빠지만큼 앞으로 민다.
				continue;
			}

			uint32_t frontBit = 0;
			for (size_t j = 0; j < mSize && j < MAX_BIT; j++)
			{
				if ((mArray[i] & (1 << j)) > 0) // 1
				{
					if (b == true)
					{
						uint32_t n = mArray[i] >> (j + 1); // 지워질 비트까지 민다.
						uint32_t n2 = n << j;  // 지워진 비트 앞 비트수 만큼 당긴다.
						mArray[i] = n2 | frontBit; // 지워진 비트 앞의 비트들을 OR시킨다.
						
						bRemove = true;
						break;
					}
					frontBit += (1 << j);
				}
				else
				{
					if (b == false)
					{
						uint32_t n = mArray[i] >> (j + 1); // 지워질 비트까지 민다.
						uint32_t n2 = n << j;  // 지워진 비트 앞 비트수 만큼 당긴다.
						mArray[i] = n2 | frontBit; // 지워진 비트 앞의 비트들을 OR시킨다.

						bRemove = true;
						break;
					}
				}
			}
		}

		if (bRemove == true)
		{
			mSize--;
		}

		return bRemove;
	}

	template<size_t N>
	bool FixedVector<bool, N>::Get(unsigned int index)
	{
		unsigned int intIndex = index / MAX_BIT;
		unsigned int bitIndex = index % MAX_BIT;

		bool b = mArray[intIndex] & (1 << bitIndex);
		return b;
	}

	template<size_t N>
	bool FixedVector<bool, N>::operator[](unsigned int index)
	{
		unsigned int intIndex = index / MAX_BIT;
		unsigned int bitIndex = index % MAX_BIT;
		bool b = mArray[intIndex] & (1 << bitIndex);
		return b;
	}

	template<size_t N>
	int FixedVector<bool, N>::GetIndex(bool b) const
	{
		const unsigned int maxIndex = ((mSize - 1) / MAX_BIT) + 1;
		for (size_t i = 0; i < maxIndex; i++)
		{
			for (size_t j = 0; j < mSize && j < MAX_BIT; j++)
			{
				if ((mArray[i] & (1 << j)) > 0) // 1
				{
					if (b == true)
					{
						return (i * MAX_BIT) + j;
					}
				}
				else
				{
					if (b == false)
					{
						return (i * MAX_BIT) + j;
					}
				}
			}
		}
		return -1;
	}

	template<size_t N>
	size_t FixedVector<bool, N>::GetSize() const
	{
		return mSize;
	}

	template<size_t N>
	size_t FixedVector<bool, N>::GetCapacity() const
	{
		return N;
	}

	template<size_t N>
	void FixedVector<bool, N>::Print() const
	{
		const unsigned int maxIndex = ((mSize - 1) / MAX_BIT) + 1;
		for (size_t i = 0; i < maxIndex; i++)
		{
			cout << bitset<MAX_BIT>(mArray[i]) << endl;
		}

		cout << "==================================" << endl;
	}
}

스마트 포인터를 이용한 Doubly Linked List구현

#pragma once

#include <memory>

namespace lab10
{
	template<typename T>
	class Node
	{
	public:
		Node(std::unique_ptr<T> data);
		Node(std::unique_ptr<T> data, std::shared_ptr<Node<T>> prev);
		std::unique_ptr<T> Data;
		std::shared_ptr<Node<T>> Next;
		std::weak_ptr<Node<T>> Previous;

	};
	
	template<typename T>Node<T>::Node(std::unique_ptr<T> data)
		: Data(std::move(data))
	{
	}

	template<typename T>Node<T>::Node(std::unique_ptr<T> data, std::shared_ptr<Node<T>> prev)
		: Data(std::move(data))
		, Previous(prev)
	{
	}
}

#pragma once

#include <memory>
//#include<iostream>

namespace lab10
{
	template<typename T>
	class Node;

	template<typename T>
	class DoublyLinkedList
	{
	public:
		DoublyLinkedList();
		void Insert(std::unique_ptr<T> data);
		void Insert(std::unique_ptr<T> data, unsigned int index);
		bool Delete(const T& data);
		bool Search(const T& data) const;

		std::shared_ptr<Node<T>> operator[](unsigned int index) const;
		unsigned int GetLength() const;
	private:
		void insert(std::shared_ptr<Node<T>> node, std::unique_ptr<T> data);
		std::shared_ptr<Node<T>> getNodeByData(const T& data) const;
		std::shared_ptr<Node<T>> getNodeByIndex(unsigned int index) const;
		
		std::shared_ptr<Node<T>> mFirst;
		size_t mSize;
	};

	template<typename T>DoublyLinkedList<T>::DoublyLinkedList()
		: mFirst(nullptr)
		, mSize(0)
	{
	}

	template<typename T>
	void DoublyLinkedList<T>::Insert(std::unique_ptr<T> data)
	{
		Insert(std::move(data), mSize);
	}

	template<typename T>
	void DoublyLinkedList<T>::Insert(std::unique_ptr<T> data, unsigned int index)
	{
		if (mFirst == nullptr)
		{
			mFirst = std::make_shared<Node<T>>(std::move(data));
			mSize++;
			return;
		}

		std::shared_ptr<Node<T>> node = getNodeByIndex(index);
		if (node == nullptr)
		{
			// 해당 index에 node가 없으면 맨뒤에 추가한다.
			insert(getNodeByIndex(mSize - 1), std::move(data));
		}
		else
		{
			// 해당 index에 node가 있으면 node의 previous node 뒤에 붙여준다.
			insert(node->Previous.lock(), std::move(data));
		}
	}

	template<typename T>
	void DoublyLinkedList<T>::insert(std::shared_ptr<Node<T>> node, std::unique_ptr<T> data)
	{
		std::shared_ptr<Node<T>> newNode = std::make_shared<Node<T>>(std::move(data), node);
		mSize++;
		if (node == nullptr)
		{
			newNode->Next = mFirst;
			mFirst->Previous = newNode;
			mFirst = newNode;
			return;
		}

		if (node->Next != nullptr)
		{
			newNode->Next = node->Next;
			node->Next->Previous = newNode;
		}
		node->Next = newNode;
		newNode->Previous = node;
	}

	template<typename T>
	bool DoublyLinkedList<T>::Delete(const T& data)
	{
		std::shared_ptr<Node<T>> node = getNodeByData(data);
		if (node == nullptr)
			return false;

		std::shared_ptr<Node<T>> prevNode = node->Previous.lock();
		if (prevNode == nullptr)
		{
			node->Next->Previous.lock() = nullptr;
			mFirst = node->Next;
		}
		else
		{
			prevNode->Next = node->Next;

			if (node->Next != nullptr)
			{
				node->Next->Previous = node->Previous;
			}
		}
		--mSize;

		return true;
	}

	template<typename T>
	bool DoublyLinkedList<T>::Search(const T& data) const
	{
		if (getNodeByData(data) == nullptr)
			return false;

		return true;
	}
	
	template<typename T>
	std::shared_ptr<Node<T>> DoublyLinkedList<T>::getNodeByData(const T& data) const
	{
		if (mFirst == nullptr)
			return nullptr;

		std::shared_ptr<Node<T>> node = mFirst;
		while (node != nullptr)
		{
			if (*node->Data == data)
			{
				break;
			}

			node = node->Next;
		}
		return node;
	}

	template<typename T>
	std::shared_ptr<Node<T>> DoublyLinkedList<T>::getNodeByIndex(unsigned int index) const
	{
		if (index >= mSize)
			return nullptr;

		unsigned int i = 0;
		std::shared_ptr<Node<T>> node = mFirst;
		while (node != nullptr)
		{
			if (i == index)
			{
				break;
			}

			node = node->Next;
			i++;
		}
		return node;
	}

	template<typename T>
	std::shared_ptr<Node<T>> DoublyLinkedList<T>::operator[](unsigned int index) const
	{
		return getNodeByIndex(index);
	}

	template<typename T>
	unsigned int DoublyLinkedList<T>::GetLength() const
	{
		return mSize;
	}
}

스마트 포인터를 이용한 Binary Search Tree 구현

#pragma once

#include <memory>

namespace assignment4
{
	template<typename T>
	class TreeNode final
	{
	public:
		TreeNode(std::unique_ptr<T> data);
		TreeNode(std::shared_ptr<TreeNode<T>> parent, std::unique_ptr<T> data);

		std::unique_ptr<T> Data;
		std::shared_ptr<TreeNode<T>> Left;
		std::shared_ptr<TreeNode<T>> Right;
		std::weak_ptr<TreeNode<T>> Parent;
	private :
	};

	template<typename T>TreeNode<T>::TreeNode(std::unique_ptr<T> data)
		: Data(std::move(data))
	{
	}

	template<typename T>TreeNode<T>::TreeNode(std::shared_ptr<TreeNode<T>> parent, std::unique_ptr<T> data)
		: Parent(parent)
		, Data(std::move(data))
	{
	}
}

#pragma once

#include <memory>
#include <vector>

namespace assignment4
{
	template<typename T>
	class TreeNode;

	template<typename T>
	class BinarySearchTree final
	{
	public:
		void Insert(std::unique_ptr<T> data);
		bool Search(const T& data);
		bool Delete(const T& data);
		const std::weak_ptr<TreeNode<T>> GetRootNode() const;

		static std::vector<T> TraverseInOrder(const std::shared_ptr<TreeNode<T>> startNode);
	private:
		void insert(std::shared_ptr<TreeNode<T>> node, std::unique_ptr<T> data);
		std::shared_ptr<TreeNode<T>> search(std::shared_ptr<TreeNode<T>> node, const T& data) const;
		void changeParent(std::shared_ptr<TreeNode<T>> deleteNode, std::shared_ptr<TreeNode<T>> changeNode);
		std::shared_ptr<TreeNode<T>> mRoot;

	};

	template<typename T>
	void BinarySearchTree<T>::Insert(std::unique_ptr<T> data)
	{
		if (mRoot == nullptr)
		{
			std::shared_ptr<TreeNode<T>> node = std::make_shared<TreeNode<T>>(std::move(data));
			mRoot = node;
			return;
		}

		insert(mRoot, std::move(data));
	}
	template<typename T>
	void BinarySearchTree<T>::insert(std::shared_ptr<TreeNode<T>> parentNode, std::unique_ptr<T> data)
	{
		if (*data <= *parentNode->Data)
		{
			// left
			if (parentNode->Left == nullptr)
			{
				parentNode->Left = std::make_shared<TreeNode<T>>(parentNode, std::move(data));
			}
			else
			{
				insert(parentNode->Left, std::move(data));
			}
		}
		else
		{
			// right
			if (parentNode->Right == nullptr)
			{
				parentNode->Right = std::make_shared<TreeNode<T>>(parentNode, std::move(data));
			}
			else
			{
				insert(parentNode->Right, std::move(data));
			}
		}
	}

	template<typename T>
	const std::weak_ptr<TreeNode<T>> BinarySearchTree<T>::GetRootNode() const
	{
		return mRoot;
	}

	template<typename T>
	bool BinarySearchTree<T>::Search(const T& data)
	{
		std::shared_ptr<TreeNode<T>> node = search(mRoot, data);
		return node != nullptr;
	}

	template<typename T>
	std::shared_ptr<TreeNode<T>> BinarySearchTree<T>::search(std::shared_ptr<TreeNode<T>> node, const T& data) const
	{
		if (node == nullptr)
			return nullptr;

		if (*node->Data == data)
		{
			return node;
		}
		else if (data < *node->Data)
		{
			return search(node->Left, data);
		}
		else if (data > * node->Data)
		{
			return search(node->Right, data);
		}
	}

	template<typename T>
	bool BinarySearchTree<T>::Delete(const T& data)
	{
		std::shared_ptr<TreeNode<T>> node = search(mRoot, data);
		if (node == nullptr)
			return false;

		if (node->Left != nullptr && node->Right != nullptr)
		{
			std::shared_ptr<TreeNode<T>> sucecessorNode = node->Right;

			while (true)
			{
				if (sucecessorNode->Left == nullptr)
					break;

				sucecessorNode = sucecessorNode->Left;
			}

			changeParent(sucecessorNode, sucecessorNode->Right);
			changeParent(node, sucecessorNode);
			sucecessorNode->Left = node->Left;
			sucecessorNode->Right = node->Right;

			if (sucecessorNode->Left != nullptr)
			{
				sucecessorNode->Left->Parent = sucecessorNode;
			}
			if (sucecessorNode->Right != nullptr)
			{
				sucecessorNode->Right->Parent = sucecessorNode;
			}
		}
		else if (node->Left != nullptr)
		{
			changeParent(node, node->Left);
		}
		else if (node->Right != nullptr)
		{
			changeParent(node, node->Right);
		}
		else
		{
			changeParent(node, nullptr);
		}

		return true;
	}

	template<typename T>
	void BinarySearchTree<T>::changeParent(std::shared_ptr<TreeNode<T>> deleteNode, std::shared_ptr<TreeNode<T>> changeNode)
	{
		std::shared_ptr<TreeNode<T>> parent = deleteNode->Parent.lock();
		if (parent == nullptr)
		{
			mRoot = changeNode;
			return;
		}

		if (changeNode == nullptr)
		{
			if (parent->Left == deleteNode)
			{
				parent->Left = nullptr;
			}
			else if (parent->Right == deleteNode)
			{
				parent->Right = nullptr;
			}
		}
		else
		{
			if (parent->Left == deleteNode)
			{
				parent->Left = changeNode;
			}
			else if (parent->Right == deleteNode)
			{
				parent->Right = changeNode;
			}
			changeNode->Parent = deleteNode->Parent;
		}
	}

	template<typename T>
	std::vector<T> BinarySearchTree<T>::TraverseInOrder(const std::shared_ptr<TreeNode<T>> startNode)
	{
		std::vector<T> v;

		if (startNode == nullptr)
			return v;

		if (startNode->Left != nullptr)
		{
			v = TraverseInOrder(startNode->Left);
		}

		v.push_back(*startNode->Data);

		if (startNode->Right != nullptr)
		{
			std::vector<T> vR = TraverseInOrder(startNode->Right);
			v.insert(v.end(), vR.begin(), vR.end());
		}

		return v;
	}
}

기본 STL Conatainer 기능에 추가적인 기능을 넣기 위해 별도로 Template을 이용하여 만듬

공통 추가 기능 : 분산, 표준 편차, 최대 최소값 반환, 평균값, 총합 값

////////// smart stack /////////////
#pragma once

#include <stack>
#include <limits>

using namespace std;

namespace assignment3
{
	template <typename T>
	class SmartStack
	{
	public:
		SmartStack();
		SmartStack(const SmartStack& rhs);
		~SmartStack();
		SmartStack<T>& operator=(const SmartStack& rhs);

		T GetMax() const;
		T GetMin() const;
		double GetAverage() const;
		T GetSum() const;
		double GetVariance() const;
		double GetStandardDeviation() const;

		void Push(const T number);
		T Pop();
		T Peek() const;
		unsigned int GetCount() const;
		bool Empty() const;
	private:
		stack<T>* mMinStack;
		stack<T>* mMaxStack;
		T mTotal;
		double mSqureTotal;

		stack<T>* mStack;

	};

	template <typename T>
	inline SmartStack<T>::SmartStack()
		: mTotal(0)
		, mSqureTotal(0)
	{
		mMinStack = new stack<T>();
		mMaxStack = new stack<T>();

		mStack = new stack<T>();
	}

	template <typename T>
	inline SmartStack<T>::SmartStack(const SmartStack<T>& rhs)
		: mTotal(rhs.mTotal)
		, mSqureTotal(rhs.mSqureTotal)
	{
		mMinStack = new stack<T>(*rhs.mMinStack);
		mMaxStack = new stack<T>(*rhs.mMaxStack);
		mStack = new stack<T>(*rhs.mStack);
	}

	template <typename T>
	inline SmartStack<T>::~SmartStack()
	{
		delete mMinStack;
		delete mMaxStack;
		delete mStack;
	}

	template <typename T>
	inline SmartStack<T>& SmartStack<T>::operator=(const SmartStack<T>& rhs)
	{
		if (this == &rhs)
			return *this;

		delete mMinStack;
		delete mMaxStack;

		mMinStack = new stack<T>(*rhs.mMinStack);
		mMaxStack = new stack<T>(*rhs.mMaxStack);
		mTotal = rhs.mTotal;
		mSqureTotal = rhs.mSqureTotal;

		delete mStack;
		mStack = new stack<T>(*rhs.mStack);

		return *this;
	}

	template <typename T>
	inline void SmartStack<T>::Push(T number)
	{
		mStack->push(number);

		if (mMinStack->empty() == true || mMinStack->top() >= number)
		{
			mMinStack->push(number);
		}

		if (mMaxStack->empty() == true || mMaxStack->top() <= number)
		{
			mMaxStack->push(number);
		}

		mTotal += number;
		mSqureTotal += pow(number, 2);
	}

	template <typename T>
	inline T SmartStack<T>::Pop()
	{
		T number = mStack->top();
		
		if (mMinStack->empty() == false && mMinStack->top() == number)
		{
			mMinStack->pop();
		}

		if (mMaxStack->empty() == false && mMaxStack->top() == number)
		{
			mMaxStack->pop();
		}

		mTotal -= number;
		mSqureTotal -= pow(number, 2);

		mStack->pop();
		return number;
	}

	template <typename T>
	inline T SmartStack<T>::Peek() const
	{
		return mStack->top();
	}

	template <typename T>
	inline unsigned int SmartStack<T>::GetCount() const
	{
		return mStack->size();
	}

	template <typename T>
	inline bool SmartStack<T>::Empty() const
	{
		return mStack->empty();
	}

	template <typename T>
	inline T SmartStack<T>::GetMax() const
	{
		if (Empty() == true)
		{
			return numeric_limits<T>().lowest();
		}

		return mMaxStack->top();
	}

	template <typename T>
	inline T SmartStack<T>::GetMin() const
	{
		if (Empty() == true)
		{
			return numeric_limits<T>().max();
		}

		return mMinStack->top();
	}

	template <typename T>
	inline double SmartStack<T>::GetAverage() const
	{
		T sum = GetSum();
		unsigned int count = GetCount();
		double d = static_cast<double>(sum) / count;
		d = round(d * 1000) / 1000;
		return d;
	}

	template <typename T>
	inline T SmartStack<T>::GetSum() const
	{
		return mTotal;
	}

	template <typename T>
	inline double SmartStack<T>::GetVariance() const
	{
		double count = static_cast<double>(GetCount());
		double dSqureTotalAverage = mSqureTotal / count;
		double dAverage = mTotal / count;
		double dResult = dSqureTotalAverage - pow(dAverage, 2);
		return round(dResult * 1000) / 1000;
	}

	template <typename T>
	inline double SmartStack<T>::GetStandardDeviation() const
	{
		double count = static_cast<double>(GetCount());
		double dSqureTotalAverage = mSqureTotal / count;
		double dAverage = mTotal / count;
		double dResult = dSqureTotalAverage - pow(dAverage, 2);
		return round(sqrt(dResult) * 1000) / 1000;
	}
}

// smart Queue ///////////////////////////////
#pragma once

#include <queue>
#include <limits>

using namespace std;

namespace assignment3
{

	template <typename T>
	class SmartQueue
	{
	public:
		SmartQueue();
		~SmartQueue();

		void Enqueue(const T number);
		T Peek() const;
		T Dequeue();
		T GetMax();
		T GetMin();
		double GetAverage() const;
		T GetSum() const;
		double GetVariance() const;
		double GetStandardDeviation() const;
		unsigned int GetCount() const;
	private:
		T mTotal;
		double mSqureTotal;
		queue<T> mQueue;
	};

	template <typename T>
	inline SmartQueue<T>::SmartQueue()
		: mTotal(0)
		, mSqureTotal(0)
	{
	}

	template <typename T>
	inline SmartQueue<T>::~SmartQueue()
	{
	}

	template <typename T>
	inline void SmartQueue<T>::Enqueue(T number)
	{
		mQueue.push(number);
		mTotal += number;
		mSqureTotal += pow(number, 2);
	}

	template <typename T>
	inline T SmartQueue<T>::Dequeue()
	{
		T number = mQueue.front();

		mTotal -= number;
		mSqureTotal -= pow(number, 2);

		mQueue.pop();
		return number;
	}

	template <typename T>
	inline T SmartQueue<T>::Peek() const
	{
		return mQueue.front();
	}

	template <typename T>
	inline unsigned int SmartQueue<T>::GetCount() const
	{
		return mQueue.size();
	}

	template <typename T>
	inline T SmartQueue<T>::GetMax()
	{
		if (mQueue.empty() == true)
		{
			return numeric_limits<T>().lowest();
		}

		T tMax = mQueue.front();
		unsigned int size = mQueue.size();
		while (size > 0)
		{
			T t = mQueue.front();
			mQueue.pop();
			mQueue.push(t);
			if (t > tMax)
				tMax = t;

			size--;
		}

		return tMax;
	}

	template <typename T>
	inline T SmartQueue<T>::GetMin()
	{
		if (mQueue.empty() == true)
		{
			return numeric_limits<T>().max();
		}

		T tMin = mQueue.front();
		unsigned int size = mQueue.size();
		while (size > 0)
		{
			T t = mQueue.front();
			mQueue.pop();
			mQueue.push(t);
			if (t < tMin)
				tMin = t;

			size--;
		}

		return tMin;
	}

	template <typename T>
	inline double SmartQueue<T>::GetAverage() const
	{
		T sum = GetSum();
		unsigned int count = GetCount();
		double d = static_cast<double>(sum) / count;
		d = round(d * 1000) / 1000;
		return d;
	}

	template <typename T>
	inline T SmartQueue<T>::GetSum() const
	{
		return mTotal;
	}

	template <typename T>
	inline double SmartQueue<T>::GetVariance() const
	{
		double count = GetCount();
		double dSqureTotalAverage = mSqureTotal / count;
		double dAverage = mTotal / count;
		double dResult = dSqureTotalAverage - pow(dAverage, 2);
		return round(dResult * 1000) / 1000;
	}

	template <typename T>
	inline double SmartQueue<T>::GetStandardDeviation() const
	{
		double count = GetCount();
		double dSqureTotalAverage = mSqureTotal / count;
		double dAverage = mTotal / count;
		double dResult = dSqureTotalAverage - pow(dAverage, 2);
		return round(sqrt(dResult) * 1000) / 1000;
	}
}

// QueueStack ///////////////////////////////
// 여러개의 stack을 Queue로 관리하는 container
// stack의 maxsize를 정할 수 있다.
// stack의 maxsize를 초과하면 새로운 stack이 생성되어 Queue에 들어간다.
#pragma once

#include <queue>
#include <stack>
#include <limits>
#include <cmath>
#include "SmartStack.h"

using namespace std;

namespace assignment3
{
	template <typename T>
	class QueueStack
	{
	public:
		QueueStack() = delete;
		QueueStack(const unsigned int maxStackSize);
		QueueStack(const QueueStack<T>& rhs);
		~QueueStack();
		QueueStack<T>& operator=(const QueueStack<T>& rhs);

		void Enqueue(const T number);
		T Peek() const;
		T Dequeue();
		T GetMax() const;
		T GetMin() const;
		double GetAverage() const;
		T GetSum() const;
		unsigned int GetCount() const;
		unsigned int GetStackCount() const;
	private:
		T mTotal;

		queue<SmartStack<T>* >* mQueue;
		const unsigned int mMaxStackSize;
	};

	template <typename T>
	inline QueueStack<T>::QueueStack(const unsigned int maxStackSize)
		: mTotal(0)
		, mMaxStackSize(maxStackSize)
	{
		mQueue = new queue<SmartStack<T>*>();
	}

	template <typename T>
	inline QueueStack<T>::QueueStack(const QueueStack<T>& rhs)
		: mTotal(rhs.mTotal)
		, mMaxStackSize(rhs.maxStackSize)
	{
		mQueue = new queue<SmartStack<T>*>();
	}

	template <typename T>
	inline QueueStack<T>::~QueueStack()
	{
		while (mQueue->empty() == false)
		{
			SmartStack<T>* s = mQueue->front();
			mQueue->pop();
			delete s;
		}
		delete mQueue;
	}

	template <typename T>
	inline QueueStack<T>& QueueStack<T>::operator=(const QueueStack& rhs)
	{
		if (this == &rhs)
			return *this;

		mTotal = rhs.mTotal;

		while (mQueue->empty() == false)
		{
			SmartStack<T>* s = mQueue->front();
			mQueue->pop();
			delete s;
		}
		delete mQueue;

		mQueue = new queue<SmartStack<T>*>();
		
		unsigned int size = rhs.GetStackCount();
		while (size > 0)
		{
			SmartStack<T>* s = rhs.mQueue->front();
			rhs.mQueue->pop();
			rhs.mQueue->push(s);
			mQueue->push(new SmartStack<T>(*s));

			size--;
		}

		return *this;
	}

	template <typename T>
	inline void QueueStack<T>::Enqueue(const T number)
	{
		if (mQueue->empty() == true)
		{
			SmartStack<T>* s = new SmartStack<T>();
			mQueue->push(s);
		}

		SmartStack<T>* s = mQueue->back();
		
		if (s->GetCount() >= mMaxStackSize)
		{
			SmartStack<T>* s = new SmartStack<T>();
			s->Push(number);
			mQueue->push(s);
		}
		else
		{
			s->Push(number);
		}

		mTotal += number;
	}

	template <typename T>
	inline T QueueStack<T>::Peek() const
	{
		SmartStack<T>* s =  mQueue->front();
		return s->Peek();
	}

	template <typename T>
	inline T QueueStack<T>::Dequeue()
	{
		SmartStack<T>* s = mQueue->front();
		T number = s->Peek();
		s->Pop();

		if (s->GetCount() == 0)
		{
			mQueue->pop();
			delete s;
		}

		mTotal -= number;

		return number;
	}

	template <typename T>
	inline unsigned int QueueStack<T>::GetCount() const
	{
		unsigned int size = mQueue->size();

		unsigned int totalSize = 0;
		while (size > 0)
		{
			SmartStack<T>* s = mQueue->front();
			mQueue->pop();
			mQueue->push(s);

			totalSize += s->GetCount();

			size--;
		}

		return totalSize;
	}

	template <typename T>
	inline unsigned int QueueStack<T>::GetStackCount() const
	{
		return mQueue->size();
	}

	template <typename T>
	inline T QueueStack<T>::GetMax() const
	{
		if (mQueue->empty() == true)
		{
			return numeric_limits<T>().lowest();
		}

		SmartStack<T>* s = mQueue->front();
		T tMax = s->GetMax();

		unsigned int size = mQueue->size();
		while (size > 0)
		{
			s = mQueue->front();
			T t = s->GetMax();
			mQueue->pop();
			mQueue->push(s);

			if (t > tMax)
				tMax = t;

			size--;
		}

		return tMax;
	}

	template <typename T>
	inline T QueueStack<T>::GetMin() const
	{
		if (mQueue->empty() == true)
		{
			return numeric_limits<T>().max();
		}

		SmartStack<T>* s = mQueue->front();
		T tMin = s->GetMin();

		unsigned int size = mQueue->size();
		while (size > 0)
		{
			s = mQueue->front();
			T t = s->GetMin();
			mQueue->pop();
			mQueue->push(s);

			if (t < tMin)
				tMin = t;

			size--;
		}

		return tMin;
	}

	template <typename T>
	inline double QueueStack<T>::GetAverage() const
	{
		T sum = GetSum();
		unsigned int count = GetCount();
		double d = sum / static_cast<double>(count);
		d = round(d * 1000) / 1000;
		return d;
	}

	template <typename T>
	inline T QueueStack<T>::GetSum() const
	{
		return mTotal;
	}
}

char 배열을 이용한 string class 구현

// MyString.h ////////////////////////////////////////////////////
#pragma once
namespace assignment1
{
	class MyString
	{
	public:
		MyString(const char* s);
		MyString(const MyString& other);
		~MyString();

		unsigned int GetLength() const;
		const char* GetCString() const;
		void Append(const char* s);
		MyString operator+(const MyString& other) const;
		int IndexOf(const char* s);
		int LastIndexOf(const char* s);
		void Interleave(const char* s);
		bool RemoveAt(unsigned int i);
		void PadLeft(unsigned int totalLength);
		void PadLeft(unsigned int totalLength, const char c);
		void PadRight(unsigned int totalLength);
		void PadRight(unsigned int totalLength, const char c);
		void Reverse();
		bool operator==(const MyString& rhs) const;
		MyString& operator=(const MyString& rhs);
		void ToLower();
		void ToUpper();
	private:
		const int PAD_LEFT = 0;
		const int PAD_RIGHT = 1;
		char* mString;
		int mStringLength;

		void pad(unsigned int totalLength, const char c, int padDir);
		void swap(char& a, char& b);
		int getStrLen(const char* s) const;
		void copyMemory(char* dst, const char* src, int size) const;
		void strConcat(char* dst, const char* src) const;
	};
}

// MyString.cpp ////////////////////////////////////////////////////

#include "MyString.h"

using namespace std;

namespace assignment1
{
	MyString::MyString(const char* s)
		: mStringLength(getStrLen(s))
	{
		mString = new char[mStringLength + 1];
		copyMemory(mString, s, mStringLength + 1);
	}

	MyString::MyString(const MyString& other)
		: mStringLength(getStrLen(other.mString))
	{
		mString = new char[mStringLength + 1];
		copyMemory(mString, other.mString, mStringLength + 1);
	}

	MyString::~MyString()
	{
		delete[] mString;
	}

	unsigned int MyString::GetLength() const
	{
		return mStringLength;
	}

	const char* MyString::GetCString() const
	{
		return mString;
	}

	void MyString::Append(const char* s)
	{
		int sLen = getStrLen(s);
		if (sLen == 0)
			return;

		int length = mStringLength + sLen;
		char* strAppend = new char[length + 1];

		copyMemory(strAppend, mString, mStringLength + 1);
		delete[] mString;

		strConcat(strAppend, s);
		mString = strAppend;
		mStringLength = length;
	}

	MyString MyString::operator+(const MyString& other) const
	{
		char* result = new char[getStrLen(mString) + getStrLen(other.mString) + 1];
		copyMemory(result, mString, mStringLength + 1);
		strConcat(result, other.mString);
		MyString str = MyString(result);
		
		delete[] result;
		return str;
	}

	int MyString::IndexOf(const char* s)
	{
		int sLen = getStrLen(s);
		if (sLen == 0)
			return 0;

		int i = 0;
		int j = 0;
		int index = -1;
		int count = 0;
		for (i = 0; i < mStringLength; i++)
		{
			if (mString[i] == s[0])
			{
				count = 0;
				for (j = 0; j < sLen; j++)
				{
					if (mString[i + j] != s[j])
					{
						break;
					}
					count++;
				}

				if (count == sLen)
				{
					index = i;
					break;
				}
			}
		}

		return index;
	}

	int MyString::LastIndexOf(const char* s)
	{
		int sLen = getStrLen(s);
		if (sLen == 0)
			return mStringLength;

		int i = 0;
		int j = 0;
		int index = -1;
		int count = 0;
		for (i = mStringLength - 1; i >= 0; i--)
		{
			if (mString[i] == s[sLen - 1])
			{
				count = 0;
				int startIndex = i - (sLen - 1);
				for (j = 0; j < sLen; j++)
				{
					if (mString[startIndex + j] != s[j])
					{
						break;
					}
					count++;
				}

				if (count == sLen)
				{
					index = startIndex;
					break;
				}
			}
		}

		return index;
	}

	void MyString::Interleave(const char* s)
	{
		int sLen = getStrLen(s);
		if (sLen == 0)
			return;

		int length = mStringLength + sLen;
		char* str = new char[length + 1];

		int i = 0;
		int mIndex = 0;
		int sIndex = 0;
		for (i = 0; i < length; i++)
		{
			if (i % 2 == 0)
			{
				if (mIndex < mStringLength)
				{
					str[i] = mString[mIndex];
					mIndex++;
				}
				else
				{
					str[i] = s[sIndex];
					sIndex++;
				}
			}
			else if (i % 2 == 1)
			{
				if (sIndex < sLen)
				{
					str[i] = s[sIndex];
					sIndex++;
				}
				else
				{
					str[i] = mString[mIndex];
					mIndex++;
				}
			}
		}

		str[length] = 0;

		delete[] mString;

		mString = str;
		mStringLength = length;
	}

	bool MyString::RemoveAt(unsigned int index)
	{
		int idx = (signed)index;
		if (idx >= mStringLength)
			return false;

		char* str = new char[mStringLength];
		for (int i = 0; i < mStringLength; i++)
		{
			if (i < idx)
			{
				str[i] = mString[i];
			}
			else
			{
				str[i] = mString[i + 1];
			}
		}

		delete[] mString;

		mString = str;
		mStringLength = mStringLength - 1;

		return true;
	}

	void MyString::PadLeft(unsigned int totalLength)
	{
		PadLeft(totalLength, ' ');
	}

	void MyString::PadLeft(unsigned int totalLength, const char c)
	{
		pad(totalLength, c, PAD_LEFT);
	}

	void MyString::PadRight(unsigned int totalLength)
	{
		PadRight(totalLength, ' ');
	}

	void MyString::PadRight(unsigned int totalLength, const char c)
	{
		pad(totalLength, c, PAD_RIGHT);
	}

	void MyString::pad(unsigned int totalLength, const char c, int padDir)
	{
		int tLen = (signed)totalLength;
		if (tLen <= mStringLength)
			return;
		
		char* str = new char[tLen + 1];
		int addCount = tLen - mStringLength;
		int i = 0;
		for (i = 0; i < tLen; i++)
		{
			if (padDir == PAD_LEFT)
			{
				if (i < addCount)
				{
					str[i] = c;
				}
				else
				{
					str[i] = mString[i - addCount];
				}
			}
			else if (padDir == PAD_RIGHT)
			{
				if (i < mStringLength)
				{
					str[i] = mString[i];
				}
				else
				{
					str[i] = c;
				}
			}
		}
		str[tLen] = 0;

		delete[] mString;

		mString = str;
		mStringLength = tLen;
	}

	void MyString::Reverse()
	{
		int i = 0, j = mStringLength - 1;
		while (true)
		{
			if (i > j)
			{
				break;
			}
			swap(mString[i], mString[j]);
			i++;
			j--;
		}
	}

	void MyString::swap(char& a, char& b)
	{
		char temp = a;
		a = b;
		b = temp;
	}

	bool MyString::operator==(const MyString& rhs) const
	{
		if (mStringLength != rhs.mStringLength)
			return false;

		for (int i = 0; i < mStringLength; i++)
		{
			if (mString[i] != rhs.mString[i])
			{
				return false;
			}
		}
		return true;
	}

	MyString& MyString::operator=(const MyString& rhs)
	{
		if (*this == rhs)
			return *this;

		delete[] mString;

		mStringLength = rhs.mStringLength;
		mString = new char[mStringLength + 1];

		copyMemory(mString, rhs.mString, mStringLength + 1);
		return *this;
	}

	void MyString::ToLower()
	{
		for (int i = 0; i < mStringLength; i++)
		{
			if (mString[i] < 65 || mString[i] > 90)
				continue;

			mString[i] += 32;
		}
	}

	void MyString::ToUpper()
	{
		for (int i = 0; i < mStringLength; i++)
		{
			if (mString[i] < 97 || mString[i] > 122)
				continue;

			mString[i] -= 32;
		}
	}

	int MyString::getStrLen(const char* s) const
	{
		int i = 0;
		int count = 0;
		while (true)
		{
			if (s[i] == 0)
			{
				break;
			}
			count++;
			i++;
		}
		return count;
	}

	void MyString::copyMemory(char* dst, const char* src, int size) const
	{
		int i = 0;
		for (i = 0; i < size; i++)
		{
			if (i > getStrLen(src))
				break;

			dst[i] = src[i];
		}
	}

	void MyString::strConcat(char* dst, const char* src) const
	{
		int dstLen = getStrLen(dst);
		int srcLen = getStrLen(src);
		int size = dstLen + srcLen + 1;
		for (int i = dstLen; i < size; i++)
		{
			dst[i] = src[i - dstLen];
		}
	}
}