36진법 긴자리 두 수의 곱셈

참고

- 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

앞자리가 0이 아닌 100자리 36진법(0 ~ 9, A ~ Z) 두 수를 곱해보자.

#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
void multiply(char num1[LENGTH_NUMBER], char num2[LENGTH_NUMBER], char result[LENGTH_RESULT])
{
	
}
#endif

int main()
{
	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 < 100; 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;
}

위의 코드에서 multiply를 구현하면 된다.

#if 01
void multiply(char num1[LENGTH_NUMBER], char num2[LENGTH_NUMBER], char result[LENGTH_RESULT])
{
	
}
#endif

구현

긴자리 계산과 같은 방식을 적용하면 이때, 36진법이기 때문에 문자를 숫자로 변환을 할 필요가 있다.

	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;

곱셈을 하기 위해 reverse 배열에 주어진 두 수를 거꾸로 뒤집는다.

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

그리고 change 배열을 이용해 실제 곱셈을 진행한다.

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

마지막으로 자리 올림 처리를 한 후, 배열 뒤에 있는 0을 제외하고 길이를 구한 후, 다시 뒤집는다.

	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;

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

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

전체 코드는 다음과 같다.

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

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

정답은 다음 input 파일을 참고하자.

input.txt

0.19MB

파이썬 - 36진법 곱셈

import random
import string
import time

alpha_num = [
    "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"
]

seed = 55

def pseudo_rand():
  global seed
  seed = seed * 20230827 + 15
  return (seed >> 16) & 0x7fffffff

def make_rand_num():
  rand_num = alpha_num[pseudo_rand() % 35 + 1]
  for i in range(99):
    rand_num += alpha_num[pseudo_rand() % 36]

  return rand_num

def to_base36(num):
  if num == 0:
    return '0'

  base36 = ""
  while num > 0:
    num, remainder = divmod(num, 36)
    if remainder < 10:
      base36 = str(remainder) + base36
    else:
      base36 = chr(ord('A') + remainder - 10) + base36
  return base36

def from_base36(base36_str):
  base36_str = base36_str.upper()
  decimal = 0
  for char in base36_str:
    if char.isdigit():
      decimal = decimal * 36 + int(char)
    else:
      decimal = decimal * 36 + ord(char) - ord('A') + 10
  return decimal

def multiply_base36(a, b):
  decimal_a = from_base36(a)
  decimal_b = from_base36(b)
  result_decimal = decimal_a * decimal_b
  result_base36 = to_base36(result_decimal)
  return result_base36

test_count = 1000

num1 = []
num2 = []

for tc in range(test_count):
  num1.append(make_rand_num())
  num2.append(make_rand_num())

start_time = time.time()

f = open("output.txt", "w")
for tc in range(test_count):
  ans = multiply_base36(num1[tc], num2[tc])
  print(len(ans))
  print(ans)
  f.write(ans)
  f.write('\n')

f.close()

end_time = time.time()

execution_time = end_time - start_time
print(f"실행 시간: {execution_time:.6f} 초")

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

36진법 긴자리 두 수의 곱셈 with 36^5진법 + Fast Input (0)	2023.08.26
36진법 긴자리 두 수의 곱셈 with 36^5진법 (0)	2023.08.26
BOJ 2338 : 긴자리 계산 with 10^N진법 (0)	2023.08.26
긴자리 후위 표기법 구현하기 (0)	2023.08.25
BOJ 5397 : 키로거 with 세그먼트 트리, 링크드 리스트 (0)	2023.08.25

피로물든딸기의 라이브러리

36진법 긴자리 두 수의 곱셈

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

댓글

티스토리툴바

36진법 긴자리 두 수의 곱셈

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

관련글

댓글

티스토리툴바