RTTI란

RTTI란 Run Time Type Infomation으로
프로그램 실행 즉 런타임 중 타입정보를 식별할 수 있는것 입니다.
정확하게 실행중에 기반 클래스 타입 포인터의 실체를 밝혀내는것입니다.

RTTI는 정적 타입체크와 각상함수들로는 해결이 불가능한 문제들이 제시되어

C++ 표준화 위원회가 RTTI를 추가 승인하게 되어 표준이 되었습니다.

1991: First meeting of WG21

1994: CD1 <RTTI 등장 : CD2에 내용이 없어서 CD1으로 판단하였는데 정확하지 않습니다>

1996: CD2  <Exception Handling, Template 등장>

1997: FDIS (Final Draft International Standard)

1998: C++ Standard (C++98)

RTTI가 필요한 이유

RTTI는 다형성을 가진 클래스 즉 가상함수가 하나라도 포함된 클래스의 타입을 알아내기 위해서 나왔다고 볼 수 있습니다.

많은 이유 중 하나는 가상함수가 포함된 클래스의 타입은 동적 바인딩에 의하여 런타임에 결정되게 되므로

런타임에 가상함수가 포함된 클래스의 타입을 확인하기 위하여 만들어졌습니다.

클래스의 다형성은 가상함수에 의해 구현되므로

RTTI는 가상함수를 갖는 클래스의 상속관계에서 사용이 가능합니다.

가상함수가 없는 클래스는 가상함수 테이블이 없기 때문에

RTTI에 대한 정보 또한 존재하지 않아 포인터의 타입을 가져와 처리를 합니다.

RTTI를 이용한 대표적 기능

• typeid
• type_info
• dynamic_cast

Typeid는 두 객체의 데이터형이 같은지 확인이 가능하고 개체의 정확한 형식을 식별하는데 사용됩니다.

Typeid는 <typeinfo> 헤더를 선언하고

typeid(변수 or 자료형)으로

#include <typeinfo>
#include <iostream>

int main()
{
	const std::type_info& type = typeid(int);
	std::cout << type.name() << std::endl;
	return 0;
}

와 같이 선언이 가능합니다.

type_info는 이 typeid연산자의 반환 값으로 <typeinfo> 헤더 파일에 정의되어 있는 클래스이며

어떤 특별한 데이터형에 대한 정보를 저장합니다.

이 type_info는 특별한 데이터형을 비교할 수 있도록 == 와 !=의 연산자가 사용이 가능합니다.

마지막 dynamic_cast는 이 RTTI에 대하여 의존적이며

런타임에 상속 관계를 분석하여 형 변환이 가능하면 형 변환을 진행하고

불가능하다면 포인터의 경우 nullptr을 반환, 참조의 경우 std::bad_cast를 throw합니다.

제가 작성한 코드에서는 dynamic_cast를 위 3가지 중 제일 많이 사용하였으며

추후 캐스팅을 다룰 예정이지만 상속관계를 체크하므로 static_cast보다는 조금 느린 단점이 존재합니다.

먼저 캐스팅이란 타입을 변환하는 것을 말하며 '형변환'이라고도 합니다.

업캐스팅과 다운캐스팅은 정의만 정리합니다.

업캐스팅

업 캐스팅이란 하위 클래스의 객체가 상위 클래스 타입으로 형변환으로 변환되는 것을 말합니다.

• 업캐스팅시 원래 자식 클래스의 메소드는 접근이 불가능하다.
• 명시적 형변환을 하지 않아도 형변환이 가능하다.

다형성을 통하여 재사용성을 높일 수 있습니다.

업캐스팅을 통하여 사용할 수 있는 예로는

• 동일한 기반(부모) 클래스를 처리하는 함수를 사용하여 같은 파생(자식) 클래스를 한번에 사용할 수 있습니다.
• 동일한 기반(부모)를 가지는 클래스들을 보관하는 컨테이너를 통한 사용이 가능합니다.

다운캐스팅

다운캐스팅이란 업캐스팅이 되면 기본 클래스에 정의된 멤버만 호출할 수 있기 때문에 동일한 타입의 포인터가 동일한 타입을 가리키게 하는 것을 말합니다.

• 다운캐스팅은 반드시 명시적 형변환이 필요하다.
• 서로 동일한 타입이여야한다.

이러한 다운캐스팅의 대표적인 예는 dynamic_cast로 상속 관계에 있는 클래스간의 형변환이 있으며 RTTI를 통하여 다양한 방식의 타입 캐스팅을 지원합니다.(이는 나중에...)

오버로딩(Overloading) : 함수의 중복 정의

오버로딩이란 같은 이름의 함수를 호출하더라도 매개변수에 따라 다른 함수가 실행되는 것입니다.

간단히 코드로 작성해 보겠습니다.

#include <iostream>
#include <string>
using namespace std;

inline void Test(int iTest)	{ cout << iTest << endl; }
inline void Test(string strTest){ cout << strTest << endl; }

int main()
{
	Test(1);
	Test("Hello World!");
	return 0;
}

같은 Test라는 함수를 호출하였음에도 

매개변수에 따라 1과 Hello World!가 출력이 되므로

같은 이름으로 다른 기능을 사용할 수 있게 됩니다.

예시로 Sum()으로 두 변수를 더하는 함수인데 (int, int), (int, float), (float, float) ... 을 만들고 싶다면

Sum_IntToInt, Sum_IntToFloat 가 아닌 Sum(int *, int *), Sum(int *, float *)와 같이

매개변수를 다르게 하여 활용이 가능하여 다형성의 예로 들수 있습니다.

오버라이딩 : 함수 재정의

오버라이딩이란 상속관계에서 부모클래스의 함수를 사용하지 않고 자신만의 함수로 재정의하여 사용하는 것을 말합니다.

#include <iostream>
using namespace std;

class Parent
{
public:
	inline void Test(int iTest) { cout << "Parent : " << iTest << endl; }
};

class Child : public Parent
{
public:
	inline void Test(int iTest) { cout << "Child : " << iTest << endl; }
};

int main()
{
	Parent P;
	Child C;
	P.Test(777);
	C.Test(777);
	return 0;
}

다음과 같이 같은 Test를 호출하였지만 자식은 부모의 Test를 재정의하여

자신만의 Test를 가질수 있게 됩니다.

자식에서의 오버라이딩을 할 때에는

• 메소드(함수)의 이름이 같아야 한다.
• 메소드(함수)의 인자 개수, 자료형이 같아야 한다.
• 리턴형이 같아야 한다.
• 재정의시 구현부가 동일하거나 추가되어야 한다.
• 오버라이드하는 함수가 상위(부모) 클래스에 존재하여야 한다.

위의 조건을 지켜야합니다.

사전순을 못봐 정렬을 안하여 틀렸지만 쉬운 문제여서 바로 코드를 올립니다.

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int iN = 0, iM = 0;
	cin >> iN >> iM;
	map<string, int> map_First;
	vector<string> pAnswer;
	string strTemp;
	pAnswer.reserve(iN > iM ? iN : iM);
	for (int i = 0; i < iN; i++)
	{
		cin >> strTemp;
		map_First.emplace(strTemp, 1);
	}
	for (int i = 0; i < iM; i++)
	{
		cin >> strTemp;
		if (map_First.find(strTemp) != map_First.end())
			pAnswer.emplace_back(strTemp);
	}
	cout << pAnswer.size() << "\n";
	sort(pAnswer.begin(), pAnswer.end());
	for (auto& iter : pAnswer)
		cout << iter << "\n";
	return 0;
}

추후 굳이 map을 안쓰고 vector만 이용하여

binary_search를 사용하여도 된다는 것을 알았습... algorithm에 있다는걸 까먹

binary_search : Algorithm 헤더의 함수로써 정렬된 배열을 이진 탐색으로 true와 false로 찾아줌

문제를 읽고 vector를 2개를 두고

정렬한 후에 unique로 제외하여 lower_bound를 사용하여

풀이가 가능할 것 같았지만 괜히 unique를 안쓰고 싶어져서 코드가 더럽다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int iN = 0;

int main()
{
	cin >> iN;
	vector<int> vUnorder;
	map<int, vector<int>> map_Order;
	vUnorder.reserve(iN);
	int iTemp = 0;
	for (int i = 0; i < iN; i++)
	{
		cin >> iTemp;
		vUnorder.emplace_back(iTemp);
		if (map_Order.find(iTemp) != map_Order.end())
			map_Order.find(iTemp)->second.emplace_back(i);
		else
			map_Order.emplace(iTemp, vector<int>(1, i));
	}
	auto iter_map = map_Order.begin();
	for (int i = 0; i < map_Order.size(); i++)
	{
		int iNum = iter_map->first;
		for (int j = 0; j < map_Order[iNum].size(); j++)
			vUnorder[map_Order[iNum][j]] = i;
		iter_map++;
	}
	for (int i = 0; i < iN; i++)
		cout << vUnorder[i] << " ";
	cout << "\n";
	return 0;
}

map을 사용하여 중복을 제거하고 물론 옳은 방법은 아닌거 같다

map의 key를 사용하여 정렬된 순서로 0부터 순차적으로 압축한 값을 출력하였다.

이 문제는 tie와 sync_with_stdio를 알려주는 문제같다.

문제 자체는 어렵지 않으니 바로 코드를 첨부하려한다.

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int iSite = 0, iPassWord = 0;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> iSite >> iPassWord;
	unordered_map<string, string> umap_Site;
	umap_Site.reserve(iSite);

	for (int i = 0; i < iSite; i++)
	{
		string strSite = "";
		string strPass = "";
		cin >> strSite >> strPass;
		umap_Site.emplace(make_pair(strSite, strPass));
	}
	for (int i = 0; i < iPassWord; i++)
	{
		string strFind = "";
		cin >> strFind;
		cout << umap_Site.find(strFind)->second << "\n";
	}
	return 0;
}

먼저 B의 값을 보고 long long으로 타입 지정을 결정했고

감이 잘 안와 시간이 오래 걸렸다.

배열의 최대값에서부터 내려가며 검사 후 인벤과 비교하며 수행하려니

너무 복잡한 코드가 나올 것 같아 패스하였고

그렇다고 0부터 최대 높이인 256까지 검사를 진행하면 너무 많은 시간이 소비될 것 같아

1차 배열의 각 높이를 Count하고 0부터 256까지 257번의 계산을 수행하여 계산을 진행하였다.

이렇게 하면 0부터 시작하여 O(n^3)이 아닌 O(n^2)으로 계산을 할 수 있어 진행을 하였다.

int main()
{
	vector<int> vMap;
	cin >> iCol >> iRow >> iInven;
	vMap.assign(MAX_HEIGHT, 0);
	int iHight = 0;
	for (int i = 0; i < iCol; i++)
	{
		for (int j = 0; j < iRow; j++)
		{
			cin >> iHight;
			vMap[iHight]++;
		}
	}
	for (int z = 0; z < MAX_HEIGHT; z++)
		SearchMap(vMap, z);
	cout << iDstT << " " << iDstH << "\n";
	return 0;
}

먼저 vMap을 MAX_HEIGHT(257)개의 배열로 초기화를 수행 후 각각의 입력된 값을 높이에 저장하여

Hash와 비슷하게 구현을 하였고 MAX_HEIGHT만큼의 SerachMap을 수행하여 계산을 하였다.

void SearchMap(const vector<int>& vMap, int iDstHeight)
{
	int iPushCnt = 0, iPopCnt = 0;
	for (int i = 0; i < iDstHeight; i++)	//목표 높이보다 낮으니 추가
		iPushCnt += (iDstHeight - i) * vMap[i];

	for (int i = iDstHeight + 1; i < MAX_HEIGHT; i++ )	//목표 높이보다 높으니 차감
		iPopCnt += (i - iDstHeight) * vMap[i];

	if (iPushCnt <= iInven + iPopCnt)
	{
		if (iDstT >= (iPushCnt + (iPopCnt * 2)))
		{
			iDstT = (iPushCnt + (iPopCnt * 2));
			iDstH = iDstHeight;
		}
	}
}

SearchMap은 반복문으로 들어오는 목표 높이를 기준으로

목표 높이보다 낮거나 높을때를 Count하여 인벤과 비교하여 현재 높이가 성립이 되고

이미 구해진 최단시간보다 작으면 갱신을 하였다.

아래는 전체 코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int MAX_HEIGHT = 257;
long long iCol = 0, iRow = 0, iMin = 0, iMax = 0, iInven = 0;
long long iDstT = INT_MAX, iDstH = 0;

void SearchMap(const vector<int>& vMap, int iDstHeight)
{
	int iPushCnt = 0, iPopCnt = 0;
	for (int i = 0; i < iDstHeight; i++)	//목표 높이보다 낮으니 추가
		iPushCnt += (iDstHeight - i) * vMap[i];

	for (int i = iDstHeight + 1; i < MAX_HEIGHT; i++ )	//목표 높이보다 높으니 차감
		iPopCnt += (i - iDstHeight) * vMap[i];

	if (iPushCnt <= iInven + iPopCnt)
	{
		if (iDstT >= (iPushCnt + (iPopCnt * 2)))
		{
			iDstT = (iPushCnt + (iPopCnt * 2));
			iDstH = iDstHeight;
		}
	}
}

int main()
{
	vector<int> vMap;
	cin >> iCol >> iRow >> iInven;
	vMap.assign(MAX_HEIGHT, 0);
	int iHight = 0;
	for (int i = 0; i < iCol; i++)
	{
		for (int j = 0; j < iRow; j++)
		{
			cin >> iHight;
			vMap[iHight]++;
		}
	}
	for (int z = 0; z < MAX_HEIGHT; z++)
		SearchMap(vMap, z);
	cout << iDstT << " " << iDstH << "\n";
	return 0;
}

그 동안 많은 문제를 풀었지만 블로그에 올리지 않았고

오프라인이나 온라인으로 코딩 문제를 해결했었지만

앞으로 푼 문제를 블로그에 포스팅해서 정리를 해보고

추후 다시 봐서 개선점을 봐야겠다.

게임 회사에서는 프로그래머스에서 시험을 코딩 테스트를 보았었지만

프로그래머스의 문제보다 백준의 문제가 많이 출제되는것 같아

Solved.ac를 통한 순서대로의 문제를 해결하려한다.