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

참고

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

카드 4장이 한 세트로 있고 각 카드에 점수가 있다고 가정하자.

카드 : 0 0 0 0 ~ 카드 : 9 9 9 9로 총 10000개의 카드 세트가 존재한다.

그리고 카드 a b c d 의 점수는 abcd (a * 1000 + b * 100 + c * 10 + d)라고 하자.

char card[10000][4];
int answer[10000];

void makeCard()
{
	int count = 0;
	for (int a = 0; a < 10; a++)
		for (int b = 0; b < 10; b++)
			for (int c = 0; c < 10; c++)
				for (int d = 0; d < 10; d++)
				{
					card[count][0] = a;
					card[count][1] = b;
					card[count][2] = c;
					card[count][3] = d;
					answer[count] = count;
					count++;
				}
}

이때, card[10000][4]를 입력 받을 때, score를 구해보자.

makeAnswer 함수를 이용해서 구현해보자.

int TESTCASE = 10000;
clock_t start = clock();

makeAnswer();

int fail = 0;
for (int tc = 0; tc < TESTCASE; tc++)
{
	for (int i = 0; i < 10000; i++)
	{
		//printf("card number : %d %d %d %d\n", card[i][0], card[i][1], card[i][2], card[i][3]);
		int score
			= card[i][0] * 1000 + card[i][1] * 100 + card[i][2] * 10 + card[i][3];

		int check = (score == answer[i]);
		fail += !check;

		//printf(">> score check : %d\n", check);
	}
}

단순히 계산하기

매번 카드 세트마다 score를 아래와 같이 계산해주면 된다.

int score
	= card[i][0] * 1000 + card[i][1] * 100 + card[i][2] * 10 + card[i][3];

전체 코드는 다음과 같다.

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

char card[10000][4];
int answer[10000];

void makeCard()
{
	int count = 0;
	for (int a = 0; a < 10; a++)
		for (int b = 0; b < 10; b++)
			for (int c = 0; c < 10; c++)
				for (int d = 0; d < 10; d++)
				{
					card[count][0] = a;
					card[count][1] = b;
					card[count][2] = c;
					card[count][3] = d;
					answer[count] = count;
					count++;
				}
}

void makeAnswer()
{
  // 생략
}

int main(void)
{
	makeCard();

	/* Timer on */
	int TIME = 0;
	int TESTCASE = 10000;
	clock_t start = clock();

	makeAnswer();

	int fail = 0;
	for (int tc = 0; tc < TESTCASE; tc++)
	{
		for (int i = 0; i < 10000; i++)
		{
			//printf("card number : %d %d %d %d\n", card[i][0], card[i][1], card[i][2], card[i][3]);
			int score 
				= card[i][0] * 1000 + card[i][1] * 100 + card[i][2] * 10 + card[i][3];

			int check = (score == answer[i]);
			fail += !check;

			//printf(">> score check : %d\n", check);
		}
	}

	printf("fail count : %d\n", fail);

	/* Timer off */
	TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

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

	return 0;
}

메모이제이션

문제가 간단하기 때문에 단순히 계산하는 것이 가장 올바른 정답이다.

하지만 만약 score를 구하는 조건이 까다로워서 매번 계산하는데 연산 비용이 많이 드는 경우라면,

memoization으로 답을 적어두는 것이 효율적이다.

현재 테스트를 10000번 하기 때문에 score를 매번 계산하는 것 보다, 저장하는 것이 좋다.

즉, cardScore[10][10][10][10] 배열에 답을 미리 적어둔다.

int cardScore[10][10][10][10];
void makeAnswer()
{
	for (int i = 0; i < 10000; i++)
	{
		cardScore[card[i][0]][card[i][1]][card[i][2]][card[i][3]]
			= card[i][0] * 1000 + card[i][1] * 100 + card[i][2] * 10 + card[i][3];
	}
}

그리고 score에서는 해당 배열에서 값을 호출하면 된다.

int score
	= cardScore[card[i][0]][card[i][1]][card[i][2]][card[i][3]];

또는 아래와 같이 작성할 수 있다.

char* tmp = card[i];
int score
	= cardScore[tmp[0]][tmp[1]][tmp[2]][tmp[3]];

전체 코드는 다음과 같다.

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

char card[10000][4];
int answer[10000];

void makeCard()
{
	int count = 0;
	for (int a = 0; a < 10; a++)
		for (int b = 0; b < 10; b++)
			for (int c = 0; c < 10; c++)
				for (int d = 0; d < 10; d++)
				{
					card[count][0] = a;
					card[count][1] = b;
					card[count][2] = c;
					card[count][3] = d;
					answer[count] = count;
					count++;
				}
}

int cardScore[10][10][10][10];
void makeAnswer()
{
	for (int i = 0; i < 10000; i++)
	{
		cardScore[card[i][0]][card[i][1]][card[i][2]][card[i][3]]
			= card[i][0] * 1000 + card[i][1] * 100 + card[i][2] * 10 + card[i][3];
	}
}

int main(void)
{
	makeCard();

	/* Timer on */
	int TIME = 0;
	int TESTCASE = 10000;
	clock_t start = clock();

	makeAnswer();

	int fail = 0;
	for (int tc = 0; tc < TESTCASE; tc++)
	{
		for (int i = 0; i < 10000; i++)
		{
			//printf("card number : %d %d %d %d\n", card[i][0], card[i][1], card[i][2], card[i][3]);
			int score 
				= cardScore[card[i][0]][card[i][1]][card[i][2]][card[i][3]];

			int check = (score == answer[i]);
			fail += !check;

			//printf(">> score check : %d\n", check);
		}
	}

	printf("fail count : %d\n", fail);

	/* Timer off */
	TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

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

	return 0;
}

타입 캐스팅 + 메모리 압축

36진법 긴자리 두 수의 곱셈 with 36^5진법 + Fast Input에서 사용한 타입 캐스팅을 활용해보자.

아래와 같은 방식은 card[i]에 4번 접근해서 입력을 받는다.

cardScore[card[i][0]][card[i][1]][card[i][2]][card[i][3]]

card가 char 배열로 8바이트씩 읽게 되는데, 이때 int*로 타입 캐스팅하면 char 4개의 배열을 한 번에 읽을 수 있다.

int cast = ((int*)card[i])[0];

printBitNumber 함수를 참고하여 실제로 값을 읽어보자.

template <typename T>
void printBitNumber(T number)
{
	unsigned int bitSize = sizeof(number) * 8;
	T mask = (1ull) << (bitSize - 1);

	printf("%d", (number & mask) == mask);

	mask = (1ull) << (bitSize - 2);
	for (int i = 1; i < bitSize; i++)
	{
		printf("%d", (number & mask) == mask);
		mask >>= 1;
		if (i % 8 == 7) printf(" ");
	}
	putchar('\n');
}

card[10000][4]의 배열을 casting을 이용해 [4]를 한꺼번에 읽는다.

printf("card number : %d %d %d %d\n", card[i][0], card[i][1], card[i][2], card[i][3]);
int cast = ((int*)card[i])[0];
printf("%d\n", cast);
printBitNumber(cast);

예를 들어 9 5 3 8 카드는 아래와 같이 읽힌다. (메모리는 거꾸로 되어 있으므로)

card number : 9 5 3 8
134415625
00001000 00000011 00000101 00001001

그림으로 나타내면 아래와 같다.

카드의 숫자가 9999라면 00001001이 4개 생긴다.

그런데 이 값은 int로 읽었을 때 151587081가 되며 배열을 만들어서 메모리에 저장하기에는 너무 큰 값이다.

하지만 현재 char 배열은 0 ~ 9의 값만 가지기 때문에 아래와 같이 0000 메모리는 낭비되고 있다.

따라서 비트 연산을 이용해 아래와 같이 압축을 할 수 있다.

((cast) | (cast >> 12)) & 0x0000FFFF

이렇게 하면 134,415,625라는 값이 34105로 압축된다.

아래와 같이 코드를 추가해서 확인해 보자.

printf("card number : %d %d %d %d\n", card[i][0], card[i][1], card[i][2], card[i][3]);
int cast = ((int*)card[i])[0];
printf("%d\n", cast);
printBitNumber(cast);

printf("%d\n", (((cast) >> 12) | ((cast))) & 0x0000FFFF);
printBitNumber((((cast) >> 12) | ((cast))) & 0x0000FFFF);

char[4] 9, 5, 3, 8이 34105로 표현이 가능해진다.

card number : 9 5 3 8
134415625
00001000 00000011 00000101 00001001 
34105
00000000 00000000 10000101 00111001

가장 큰 메모리가 9999이고 이 값은 10011001 10011001 = 39321이다.

즉, 메모리를 39321 정도만 사용해서 카드 0000 ~ 9999를 저장할 수 있다.

cardScore에 저장할 때는 9538 → 8359 → 8539 형태로 되므로 아래와 같이 비트 연산으로 저장한다.

int cardScore[39321 + 1];
void makeAnswer()
{
	int max = 0;
	for (int a = 0; a < 10; a++)
		for (int b = 0; b < 10; b++)
			for (int c = 0; c < 10; c++)
				for (int d = 0; d < 10; d++)
				{
					cardScore[(a) | (b << 8) | (c << 4) | (d << 12)] = a * 1000 + b * 100 + c * 10 + d;
				}
}

전체 코드는 다음과 같다.

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

char card[10000][4];
int answer[10000];

void makeCard()
{
	int count = 0;
	for (int a = 0; a < 10; a++)
		for (int b = 0; b < 10; b++)
			for (int c = 0; c < 10; c++)
				for (int d = 0; d < 10; d++)
				{
					card[count][0] = a;
					card[count][1] = b;
					card[count][2] = c;
					card[count][3] = d;
					answer[count] = count;
					count++;
				}
}

template <typename T>
void printBitNumber(T number)
{
	unsigned int bitSize = sizeof(number) * 8;
	T mask = (1ull) << (bitSize - 1);

	printf("%d", (number & mask) == mask);

	mask = (1ull) << (bitSize - 2);
	for (int i = 1; i < bitSize; i++)
	{
		printf("%d", (number & mask) == mask);
		mask >>= 1;
		if (i % 8 == 7) printf(" ");
	}
	putchar('\n');
}

int cardScore[39321 + 1];
void makeAnswer()
{
	int max = 0;
	for (int a = 0; a < 10; a++)
		for (int b = 0; b < 10; b++)
			for (int c = 0; c < 10; c++)
				for (int d = 0; d < 10; d++)
				{
					cardScore[(a) | (b << 8) | (c << 4) | (d << 12)] = a * 1000 + b * 100 + c * 10 + d;
				}
}

int main(void)
{
	makeCard();

	/* Timer on */
	int TIME = 0;
	int TESTCASE = 10000;
	clock_t start = clock();

	makeAnswer();

	int fail = 0;
	for (int tc = 0; tc < TESTCASE; tc++)
	{
		for (int i = 0; i < 10000; i++)
		{
			//printf("card number : %d %d %d %d\n", card[i][0], card[i][1], card[i][2], card[i][3]);
			int cast = ((int*)card[i])[0];
			//printf("%d\n", cast);
			//printBitNumber(cast);

			//printf("%d\n", (((cast) >> 12) | ((cast))) & 0x0000FFFF);
			//printBitNumber((((cast) >> 12) | ((cast))) & 0x0000FFFF);

			int score = cardScore[((cast) | (cast >> 12)) & 0x0000FFFF];

			int check = (score == answer[i]);
			fail += !check;

			//printf(">> score check : %d\n", check);
		}
	}

	printf("fail count : %d\n", fail);

	/* Timer off */
	TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

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

	return 0;
}

위 문제는 단순하기 때문에 3개의 방법 모두 속도 차이가 큰 편은 아니다.

score를 계산하는 방식이 복잡할수록, 캐스팅 + 비트압축 > 메모이제이션 > 단순 계산 순으로 빠르다.

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

비트 압축 - 허프만 알고리즘 (Simple Huffman Coding Algorithm) (0)	2023.09.02
char 타입 배열을 다른 타입의 메모리로 사용하기 (0)	2023.08.26
36진법 긴자리 두 수의 곱셈 with 36^5진법 + Fast Input (0)	2023.08.26
36진법 긴자리 두 수의 곱셈 with 36^5진법 (0)	2023.08.26
36진법 긴자리 두 수의 곱셈 (0)	2023.08.26

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

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

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

댓글

티스토리툴바

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

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

관련글

댓글

티스토리툴바