해시 응용 : 2차원 배열 탐색

삼성 B형 전체 링크

 

참고

- 해시 테이블 Hash Table

- 해시 테이블 추가, 삭제, 수정, 검색

- 해시 응용 - 2차원 배열 탐색

- 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용)

- 해시 테이블 성능 비교

 

아래와 같은 15x15 2차원 배열에서 오른쪽의 4x4 조각이 총 몇 개 있는지 찾아보자.

 

실제 B형 문제라면, 아래의 코드에서 findPiece 함수를 만들면 된다.

#include <stdio.h>

int N = 15;
int M = 4;

char MAP[15][15] =
{
	{ 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, },
	{ 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, },
	{ 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, },
	{ 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, },
	{ 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, },
	{ 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, },
	{ 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, },
	{ 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, },
	{ 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, },
	{ 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, },
	{ 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, },
	{ 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, },
	{ 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, },
	{ 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, },
	{ 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, },
};

char piece1[4][4] =
{
	{ 1, 0, 0, 1, },
	{ 0, 1, 0, 0, },
	{ 0, 0, 1, 0, },
	{ 0, 0, 0, 1, },
};

char piece2[4][4] =
{
	{ 1, 1, 0, 1, },
	{ 0, 0, 1, 0, },
	{ 0, 1, 0, 0, },
	{ 1, 0, 0, 0, },
};

char piece3[4][4] =
{
	{ 1, 0, 0, 0, },
	{ 0, 1, 0, 1, },
	{ 0, 0, 1, 0, },
	{ 0, 1, 0, 0, },
};

///////////////////////// user. cpp /////////////////////////

int findPiece(char MAP[][15], char piece[][4])
{
	/* MAP에서 조각을 찾는 코드를 추가 */
	return 0;
}

/////////////////////////////////////////////////////////////

int main(void)
{
	for (register int tc = 0; tc < 1000000; tc++)
	{
		if (findPiece(MAP, piece1) != 5) printf("wrong!\n");
		if (findPiece(MAP, piece2) != 3) printf("wrong!\n");
		if (findPiece(MAP, piece3) != 3) printf("wrong!\n");
	}

    printf("pass\n");
    
	return 0;
}

---

 각 조각은 5개/3개/3개가 존재한다.

 

findPiece는 각 조각에 대해 5, 3, 3을 return 해야 한다.

---

완전 탐색

 

실제 B형 시험에서도, 완전 탐색은 중요하다.

왜냐하면 time out은 100% 나겠지만,

정답을 맞춰서 자신이 구현하고자 하는 함수가 올바른지 확인하는 과정이 필요하기 때문이다.

(최소 주어지는 tc는 통과하는 지, 보통 점수를 알려준다)

 

완전 탐색은 알고리즘 상관없이 일단 구현만 하면 되기 때문에 30분 ~ 1시간 내에 빠르게 구현해본다.

최적화 따위는 신경 쓰지말자.

 

MAP의 좌표를 넘겨받아서 piece와 모두 같으면 return 1, 하나라도 다르면 return 0를 하도록 만들었다.

///////////////////////// user. cpp /////////////////////////

int compare(char MAP[][15], int sr, int sc, char piece[][4])
{
	for (register int r = 0; r < M; r++)
		for (register int c = 0; c < M; c++)
			if (piece[r][c] != MAP[sr + r][sc + c]) return 0;

	return 1;
}

int findPiece(char MAP[][15], char piece[][4])
{
	int count = 0;
	int boundary = N - M;

	for (register int r = 0; r <= boundary; r++)
		for (register int c = 0; c <= boundary; c++)
			count += compare(MAP, r, c, piece);

	return count;
}

/////////////////////////////////////////////////////////////

 

tc 100만번에 약 3.94초 정도 소요된다.

---

type casting

 

이번에는 type casting을 이용하여 char 4개를 int 1개로 보고 직접 비교하자.

///////////////////////// user. cpp /////////////////////////

typedef unsigned int ui;

int compare(char MAP[][15], int sr, int sc, char piece[][4])
{
	ui cast = 0;

	for (int i = 0; i < 4; i++)
		if (*(ui*)&MAP[sr + i][sc] != *(ui*)&piece[i][0]) return 0;

	return 1;
}

int findPiece(char MAP[][15], char piece[][4])
{
	int count = 0;
	int boundary = N - M;

	for (register int r = 0; r <= boundary; r++)
		for (register int c = 0; c <= boundary; c++)
			count += compare(MAP, r, c, piece);

	return count;
}

/////////////////////////////////////////////////////////////

4x4 모두 비교하는 것과 달리, 4번만 비교하면 되므로, 소요 시간이 많이 줄어들었다.

 

type casting 비교 과정은 아래와 같다.

piece[i][0]	piece[i][0]
&piece[i][0]	piece[i][0]의 주소를
(ui*)&piece[i][0]	piece[i][0]의 주소를 unsigned int로 보겠다.
*(ui*)&piece[i][0]	그리고 그 값을 읽겠다. (*연산자)

어떤 주소값에서 * 연산자를 이용하면 그 주소에 쓰여진 값을 읽는다.

 

따라서 piece[0]이 1, 0, 0, 1인 경우, bit 단위로 볼 때, 0000 0001, 0000 0000, 0000 0000, 0000 0001이 된다.

아래의 printbinary 함수로 실제 메모리와 값을 확인해보자.

char piece1[4][4] =
{
	{ 1, 0, 0, 1, },
	{ 0, 1, 0, 0, },
	{ 0, 0, 1, 0, },
	{ 0, 0, 0, 1, },
};

void printbinary(unsigned int a)
{
	unsigned int mask = 1 << 31;
	for (int i = 0; i < 32;i++)
	{
		printf("%d", (a & mask) == mask);
		mask >>= 1;
		if (i % 4 == 3) printf(" ");
	}
	putchar('\n');
}

int main(void)
{
	printf("%d\n", *(ui*)&piece1[0][0]);
	printbinary(*(ui*)&piece1[0][0]);

	return 0;
}

char 1, 0, 0, 1이 메모리 순서대로 적혀있는 것을 확인할 수 있다.

하지만 piece1의 뒷 부분을 2로 바꿔보자.

char piece1[4][4] =
{
	{ 1, 0, 0, 2, },
	{ 0, 1, 0, 0, },
	{ 0, 0, 1, 0, },
	{ 0, 0, 0, 1, },
};

2가 들어간 부분이 뒤가 아니라 앞부터라는 것을 알 수 있다. (0000 0001 이 아닌 0000 0010)

이것은 endian 변환 때문에 발생하는 것이므로, 간단히 얘기해서 거꾸로 메모리를 읽는다고 생각하면 된다.

자세한 설명은 리틀 엔디안, 빅 엔디안을 검색해보자.

---

hash

 

이제 hash를 이용해서 풀어보자. 보통 B형에서 가장 많이 쓰는 방법이다.

hash 방법은 여러개가 있지만 이 경우에는 unsigned int의 32bit의 16개 bit를 사용하였다.

 

char piece1[4][4] =
{
	{ 1, 0, 0, 1, },
	{ 0, 1, 0, 0, },
	{ 0, 0, 1, 0, },
	{ 0, 0, 0, 1, },
};

piece1의 경우 gethash로 바꾸면 0000 0000 0000 0000 1001 0100 0010 0001 로 변경된다.

 

그리고 MAP의 좌표를 최초 한번 hashMap 배열에 미리 저장해두고, hash 값만 비교하면 속도가 많이 개선된다.

실제 B형에서 init함수가 없는 경우 실행 함수에서 전역 변수를 이용해 한 번만 실행하도록 하는 기법이 자주 쓰인다.

///////////////////////// user. cpp /////////////////////////

typedef unsigned int ui;

ui hashMap[15][15];

#define gethash(arr, r, c) (((ui)arr[r + 0][c + 0] << 15) | (ui)(arr[r + 0][c + 1] << 14) | (ui)(arr[r + 0][c + 2] << 13) | (ui)(arr[r + 0][c + 3] << 12) | \
							((ui)arr[r + 1][c + 0] << 11) | (ui)(arr[r + 1][c + 1] << 10) | (ui)(arr[r + 1][c + 2] << 9)  | (ui)(arr[r + 1][c + 3] << 8)  | \
						    ((ui)arr[r + 2][c + 0] << 7)  | (ui)(arr[r + 2][c + 1] << 6)  | (ui)(arr[r + 2][c + 2] << 5)  | (ui)(arr[r + 2][c + 3] << 4)  | \
						    ((ui)arr[r + 3][c + 0] << 3)  | (ui)(arr[r + 3][c + 1] << 2)  | (ui)(arr[r + 3][c + 2] << 1)  | (ui)(arr[r + 3][c + 3]))

int first = 1;

int findPiece(char MAP[][15], char piece[][4])
{
	if (first)
	{
		int boundary = N - M;
		for (register int r = 0; r <= boundary; r++)
			for (register int c = 0; c <= boundary; c++)
				hashMap[r][c] = gethash(MAP, r, c);

		first = 0;
	}

	int count = 0;
	int boundary = N - M;

	int pieceHash = gethash(piece, 0, 0);

	for (register int r = 0; r <= boundary; r++)
		for (register int c = 0; c <= boundary; c++)
			if (hashMap[r][c] == pieceHash) count++;

	return count;
}

/////////////////////////////////////////////////////////////

0.55초로 가장 빠르게 답을 찾는다.

 

문제에서 조각이 1, 0으로 이루어지기 때문에, 4x4 배열은 중복 없이 unsigned int에 넣을 수 있다.

 

속도 비교는 SW EXPERT ACADEMY 문제에서 실행할 수 있다.

---

3가지 방법으로 문제를 풀어 보았다.

 

B형에서는 아마 3번이 가장 많이 쓰일 것 같다.

하지만 2번의 경우도 필요할 수가 있다.

이번 문제의 경우는 char가 0, 1로만 이루어져 있어서 bit 16개에 넣었지만,

char 2차원 배열의 값이 0~255라면 두 번째 방법이 더 효율적일 수도 있다.