DAT (Direct Access Table) 배열 활용법

개요

DAT란 배열의 인덱스를 "의미 있게" 활용하게 하는 배열 활용법이다.

조회가 잦은 데이터인 경우, DAT 테이블을 만들어서 관리한다.

 

 

장점

중복 반복문의 경우 시간 복잡도는 조회 회수 * 데이터의 개수이다.

DAT의 경우 조회 회수 + 데이터의 개수로 방문해야할 데이터의 개수가 많을 경우 시간복잡도 측에서 큰 차이가 난다.

 

 

활용

존재 유무, counting등에 활용된다. BFS나 DFS를 구현할때 방문 처리를 하는 것도 DAT에 해당된다.

 

정수형 탐색

입력 가능한 정수의 범위 만큼 DAT배열을 초기화 한다, 입력 받은 숫자의 index를 특정 값으로 설정할 경우 해당 숫자가 배열 안에 존재하는지 O(1)의 시간 복잡도로 확인할 수 있다.

만약 Counting이 필요한 케이스의 경우 입력 받은 숫자의 index를 특정 값이 아닌 1씩 증가시킬 경우 해당 숫자가 배열에 몇개 존재하는지 확인할 수 있다.

 

예제 코드

int main() {
	int a = 10;
	int arr[30] = { 42, 16,7,27,99, 8, 13,64,49,15,15,15,15,1,2,3,4,5,6,7,10 };
	int DAT[100] = { 0, };
	for (int i = 0; i < 30; i++) {
		//DAT[arr[i]] = 1; // index : 어떤 숫자 value : 존재한다.
		DAT[arr[i]] += 1; // index : 어떤 숫자 value : 하나 더 존재한다.
	}
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		cout << DAT[num] << "\n";
	}


	/*for (int i = 0; i < 100; i++) {
		cout << i << " : " << DAT[i] << "\n";
	}*/

 

---

문자열 탐색

아스키 코드의 범위 만큼 DAT배열을 초기화, 이후 내용은 정수형 탐색과 상동

 

예제 코드

#include <iostream>

using namespace std;

//DAT = 배열 활용법
int main() {
	char str[10] = "AACDEBBCD";
	int DAT[256] = {0,};
	for (int i = 0; i < 9; i++) {
		DAT[str[i]] += 1;
	}
	for (int i = 65; i < 70; i++) {
		while (DAT[i]--) {
			cout << (char)i;
		}
	}
}