[자료구조] 배열(Array)과 DAT(Direct Access Table)

CS/자료구조

[자료구조] 배열(Array)과 DAT(Direct Access Table)

청월누리 2025. 1. 27. 23:38

배열 (Array)

컴퓨터 과학과 프로그래밍에서 가장 기본적이고 중요한 자료구조 중 하나
효율적인 데이터 관리와 알고리즘 설계의 초석

배열이란

같은 데이터 타입의 값을 연속적인 메모리 공간에 저장하는 자료구조
각 값은 고유한 인덱스를 통해 접근 가능
데이터를 순서대로 저장하고, 빠르게 접근하거나 수정해야 할 때 사용

주요 용어

요소 (element) : 배열에 저장된 개별 데이터
인덱스 (index) : 배열의 각 요소에 접근하기 위한 번호로, 대부분의 프로그래밍 언어에서 0부터 시작
크기 (size) : 배열에 저장할 수 있는 최대 요소의 개수

배열의 예시

인덱스 (index)	0	1	2	3	4
값 (element)	10	20	30	40	50

위와 같이 선언된 배열에서 arr[2]는 값으로 30을 반환

배열의 특징

고정된 크기
- 배열의 크기는 선언 시 지정되며, 이후 변경할 수 없음
- ex) int arr[5]; : 5개의 정수(int)를저장할 수 있는 배열 선언
연속적인 메모리 할당
- 배열의 모든 요소는 메모리에서 연속적으로 저장
- 인덱스 기반 접근이 매우 빠름
같은 데이터 타입
- 배열은 동일한 데이터 타입만 저장 가능
- ex) 정수형 배열은 요소로 정수형 데이터만 저장 가능
빠른 접근 속도
- 인덱스를 통해 $ O(1) $의 시간 복잡도로 요소에 접근 가능

Python에서는 리스트를 사용하여 배열과 유사하게 데이터를 저장할 수 있으며, 서로 다른 데이터 타입도 함께 저장할 수 있다는 특징이 있음
>> C++의 배열은 정적 타입 배열이지만, Python의 리스트는 동적 타입 배열이기 때문에 차이가 발생

배열의 동작 원리

배열 요소 접근

0번 인덱스를 배열이 저장된 메모리의 주소를 시작으로, 데이터 타입의 크기만큼 늘어난 메모리의 주소에 다음 인덱스의 값이 저장되는 형태로 동작

만약, 정수형 배열 arr[5]의 시작 주소가 1000이고 정수형 데이터 타입의 크기가 4byte라면

arr[index]	계산 식	주소
arr[0]	-	1000
arr[1]	$ 1000 + (1 \times 4) $	1004
arr[2]	$ 1000 + (2 \times 4) $	1008

작업에 따른 시간 복잡도

접근 (Access) : $ O(1) $ >> 인덱스를 통한 접근
검색 (Search) : $ O(n) $ >> 순차 탐색
삽입 (Insert) : $ O(n) $ >> 중간에 삽입하는 경우
삭제 (Delete) : $ O(n) $ >> 중간에서 삭제하는 경우

#include <iostream>
using namespace std;

int main() {
    int arr[5] = {10, 20, 30, 40, 50};

    // 배열 요소 출력
    for (int i = 0; i < 5; i++) {
        cout << "arr[" << i << "] = " << arr[i] << endl;
    }

    // 배열 요소 접근
    cout << "3번째 요소: " << arr[2] << endl;

    return 0;
}

배열의 종류

1차원 배열

가장 기본적인 배열 형태로, 선형 데이터 저장

int arr[5] = {10, 20, 30, 40, 50};

2차원 배열

행(row)과 열(column)로 데이터 저장
주로 행렬 데이터를 표현하는 데 사용

int matrix[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

다차원 배열

3차원 이상의 데이터 저장
복잡한 데이터 구조를 표현할 때 사용

int tensor[2][2][3];

배열의 장점과 단점

장점

빠른 데이터 접근 : 인덱스를 통한 $ O(1) $ 시간 복잡도
단순한 구조 : 구현과 사용이 쉽고 직관적
연속적인 메모리 : 캐시 친화적이며 데이터 접근 속도가 빠름

단점

고정된 크기 : 크기를 동적으로 변경할 수 없음
삽입 및 삭제의 비효율 : 중간에 데이터를 삽입하거나 삭제하려면 $ O(n) $의 시간이 소요
메모리 낭비 : 선언한 크기보다 적은 데이터를 저장하면 메모리가 낭비될 수 있음

Direct Access Table (DAT)

컴퓨터 과학에서 특정 키 값을 기반으로 데이터를 효율적으로 저장하고 검색할 수 있는 자료구조

Direct Access Table (DAT) 이란?

키(key)를 인덱스로 변환하여 데이터를 저장하거나 검색하는 방식의 자료구조
해시 테이블(hash table) 방식과 유사하지만, 충돌(collision)이 없는 환경에서 동작

작동 원리

주어진 키(key)를 특정 인덱스(index)로 변환하는 함수를 사용하여 데이터에 접근
데이터는 연속된 메모리 공간에 저장
키 값은 데이터의 위치를 직접 지정하므로 매우 빠른 검색 속도를 제공

DAT의 예시

학생들의 시험 점수를 학생 ID로 관리한다고 가정하면,

학생 ID가 101, 102, 103이라면, 이 ID를 배열의 인덱스로 활용
배열의 크기는 키 값 범위에 따라 고정

int scores[1000] = {0}; // 최대 1000명의 학생 점수를 저장
scores[101] = 95;       // ID 101번 학생의 점수 저장
scores[102] = 88;       // ID 102번 학생의 점수 저장
cout << scores[101];    // ID 101번 학생의 점수 출력 (95)

>> 즉, 저장된 순서를 나타내는 인덱스에 의미를 부여하는 것

DAT의 구조

구성 요소

키 (key) : 데이터 항목을 식별하는 고유한 값 >> 인덱스와 동일
값 (value) : 키와 연결된 데이터
테이블 (table) : 키와 값을 저장하는 배열

인덱스 계산

키를 인덱스로 변환하기 위해 단순한 변환 함수를 사용 >> Offset은 키의 최소값으로 인덱스를 0부터 시작하게 만듦
변환 없이 사용하기도 함

DAT의 특징

빠른 접근 속도
- 키를 인덱스로 바로 변환하므로 $ O(1) $의 시간 복잡도로 접근 가능
연속적인 메모리 사용
- 데이터는 배열 형태로 저장되므로 메모리의 연속성을 가짐
고정된 키 범위
- DAT는 키의 범위가 고정적이고 작은 경우에 적합
충돌 없음
- 해시 테이블과 달리 키 값이 고유하므로 충돌 처리 과정이 필요하지 않음

DAT의 장점과 단점

장점

탐색 속도 : 키를 기반으로 $ O(1) $의 시간 복잡도를 가짐
구현의 간단함: 배열을 활용한 간단한 구조
충돌 처리 불필요 : 고유한 키 값이 보장될 경우 충돌 문제 없음

단점

메모리 낭비 : 키 값 범위에 따라 크기를 미리 할당해야 하므로, 실제 사용보다 큰 메모리가 필요할 수 있음
동적 크기 조정 불가 : 배열의 크기는 고정되어 동적으로 확장 불가
제한된 키 값 범위 : 키 값이 작고 연속적일 때만 효과적

DAT 활용 사례

빈도 카운팅
- ex) 문자열에서 각 문자의 빈도 수를 계산

int freq[26] = {0}; // 알파벳 개수만큼 배열 생성
string text = "hello";

for (char c : text) {
    freq[c - 'a']++; // 문자 'a'를 기준으로 인덱스 계산
}

cout << "빈도 수: " << freq['h' - 'a'] << endl; // 'h'의 빈도 출력

존재 여부 확인
- ex) 특정 숫자가 존재하는지 빠르게 확인

bool exists[1000] = {false};
exists[500] = true; // 500번 데이터가 존재함을 표시

if (exists[500]) {
    cout << "500번 데이터 존재";
}