본문 바로가기
알고리즘/[EXP] 삼성 SW 역량 테스트 C형

36진법 긴자리 두 수의 곱셈 with 36^5진법 + Fast Input

by 피로물든딸기 2023. 8. 26.
반응형

삼성 C형 전체 링크

 

참고

- 타입 캐스팅으로 입력 빨리 받기, 비트 연산으로 메모리 압축하기

 

- BOJ 10757 : 큰 수 A+B
- BOJ 10757 : 큰 수 A+B with 10^N진법
- BOJ 2338 : 긴자리 계산
- BOJ 2338 : 긴자리 계산 with 10^N진법
- 36진법 긴자리 두 수의 곱셈
- 36진법 긴자리 두 수의 곱셈 with 36^5진법
- 36진법 긴자리 두 수의 곱셈 with 36^5진법 + Fast Input

 

아래와 같이 10자리 문자열로 된 숫자가 있다고 가정하자.

char number10[] = "1234567890";

 

이 문자열로 된 숫자를 int로 바꾸려면 for문을 10번 순회해야 한다.

#include <stdio.h>

char number10[] = "1234567890";

int main()
{
	int sum = 0;
	for (int i = 0; i < 10; i++)
	{
		sum *= 10;
		sum += (number10[i] - '0');
	}

	printf("%d\n", sum); // 1234567890

	return 0;
}

 

하지만, 타입 캐스팅을 이용하여 두 번의 처리로 조금 더 빠르게 입력값을 받을 수 있다.

 

number10 배열은 1byte char 타입 배열이지만, 타입 캐스팅을 이용하여 한 번에 8byte 값을 읽을 수 있다.

그리고 8개의 배열을 읽은 후, 5개에 대해서 처리를 하면 두 번만 메모리를 읽어서 10개의 값을 모두 알 수 있다.

 

number10 각 값은 최대 '9'가 될 수 있기 때문에 연속된 메모리 2개의 최대값은 ('9' << 8) + '9' 가 된다.

마찬가지로 3개의 값은 ('9' << 16) + ('9' << 8) + '9') 가 된다.

printf("%d %d\n", ('9' << 8) + '9', ('9' << 16) + ('9' << 8) + '9'); // 14649 3750201

 

위의 배열을 한 번에 읽기 위해 table을 정의하자.

int table2[15000]; // 14649 보다 큰 배열 
int table3[3760000]; // 3750201 보다 큰 배열

 

이제 table2와 table3를 아래와 같이 전처리한다.

'1' '2' 가 적혀있는 메모리라면 table[('2' << 8) + '1' = 12849] = ('2' - '0') * 1 + ('1' - '0') * 10 = 12가 된다.

	for (int i = '0'; i <= '9'; i++)
	{
		for (int k = '0'; k <= '9'; k++)
		{
			table2[(k << 8) + i] = (k - '0') * 1 + (i - '0') * 10;

			for (int t = '0'; t <= '9'; t++)
			{
				table3[(t << 16) + (k << 8) + i]
					= (t - '0') * 100 + (k - '0') * 1000 + (i - '0') * 10000;
			}
		}
	}

 

long으로 type casting을 해서 number10 배열을 8칸을 읽는다.

그리고 메모리의 3칸과 2칸을 나눠서 아래와 같이 계산할 수 있다.

number10 = "1234567890" → tmp = "12345678" → table → 12345 가 된다.

	ull tmp = *(ull*)&number10[0];
	int sum = table3[tmp & 0xFFFFFF] + table2[(tmp >> 24) & 0xFFFF];

	printf("%d\n", sum); // 12345

 

마찬가지로 number10의 5번째 메모리부터 읽으면 67890을 얻을 수 있다.

	ull tmp = *(ull*)&number10[5];
	int sum = table3[tmp & 0xFFFFFF] + table2[(tmp >> 24) & 0xFFFF];

	printf("%d\n", sum); // 67890

 

전체 코드는 다음과 같다.

#include <stdio.h>

typedef unsigned long long int ull;

char number10[] = "1234567890";

int table2[15000];
int table3[3760000];

int main()
{
	printf("%d %d\n", ('9' << 8) + '9', ('9' << 16) + ('9' << 8) + '9');

	for (int i = '0'; i <= '9'; i++)
	{
		for (int k = '0'; k <= '9'; k++)
		{
			//printf("%d %d %d\n", i, k, (k << 8) + i);

			table2[(k << 8) + i] = (k - '0') * 1 + (i - '0') * 10;

			for (int t = '0'; t <= '9'; t++)
			{
				//printf("%d %d %d %d\n", i, k, t, (t << 16) + (k << 8) + i);

				table3[(t << 16) + (k << 8) + i]
					= (t - '0') * 100 + (k - '0') * 1000 + (i - '0') * 10000;
			}
		}
	}

	{
		ull tmp = *(ull*)&number10[0];
		int sum = table3[tmp & 0xFFFFFF] + table2[(tmp >> 24) & 0xFFFF];

		printf("%d\n", sum); // 12345
	}

	{
		ull tmp = *(ull*)&number10[5];
		int sum = table3[tmp & 0xFFFFFF] + table2[(tmp >> 24) & 0xFFFF];

		printf("%d\n", sum); // 67890
	}


	return 0;
}

36진법으로 확장하기

 

36진법 곱셈의 경우는 다음과 같이 table을 이용하여 숫자를 먼저 변경한다.

또한 긴자리 곱셈을 할 때 거꾸로 값이 들어가는 것을 고려하였다.

 

예를 들어 ABCDE01000는 실제로 EDCBA = 24137110 / 00010 = 10 = 36이 된다.

 

또한 최대 'Z'까지 사용하므로 테이블의 배열 크기가 아래와 같이 변경된다.

ull table2[23300];
ull table3[5921370 + 100];

 

아래 테스트 코드를 참고하자.

#include <stdio.h>

typedef unsigned long long int ull;

#define ONE36 (36)
#define TWO36 (36 * 36)
#define THREE36 (36 * 36 * 36)
#define FOUR36 (36 * 36 * 36 * 36)
#define FIVE36 (36 * 36 * 36 * 36 * 36)


char number36[] = "ABCDE01000";

ull table2[23300];
ull table3[5921370 + 100];

int main()
{
	ull a = ('Z' << 8) + 'Z';
	ull b = ('Z' << 16) + ('Z' << 8) + 'Z';

	printf("%lld %lld\n", a, b);

	int change['Z' + 1] = { 0 };
	int change36[36] = { 0 };

	for (int i = '0'; i <= '9'; i++) change[i] = i - '0';
	for (int i = 'A'; i <= 'Z'; i++) change[i] = i - 'A' + 10;

	for (int i = 0; i <= 9; i++) change36[i] = '0' + i;
	for (int i = 10; i <= 35; i++) change36[i] = 'A' + i - 10;


	for (int i = 0; i < 36; i++)
	{
		for (int k = 0; k < 36; k++)
		{
			int a = change36[i];
			int b = change36[k];

			table2[(b << 8) + a] = change[a] * THREE36 + change[b] * FOUR36;

			for (int t = 0; t < 36; t++)
			{
				int c = change36[t];
				table3[(c << 16) + (b << 8) + a] = change[a] + change[b] * ONE36 + change[c] * TWO36;
			}
		}
	}

	{
		ull tmp = *(ull*)&number36[0];
		ull sum = table3[tmp & 0xFFFFFF] + table2[(tmp >> 24) & 0xFFFF];

		printf("%llu\n", sum);
		
		ull compare
			= change[number36[0]] * 1
			+ change[number36[1]] * 36
			+ change[number36[2]] * TWO36
			+ change[number36[3]] * THREE36
			+ change[number36[4]] * FOUR36;
		printf(">> %llu\n", compare);
	}

	{
		ull tmp = *(ull*)&number36[5];
		ull sum = table3[tmp & 0xFFFFFF] + table2[(tmp >> 24) & 0xFFFF];

		printf("%llu\n", sum);

		ull compare
			= change[number36[5]] * 1
			+ change[number36[6]] * 36
			+ change[number36[7]] * TWO36
			+ change[number36[8]] * THREE36
			+ change[number36[9]] * FOUR36;
		printf(">> %llu\n", compare);
	}


	return 0;
}

곱셈에 적용하기

 

매번 곱셈을 할 때마다 table2, 3을 만들 필요가 없기 때문에 전역 변수(first)를 두고 한 번만 처리하도록 한다.

ull table2[23300];
ull table3[5921370 + 100];
int first = 1;

void multiply(char num1[LENGTH_NUMBER], char num2[LENGTH_NUMBER], char result[LENGTH_RESULT])
{
	char change['Z' + 1] = { 0 };
	char recover['Z' + 1] = { 0 };

	for (int i = '0'; i <= '9'; i++) change[i] = i - '0';
	for (int i = 'A'; i <= 'Z'; i++) change[i] = i - 'A' + 10;

	for (int i = 0; i <= 9; i++) recover[i] = i + '0';
	for (int i = 10; i <= 35; i++) recover[i] = 'A' - 10 + i;

	if (first)
	{
		first = 0;
		for (int i = 0; i < 36; i++)
		{
			for (int k = 0; k < 36; k++)
			{
				int a = recover[i];
				int b = recover[k];

				table2[(b << 8) + a] = change[a] * THR + change[b] * FOU;

				for (int t = 0; t < 36; t++)
				{
					int c = recover[t];
					table3[(c << 16) + (b << 8) + a] = change[a] + change[b] * ONE + change[c] * TWO;
				}
			}
		}
	}
    
	...

 

이제 아래의 코드를 Fast Input으로 처리하면 된다.

	register ull lnum1[20 + 1] = { 0 };
	register ull lnum2[20 + 1] = { 0 };
	register ull ltemp3[40 + 1] = { 0 };

	int lcnt = 0;
	for (int i = 0; i < 100; i += 5)
	{
		lnum1[lcnt]
			= change[rev1[i + 0]] * 1
			+ change[rev1[i + 1]] * ONE
			+ change[rev1[i + 2]] * TWO
			+ change[rev1[i + 3]] * THR
			+ change[rev1[i + 4]] * FOU;

		lnum2[lcnt]
			= change[rev2[i + 0]] * 1
			+ change[rev2[i + 1]] * ONE
			+ change[rev2[i + 2]] * TWO
			+ change[rev2[i + 3]] * THR
			+ change[rev2[i + 4]] * FOU;

		lcnt++;
	}

 

개선한 코드는 아래와 같다.

	register ull lnum1[20 + 1] = { 0 };
	register ull lnum2[20 + 1] = { 0 };
	register ull ltemp3[40 + 1] = { 0 };

	int lcnt = 0;
	for (int i = 0; i < 100; i += 5)
	{
		ull fastRev1= *(ull*)&rev1[i];
		ull fastRev2 = *(ull*)&rev2[i];
        
		lnum1[lcnt]
			= table3[fastRev1 & 0xFFFFFF] + table2[(fastRev1 >> 24) & 0xFFFF];

		lnum2[lcnt]
			= table3[fastRev2 & 0xFFFFFF] + table2[(fastRev2 >> 24) & 0xFFFF];

		lcnt++;
	}

 

36^5진법 긴자리 곱셈 + Fast Input의 구현은 아래와 같다.

#if 01 // 36^5진법 + fast input
typedef unsigned long long int ull;

#define ONE (36ull)
#define TWO (1296ull)
#define THR (46656ull)
#define FOU (1679616ull)
#define FIV (60466176ull)

ull table2[23300];
ull table3[5921370 + 100];
int first = 1;

void multiply(char num1[LENGTH_NUMBER], char num2[LENGTH_NUMBER], char result[LENGTH_RESULT])
{
	char change['Z' + 1] = { 0 };
	char recover['Z' + 1] = { 0 };

	for (int i = '0'; i <= '9'; i++) change[i] = i - '0';
	for (int i = 'A'; i <= 'Z'; i++) change[i] = i - 'A' + 10;

	for (int i = 0; i <= 9; i++) recover[i] = i + '0';
	for (int i = 10; i <= 35; i++) recover[i] = 'A' - 10 + i;

	if (first)
	{
		first = 0;
		for (int i = 0; i < 36; i++)
		{
			for (int k = 0; k < 36; k++)
			{
				int a = recover[i];
				int b = recover[k];

				table2[(b << 8) + a] = change[a] * THR + change[b] * FOU;

				for (int t = 0; t < 36; t++)
				{
					int c = recover[t];
					table3[(c << 16) + (b << 8) + a] = change[a] + change[b] * ONE + change[c] * TWO;
				}
			}
		}
	}

	int temp[LENGTH_RESULT] = { 0 };

	char rev1[LENGTH_NUMBER] = { 0 };
	char rev2[LENGTH_NUMBER] = { 0 };

	int numLen = LENGTH_NUMBER - 1;
	for (int i = 0; i < numLen; i++) rev1[numLen - 1 - i] = num1[i];
	for (int i = 0; i < numLen; i++) rev2[numLen - 1 - i] = num2[i];

	register ull lnum1[20 + 1] = { 0 };
	register ull lnum2[20 + 1] = { 0 };
	register ull ltemp3[40 + 1] = { 0 };

	int lcnt = 0;
	for (int i = 0; i < 100; i += 5)
	{
		ull fastRev1= *(ull*)&rev1[i];
		ull fastRev2 = *(ull*)&rev2[i];
        
		lnum1[lcnt]
			= table3[fastRev1 & 0xFFFFFF] + table2[(fastRev1 >> 24) & 0xFFFF];

		lnum2[lcnt]
			= table3[fastRev2 & 0xFFFFFF] + table2[(fastRev2 >> 24) & 0xFFFF];

		lcnt++;
	}

	lcnt++;
	for (int i = 0; i < lcnt; i++)
		for (int k = 0; k < lcnt; k++)
			ltemp3[i + k] += lnum1[i] * lnum2[k];

	int len = lcnt * 2 - 2;
	for (int i = 0; i < len; i++)
	{
		ltemp3[i + 1] += (ltemp3[i] / FIV);
		ltemp3[i] %= FIV;
	}

	while (len && ltemp3[len] == 0) len--;
	len++;

	int ansLen = 0;
	for (int i = 0; i < len; i++)
	{
		ull value = ltemp3[i];

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;
	}

	while (ansLen && temp[ansLen] == 0) ansLen--;
	ansLen++;

	for (int i = 0; i < ansLen; i++) result[ansLen - 1 - i] = recover[temp[i]];
	result[ansLen] = 0;
}
#endif

 

전체 코드는 다음과 같다.

#pragma warning(disable:4996)

#include <stdio.h>
#include <time.h>

#define LENGTH_NUMBER (100 + 1)
#define LENGTH_OPERANDS (100 + 1)
#define LENGTH_RESULT (200 + 2)
#define TC_COUNT (1000)

char alphaNum[36] = 
{
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E',
	'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
	'U', 'V', 'W', 'X', 'Y', 'Z'
};

static unsigned long long seed = 55L;

static inline int pseudo_rand()
{
	seed = seed * 20230827ULL + 15ULL;
	return (seed >> 16) & 0x7fffffff;
}

void makeRandNum(char number[LENGTH_NUMBER])
{
	char randNum = alphaNum[pseudo_rand() % 35 + 1];
	number[0] = randNum;
	for (int i = 1; i < 100; i++)  number[i] = alphaNum[pseudo_rand() % 36];
	
	number[100] = 0;
}

int mystrcmp(const char *a, const char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

char number1[TC_COUNT][LENGTH_NUMBER];
char number2[TC_COUNT][LENGTH_NUMBER];

char result[TC_COUNT][LENGTH_RESULT];
char answer[TC_COUNT][LENGTH_RESULT];

#if 01 // 36^5진법 + fast input
typedef unsigned long long int ull;

#define ONE (36ull)
#define TWO (1296ull)
#define THR (46656ull)
#define FOU (1679616ull)
#define FIV (60466176ull)

ull table2[23300];
ull table3[5921370 + 100];
int first = 1;

void multiply(char num1[LENGTH_NUMBER], char num2[LENGTH_NUMBER], char result[LENGTH_RESULT])
{
	char change['Z' + 1] = { 0 };
	char recover['Z' + 1] = { 0 };

	for (int i = '0'; i <= '9'; i++) change[i] = i - '0';
	for (int i = 'A'; i <= 'Z'; i++) change[i] = i - 'A' + 10;

	for (int i = 0; i <= 9; i++) recover[i] = i + '0';
	for (int i = 10; i <= 35; i++) recover[i] = 'A' - 10 + i;

	if (first)
	{
		first = 0;
		for (int i = 0; i < 36; i++)
		{
			for (int k = 0; k < 36; k++)
			{
				int a = recover[i];
				int b = recover[k];

				table2[(b << 8) + a] = change[a] * THR + change[b] * FOU;

				for (int t = 0; t < 36; t++)
				{
					int c = recover[t];
					table3[(c << 16) + (b << 8) + a] = change[a] + change[b] * ONE + change[c] * TWO;
				}
			}
		}
	}

	int temp[LENGTH_RESULT] = { 0 };

	char rev1[LENGTH_NUMBER] = { 0 };
	char rev2[LENGTH_NUMBER] = { 0 };

	int numLen = LENGTH_NUMBER - 1;
	for (int i = 0; i < numLen; i++) rev1[numLen - 1 - i] = num1[i];
	for (int i = 0; i < numLen; i++) rev2[numLen - 1 - i] = num2[i];

	register ull lnum1[20 + 1] = { 0 };
	register ull lnum2[20 + 1] = { 0 };
	register ull ltemp3[40 + 1] = { 0 };

	int lcnt = 0;
	for (int i = 0; i < 100; i += 5)
	{
		ull fastRev1= *(ull*)&rev1[i];
		ull fastRev2 = *(ull*)&rev2[i];
        
		lnum1[lcnt]
			= table3[fastRev1 & 0xFFFFFF] + table2[(fastRev1 >> 24) & 0xFFFF];

		lnum2[lcnt]
			= table3[fastRev2 & 0xFFFFFF] + table2[(fastRev2 >> 24) & 0xFFFF];

		lcnt++;
	}

	lcnt++;
	for (int i = 0; i < lcnt; i++)
		for (int k = 0; k < lcnt; k++)
			ltemp3[i + k] += lnum1[i] * lnum2[k];

	int len = lcnt * 2 - 2;
	for (int i = 0; i < len; i++)
	{
		ltemp3[i + 1] += (ltemp3[i] / FIV);
		ltemp3[i] %= FIV;
	}

	while (len && ltemp3[len] == 0) len--;
	len++;

	int ansLen = 0;
	for (int i = 0; i < len; i++)
	{
		ull value = ltemp3[i];

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;
	}

	while (ansLen && temp[ansLen] == 0) ansLen--;
	ansLen++;

	for (int i = 0; i < ansLen; i++) result[ansLen - 1 - i] = recover[temp[i]];
	result[ansLen] = 0;
}
#endif

int main()
{
	freopen("input.txt", "r", stdin);
	for (int tc = 0; tc < TC_COUNT; tc++)
	{
		scanf("%s", answer[tc]);
		makeRandNum(number1[tc]);
		makeRandNum(number2[tc]);
	}

	int TIME = 0;
	clock_t start = clock();
	for (int repeat = 0; repeat < 1000; repeat++)
	{
		for (int tc = 0; tc < TC_COUNT; tc++)
		{
			multiply(number1[tc], number2[tc], result[tc]);
			if (mystrcmp(result[tc], answer[tc]))
			{
				printf("FAIL!!\n");
				break;
			}
		}
	}
	
	TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

	printf("TIME : %d ms\n", TIME); /* ms 단위로 출력 */

	return 0;
}

 

이전 보다 속도가 아주 조금 더 개선되었다.

속도 비교

 

참고로 Release 모드에서 속도를 비교하였다.

 

Release 모드에서는 scanf 경고가 나타나기 때문에 경고를 무시하도록 선언한다.

#pragma warning(disable:4996)

 

36진법 / 36^5진법 / 36^5진법 + Fast Input 의 속도는 아래와 같다.

 

전체 코드는 다음과 같다.

#pragma warning(disable:4996)

#include <stdio.h>
#include <time.h>

#define LENGTH_NUMBER (100 + 1)
#define LENGTH_OPERANDS (100 + 1)
#define LENGTH_RESULT (200 + 2)
#define TC_COUNT (1000)

char alphaNum[36] = 
{
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E',
	'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
	'U', 'V', 'W', 'X', 'Y', 'Z'
};

static unsigned long long seed = 55L;

static inline int pseudo_rand()
{
	seed = seed * 20230827ULL + 15ULL;
	return (seed >> 16) & 0x7fffffff;
}

void makeRandNum(char number[LENGTH_NUMBER])
{
	char randNum = alphaNum[pseudo_rand() % 35 + 1];
	number[0] = randNum;
	for (int i = 1; i < 100; i++)  number[i] = alphaNum[pseudo_rand() % 36];
	
	number[100] = 0;
}

int mystrcmp(const char *a, const char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

char number1[TC_COUNT][LENGTH_NUMBER];
char number2[TC_COUNT][LENGTH_NUMBER];

char result[TC_COUNT][LENGTH_RESULT];
char answer[TC_COUNT][LENGTH_RESULT];

#if 0 // 36진법 
void multiply(char num1[LENGTH_NUMBER], char num2[LENGTH_NUMBER], char result[LENGTH_RESULT])
{
	char change['Z' + 1] = { 0 };
	char recover['Z' + 1] = { 0 };

	for (int i = '0'; i <= '9'; i++) change[i] = i - '0';
	for (int i = 'A'; i <= 'Z'; i++) change[i] = i - 'A' + 10;

	for (int i = 0; i <= 9; i++) recover[i] = i + '0';
	for (int i = 10; i <= 35; i++) recover[i] = 'A' - 10 + i;

	int temp[LENGTH_RESULT] = { 0 };

	char rev1[LENGTH_NUMBER] = { 0 };
	char rev2[LENGTH_NUMBER] = { 0 };

	int numLen = LENGTH_NUMBER - 1;
	for (int i = 0; i < numLen; i++) rev1[numLen - 1 - i] = num1[i];
	for (int i = 0; i < numLen; i++) rev2[numLen - 1 - i] = num2[i];

	int len1, len2, len;

	len1 = len2 = numLen;
	for (int i = 0; i < len1; i++)
		for (int k = 0; k < len2; k++)
			temp[i + k] += change[rev1[i]] * change[rev2[k]];

	len = len1 + len2 + 1;

	for (int i = 0; i < len; i++)
	{
		temp[i + 1] += (temp[i] / 36);
		temp[i] %= 36;
	}

	while (len && temp[len] == 0) len--;
	len++;

	for (int i = 0; i < len; i++) result[len - 1 - i] = recover[temp[i]];
	result[len] = 0;
}
#endif

#if 0 // 36^5진법
typedef unsigned long long int ull;

#define ONE (36ull)
#define TWO (1296ull)
#define THR (46656ull)
#define FOU (1679616ull)
#define FIV (60466176ull)

void multiply(char num1[LENGTH_NUMBER], char num2[LENGTH_NUMBER], char result[LENGTH_RESULT])
{
	char change['Z' + 1] = { 0 };
	char recover['Z' + 1] = { 0 };

	for (int i = '0'; i <= '9'; i++) change[i] = i - '0';
	for (int i = 'A'; i <= 'Z'; i++) change[i] = i - 'A' + 10;

	for (int i = 0; i <= 9; i++) recover[i] = i + '0';
	for (int i = 10; i <= 35; i++) recover[i] = 'A' - 10 + i;

	int temp[LENGTH_RESULT] = { 0 };

	char rev1[LENGTH_NUMBER] = { 0 };
	char rev2[LENGTH_NUMBER] = { 0 };

	int numLen = LENGTH_NUMBER - 1;
	for (int i = 0; i < numLen; i++) rev1[numLen - 1 - i] = num1[i];
	for (int i = 0; i < numLen; i++) rev2[numLen - 1 - i] = num2[i];

	register ull lnum1[20 + 1] = { 0 };
	register ull lnum2[20 + 1] = { 0 };
	register ull ltemp3[40 + 1] = { 0 };

	int lcnt = 0;
	for (int i = 0; i < 100; i += 5)
	{
		lnum1[lcnt]
			= change[rev1[i + 0]] * 1
			+ change[rev1[i + 1]] * ONE
			+ change[rev1[i + 2]] * TWO
			+ change[rev1[i + 3]] * THR
			+ change[rev1[i + 4]] * FOU;

		lnum2[lcnt]
			= change[rev2[i + 0]] * 1
			+ change[rev2[i + 1]] * ONE
			+ change[rev2[i + 2]] * TWO
			+ change[rev2[i + 3]] * THR
			+ change[rev2[i + 4]] * FOU;

		lcnt++;
	}

	lcnt++;
	for (int i = 0; i < lcnt; i++)
		for (int k = 0; k < lcnt; k++)
			ltemp3[i + k] += lnum1[i] * lnum2[k];

	int len = lcnt * 2 - 2;
	for (int i = 0; i < len; i++)
	{
		ltemp3[i + 1] += (ltemp3[i] / FIV);
		ltemp3[i] %= FIV;
	}

	while (len && ltemp3[len] == 0) len--;
	len++;

	int ansLen = 0;
	for (int i = 0; i < len; i++)
	{
		ull value = ltemp3[i];

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;
	}

	while (ansLen && temp[ansLen] == 0) ansLen--;
	ansLen++;

	for (int i = 0; i < ansLen; i++) result[ansLen - 1 - i] = recover[temp[i]];
	result[ansLen] = 0;
}
#endif

#if 01 // 36^5진법 + fast input
typedef unsigned long long int ull;

#define ONE (36ull)
#define TWO (1296ull)
#define THR (46656ull)
#define FOU (1679616ull)
#define FIV (60466176ull)

ull table2[23300];
ull table3[5921370 + 100];
int first = 1;

void multiply(char num1[LENGTH_NUMBER], char num2[LENGTH_NUMBER], char result[LENGTH_RESULT])
{
	char change['Z' + 1] = { 0 };
	char recover['Z' + 1] = { 0 };

	for (int i = '0'; i <= '9'; i++) change[i] = i - '0';
	for (int i = 'A'; i <= 'Z'; i++) change[i] = i - 'A' + 10;

	for (int i = 0; i <= 9; i++) recover[i] = i + '0';
	for (int i = 10; i <= 35; i++) recover[i] = 'A' - 10 + i;

	if (first)
	{
		first = 0;
		for (int i = 0; i < 36; i++)
		{
			for (int k = 0; k < 36; k++)
			{
				int a = recover[i];
				int b = recover[k];

				table2[(b << 8) + a] = change[a] * THR + change[b] * FOU;

				for (int t = 0; t < 36; t++)
				{
					int c = recover[t];
					table3[(c << 16) + (b << 8) + a] = change[a] + change[b] * ONE + change[c] * TWO;
				}
			}
		}
	}

	int temp[LENGTH_RESULT] = { 0 };

	char rev1[LENGTH_NUMBER] = { 0 };
	char rev2[LENGTH_NUMBER] = { 0 };

	int numLen = LENGTH_NUMBER - 1;
	for (int i = 0; i < numLen; i++) rev1[numLen - 1 - i] = num1[i];
	for (int i = 0; i < numLen; i++) rev2[numLen - 1 - i] = num2[i];

	register ull lnum1[20 + 1] = { 0 };
	register ull lnum2[20 + 1] = { 0 };
	register ull ltemp3[40 + 1] = { 0 };

	int lcnt = 0;
	for (int i = 0; i < 100; i += 5)
	{
		ull fastRev1= *(ull*)&rev1[i];
		ull fastRev2 = *(ull*)&rev2[i];
        
		lnum1[lcnt]
			= table3[fastRev1 & 0xFFFFFF] + table2[(fastRev1 >> 24) & 0xFFFF];

		lnum2[lcnt]
			= table3[fastRev2 & 0xFFFFFF] + table2[(fastRev2 >> 24) & 0xFFFF];

		lcnt++;
	}

	lcnt++;
	for (int i = 0; i < lcnt; i++)
		for (int k = 0; k < lcnt; k++)
			ltemp3[i + k] += lnum1[i] * lnum2[k];

	int len = lcnt * 2 - 2;
	for (int i = 0; i < len; i++)
	{
		ltemp3[i + 1] += (ltemp3[i] / FIV);
		ltemp3[i] %= FIV;
	}

	while (len && ltemp3[len] == 0) len--;
	len++;

	int ansLen = 0;
	for (int i = 0; i < len; i++)
	{
		ull value = ltemp3[i];

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;

		temp[ansLen++] = value % 36;
		value /= 36;
	}

	while (ansLen && temp[ansLen] == 0) ansLen--;
	ansLen++;

	for (int i = 0; i < ansLen; i++) result[ansLen - 1 - i] = recover[temp[i]];
	result[ansLen] = 0;
}
#endif

int main()
{
	freopen("input.txt", "r", stdin);
	for (int tc = 0; tc < TC_COUNT; tc++)
	{
		scanf("%s", answer[tc]);
		makeRandNum(number1[tc]);
		makeRandNum(number2[tc]);
	}

	int TIME = 0;
	clock_t start = clock();
	for (int repeat = 0; repeat < 1000; repeat++)
	{
		for (int tc = 0; tc < TC_COUNT; tc++)
		{
			multiply(number1[tc], number2[tc], result[tc]);
			if (mystrcmp(result[tc], answer[tc]))
			{
				printf("FAIL!!\n");
				break;
			}
		}
	}
	
	TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

	printf("TIME : %d ms\n", TIME); /* ms 단위로 출력 */

	return 0;
}
반응형

'알고리즘 > [EXP] 삼성 SW 역량 테스트 C형' 카테고리의 다른 글

char 타입 배열을 다른 타입의 메모리로 사용하기  (0) 2023.08.26
타입 캐스팅으로 입력 빨리 받기, 비트 연산으로 메모리 압축하기  (0) 2023.08.26
36진법 긴자리 두 수의 곱셈 with 36^5진법  (0) 2023.08.26
36진법 긴자리 두 수의 곱셈  (0) 2023.08.26
BOJ 2338 : 긴자리 계산 with 10^N진법  (0) 2023.08.26

관련글

댓글

티스토리툴바