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

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

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

 

BOJ 2338 : 긴자리 계산 with 10^N진법를 참고하여 36^5진법으로 개선이 가능하다.

아래와 같이 진법 계산을 위해 define을 정의하자. (36 ~ 36^5)

typedef unsigned long long int ull;

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

 

그리고 long type 배열에 5개의 값을 한 번에 넣는다.

	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;
	}

 

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

#if 01 // 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

 

전체 코드는 다음과 같다.

#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진법
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

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;
}

 

이전 보다 속도가 2배 가까이 개선되었다.

반응형

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

타입 캐스팅으로 입력 빨리 받기, 비트 연산으로 메모리 압축하기  (0) 2023.08.26
36진법 긴자리 두 수의 곱셈 with 36^5진법 + Fast Input  (0) 2023.08.26
36진법 긴자리 두 수의 곱셈  (0) 2023.08.26
BOJ 2338 : 긴자리 계산 with 10^N진법  (0) 2023.08.26
긴자리 후위 표기법 구현하기  (0) 2023.08.25

관련글

댓글

티스토리툴바