C++ TMP를 이용해서 2015년의 13일의 금요일 계산하기
흑마법의 세계에 어서오세요!

2015. 04. 13

개요

2015년 3월 15일에 코딩 전력 60분!에서 13일의 금요일을 구하는 문제를 던졌다. 다음 트윗에서 Short coding을 목표로 제시했지만 나는 그걸 못봤다. 그래서 아무 생각없이 몇년만에 C++ Template Metaprogramming로 흑마법을 써보기로 했다. 실력이 없어서 1시간 안에 작성하는 것은 실패했지만 어떻게든 완성시켜서 코드를 Gist에 올려두었다. 코드 작성한지 1달정도 지나니 어떻게 짯는지 기억이 안나서 글로 정리하면서 코드를 개선해보기로 했다.

제약사항

오랜만에 C++ Template Metaprogramming로 흑마법을 쓰는만큼 제대로 써보기로 했다. 추가로 1달만에 코드를 수정하는거니 몇가지 제약을 걸었다.

Remember, No if/for/while. if/for/while 키워드를 사용하지 않는다. 최초 구현체에는 if를 썻는데 그거조차 없애보자.
Variadic template 한번도 써본적 없는 가변인자 템플릿을 쓴다. 한번도 써본적 없는 문법이라서 @summerlight00님께 샘플코드를 받았다.

알고리즘

날짜를 알때 요일을 계산할수 있는 다양한 알고리즘이 존재한다. 하지만 몇년만에 C++ 템플릿 메타 프로그래밍을 하는거니까 무식한 방법을 선택했다.

2000/01/01이 무슨 요일인지 확인한다.
2000/01/01로부터 며칠이 지나면 2015/01/13이 되는지 확인한다
경과한 일수를 7로 나눈 나머지를 얻는다
2000/01/01의 요일에서 나머지를 더하면 2015/01/13의 요일을 얻을수 있다.
같은 방법으로 2015/02/13, …, 2015/12/13의 요일을 확인한다.
13일의 금요일인 경우에만 결과값에 집어넣는다.

무엇이 필요한가?

코드를 작성하기전에 필요한 것을 정리해보자.

2000/01/01의 요일과 요일 상수가 필요하다. 기준을 잡는 것이 모든 일의 시작이다. 또한 토요일, 일요일, 월요일중에서 무엇을 기준으로 할지 정해야 계산할 수 있다.

다음으로는 2000/01/01로 YYYY/MM/DD까지의 간격이 며칠인지 계산할수 있어야한다. 이를 위해서는 첫번째로 YY년이 윤년인지 아닌이 알수 있어야한다. 윤년인지 파악할수 있으면 2000/01/01로부터 YYYY/01/01까지의 간격을 계산할수 있다. 다음으로는 월에 며칠이 있는지 계산할수 있어야한다. 1월에는 31일이 있다는걸 알수 있으면 YYYY/01/01로 부터 YYYY/02/01의 요일을 추정할수 있을것이다.

다음으로는 반복문을 만들수 있어야한다. 반복문을 이용하여 2015년 1월부터 12월까지의 13일의 금요일을 계산할수 있을것이다.

요일상수와 2000/01/01

2000/01/01은 토요일이다. 이 정보는 나중에 사용할 예정이다.

요일의 시작은 월요일로 잡았다.

enum {
	DAY_MON = 0,
	DAY_TUE,
	DAY_WED,
	DAY_THU,
	DAY_FRI,
	DAY_SAT,
	DAY_SUN
};

윤년

윤년인지 확인하는 공식은 위키 를 참조했다.

서력 기원 연수가 4로 나누어 떨어지는 해는 윤년으로 한다.(2004년, 2008년, 2012년, 2016년…)
이 중에서 100으로 나누어 떨어지는 해는 평년으로 한다.(1900년, 2100년, 2200년, 2300년…)
그중에 400으로 나누어 떨어지는 해는 윤년으로 둔다.(1600년, 2000년, 2400년 …)

구조체에 윤년여부와 그 해에 며칠이 있는지를 같이 넣어놓으면 이후에 사용할수 있다. 이를 템플릿 메타프로그래밍으로 표현하면 다음과 같다. 윤년 검증은 static_assert를 이용했다. 앞으로도 이것을 자주 사용할 것이다.

template<int Y>
struct LeapYear {
	enum {
		value = ((Y % 4 == 0) && (Y % 100 != 0)) || (Y % 400 == 0),
		total = value ? 366 : 365
	};
};

// 서력 기원 연수가 4로 나누어 떨어지는 해는 윤년으로 한다.(2004년, 2008년, 2012년, 2016년…)
static_assert(LeapYear<2004>::value == true, "");
static_assert(LeapYear<2008>::value == true, "");
static_assert(LeapYear<2012>::value == true, "");
static_assert(LeapYear<2016>::value == true, "");
// 이 중에서 100으로 나누어 떨어지는 해는 평년으로 한다.(1900년, 2100년, 2200년, 2300년…)
static_assert(LeapYear<1900>::value == false, "");
static_assert(LeapYear<2100>::value == false, "");
static_assert(LeapYear<2200>::value == false, "");
static_assert(LeapYear<2300>::value == false, "");
// 그중에 400으로 나누어 떨어지는 해는 윤년으로 둔다.(1600년, 2000년, 2400년 …)
static_assert(LeapYear<1600>::value == true, "");
static_assert(LeapYear<2000>::value == true, "");
static_assert(LeapYear<2400>::value == true, "");

배열(?) 접근

1월부터 12월까지 각각의 월이 며칠로 구성되는지 배열로 만들어두고 인덱스를 이용해서 접근할수 있으면 5월이 31일로 구성한것을 알 수 있다.

int month_list[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }
int day = month_list[5];

하지만 템플릿 메타프로그래밍에서는 C배열에 접근할수 없다. 그래서 typelist나 Variadic Template를 사용해야한다. 제약조건에 맞춰서 가변인자 템플릿을 사용하기로 했다. 템플릿의 첫번째 인자가 인덱스고 나머지가 배열 역할을 한다.

template<int idx, int I, int... Remainder>
struct ElementAt {
	enum {
		value = ElementAt<idx - 1, Remainder...>::value
	};
};

template<int I, int... Remainder>
struct ElementAt <0, I, Remainder...> {
	enum {
		value = I
	};
};

static_assert(ElementAt<0, 1, 2, 4>::value == 1, "");	//[1, 2, 4][0]
static_assert(ElementAt<1, 1, 2, 4>::value == 2, "");	//[1, 2, 4][1]
static_assert(ElementAt<2, 1, 2, 4>::value == 4, "");	//[1, 2, 4][2]

N월이 며칠로 구성되는가?

인덱스로 접근가능한 배열(?)을 만들었으니 1월부터 12월이 각각 며칠로 구성되는지 알 수 있다. 윤년과 평년 각각에 맞춰서 클래스를 준비한다. 편의상 첫번째 인자를 0으로 두고 13개의 요소를 넣었다. 이렇게 하면 1월을 얻고 싶을때 인덱스 1로 접근하면 된다.

template<int Month>
struct NormalYearDayCount {
	enum {
		value = ElementAt<Month, 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31>::value
	};
};

template<int Month>
struct LeapYearDayCount {
	enum {
		value = ElementAt<Month, 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31>::value
	};
};

static_assert(NormalYearDayCount<2>::value == 28, "");
static_assert(LeapYearDayCount<2>::value == 29, "");

윤년인지 아닌지를 직접 확인하는 것은 불편하다. 클래스안에서 윤년인지 아닌지를 확인할수 있으면 NormalYearDayCount와 LeapYearDayCount를 구분하지 않고 하나로 처리할수 있을 것이다. 이전에 만들어둔 윤년 클래스를 이용하자.

template<int Year, int Month>
struct YearDayCount {
	enum {
		value = LeapYear<Year>::value ? LeapYearDayCount<Month>::value : NormalYearDayCount<Month>::value
	};
};

static_assert(YearDayCount<2015, 2>::value == 28, "");
static_assert(YearDayCount<2016, 2>::value == 29, "");

`YYYY/01/01` ~ `YYYY/MM/DD`

새해의 첫날로부터 며칠이 지나야 특정 날짜가 되는지 확인하는 클래스를 만들어보자. 템플릿 특수화를 사용하면 간단하게 만들수 있다. 사용하는 조건은 다음과 같다.

YYYY/01/01은 0일이다.
YYYY/MM/01은 1월부터 MM-1월까지의 합이다. 예를 들어 2015/04/01은 1,2,3월이 전부다 지났다는 뜻이니까 1,2,3월의 날짜를 전부 더한다. (31 + 28 + 31)
YYYY/MM/DD는 YYYY/MM/01로 부터의 경과일을 센다. 예를 들어 2015/01/11은 2015/01/01로부터 10일이 지났다.

이를 코드로 표현하면 다음과 같다.

template<int Year, int Month, int Day>
struct DayCount {
	enum {
		value = DayCount<Year, Month, 1>::value + Day - 1
	};
};

template<int Year, int Month>
struct DayCount < Year, Month, 1 > {
	enum {
		value = DayCount<Year, Month - 1, 1>::value + YearDayCount<Year, Month - 1>::value
	};
};

template<int Year>
struct DayCount <Year, 1, 1> {
	enum {
		value = 0
	};
};

static_assert(DayCount<2015, 1, 1>::value == 0, "");
static_assert(DayCount<2015, 1, 11>::value == 10, "");

static_assert(DayCount<2015, 2, 1>::value == 31, "");
static_assert(DayCount<2015, 3, 1>::value == 31 + 28, "");
static_assert(DayCount<2015, 4, 1>::value == 31 + 28 + 31, "");

`2000/01/01` ~ `YYYY/01/01`

새해까지의 간격을 계산하는 클래스를 만들자. 윤년인지 아닌지를 확인해서 365 또는 366을 연속으로 더하면된다. 2000/01/01이 토요일이라는 정보를 이용해서 템플릿 특수화를 한다.

template<int Year>
struct YearTotalDay {
	enum {
		value = YearTotalDay<Year - 1>::value + LeapYear<Year - 1>::total
	};
};

template<>
struct YearTotalDay <2000> {
	// 2000/01/01 = SAT
	enum {
		value = DAY_SAT
	};
};

static_assert(YearTotalDay<2000>::value == DAY_SAT, "");
static_assert(YearTotalDay<2001>::value % 7 == DAY_MON, "");
static_assert(YearTotalDay<2002>::value % 7 == DAY_TUE, "");

`YYYY/MM/DD`의 요일

2000/01/01로부터의 경과일을 알면 요일은 간단하게 구할수 있다. 경과일에 mod 7을 하면 된다. 위에서 준비한 클래스를 조합하면 다음과 같다.

template<int Y, int M, int D>
struct Weekday {
	enum {
		start = YearTotalDay<Y>::value % 7,
		month_start = (DayCount<Y, M, 1>::value + start) % 7,
		value = (DayCount<Y, M, D>::value + start) % 7
	};
};

static_assert(Weekday<2001, 1, 1>::value == DAY_MON, "");
static_assert(Weekday<2002, 1, 1>::value == DAY_TUE, "");
static_assert(Weekday<2003, 1, 1>::value == DAY_WED, "");
static_assert(Weekday<2015, 1, 1>::value == DAY_THU, "");

static_assert(Weekday<2015, 1, 1>::month_start == DAY_THU, "");
static_assert(Weekday<2015, 2, 1>::month_start == DAY_SUN, "");
static_assert(Weekday<2015, 3, 1>::month_start == DAY_SUN, "");

static_assert(Weekday<2015, 1, 13>::value == DAY_TUE, "");
static_assert(Weekday<2015, 2, 13>::value == DAY_FRI, "");
static_assert(Weekday<2015, 3, 13>::value == DAY_FRI, "");

`YYYY/01/13` ~ `YYYY/12/13`이 금요일인가?

특정 날짜의 요일을 알수 있으면 금요일인지 비교하는 것은 아주 쉽다. 그러니까 1월부터 12월까지의 13일의 금요일을 확인하는 것을 같이 한다. 13일의 금요일 여부를 확인한 다음 if를 이용해서 재귀호출을 어떻게 할지 결정할수도 있겠지만 제약조건으로 if를 쓰지 않기로 했기 때문에 다른 방법을 이용했다. 제네릭 프로그래밍과 디자인 패턴을 적용한 Modern C++ Design을 보면 int를 type로 바꾸는 편법이 있다. 이것과 오버로딩을 이용했다. YYYY/01/13부터 YYYY/12/13까지 재귀적으로 호출된다. 만약 해당 월의 13일이 금요일이면 vector에 집어넣는다.

template<int v>
struct Int2Type {
	enum { value = v };
};

template<int Year, int Month>
struct EvilYear {
	typedef EvilYear<Year, Month + 1> Next;

	enum {
		Weekday = Weekday<2015, Month, 13>::value,
		value = Weekday == DAY_FRI
	};

	static void run(std::vector<int> &result) {
		run(result, Int2Type<value>());
	}

	static void run(std::vector<int> &result, Int2Type<true>) {
		result.push_back(Month);
		Next::run(result);
	}

	static void run(std::vector<int> &result, Int2Type<false>) {
		Next::run(result);
	}
};

template<int Year>
struct EvilYear<Year, 12> {
	enum {
		Month = 12,
		Weekday = Weekday<2015, Month, 13>::value,
		value = Weekday == DAY_FRI
	};

	static void run(std::vector<int> &result) {
		run(result, Int2Type<value>());
	}

	static void run(std::vector<int> &result, Int2Type<true>) {
		result.push_back(Month);
	}
	static void run(std::vector<int> &result, Int2Type<false>) {
	}
};

실행기

년도만 지정하면 1월을 호출하는 클래스이다. 실제 재귀는 각각의 월에서 알아서 처리한다.

template<int Year>
struct EvilYearRunner {
	typedef EvilYear<Year, 1> Start;
	
	static void run(std::vector<int> &result) {
		Start::run(result);
	}
};

main()

별거 없다. 이전에 만든 실행기에 인자를 2015년으로 지정한 다음에 실행한다. 그리고 실행결과가 올바른지 확인하고 출력한다.

int main()
{
	const int Year = 2015;

	std::vector<int> retval;
	EvilYearRunner<Year>::run(retval);

	if (Year == 2015) {
		assert(retval.size() == 3);
		assert(retval[0] == 2);	// 2015/02/13
		assert(retval[1] == 3);	// 2015/03/13
		assert(retval[2] == 11);	// 2015/11/13
	}

	for (int month : retval) {
		printf("%d ", month);
	}

	getchar();
	return 0;
}

O(1)

코드는 2015년 1월부터 12월까지 총 12번 EvilYear<Year, Month>::run()을 호출한다. 해당 년월의 13일이 금요일인지는 컴파일 시간에 이미 계산되었기 때문에 vector에 월을 집어넣는 작업밖에 수행하지 않는다. 즉, 런타임에서 날짜 계산은 아무것도 하지 않는다. 이것이 C++ Template Metaprogramming의 좋은 점이다.

정리

C++ Template Metaprogramming은 흑마법이라고 불리지만 차근차근 하면 못할 짓은 아니다.
나같은 초보자도 13일의 금요일 정도의 로직은 C++ Template Metaprogramming 정도로 짤 수 있다.
C++ TMP를 이용하면 if/for/while 하나없이 로직을 작성하는 것이 가능하다.
흑마법은 안하는게 정신건강에 좋다.

🡰 Process Address Space

"foo" "bar" == "foobar" 🡲

C++ TMP를 이용해서 2015년의 13일의 금요일 계산하기흑마법의 세계에 어서오세요!

개요