[자료구조] 2강 - 배열

✅ 1. 배열의 정의

• 일정한 차례나 간격에 따라 벌여 놓음
• 차례(순서)와 관련된 기본적인 자료구조이다.
• 원소의 메모리 공간(메인 메모리, DDR)의 물리적인 위치를 순서적으로 결정하는 특징이 있다.
• 배열의 순서는 메모리 공간에서 저장되는 원소값의 물리적 순서와 같다.
• 인덱스와 원소값( indext, value ) 의 쌍으로 이루어져 있음.

(1) 배열의 의미

• 인덱스로 표현되는 순서를 갖는 특정 배열이 존재하며, 그곳에는 순서대로 원소가 들어가게 된다.
• 원소들이 모두 같은 자료형과 같은 크기의 기억 공간을 가지게 된다.
• 배열의 인덱스값을 이용해서 원소값에 접근하기 때문에 직접 접근이 가능함

[ 배열의 인덱스 값 ]

• 컴퓨터의 내구구조나 메모리 주소와 무관하게 개발자에게 개념적으로 정의되는 추상화된 값이다.
• 메모리 주소값은 실제 메모리의 물리적인 위치값을 의미함.
• 배열의(추상화된) 인덱스값은 프로그래밍 언어와 컴파일 과정을 통해 메모리 주소값과 연결이 됨.
• 즉, 프로그램 실행과 동시에 운영체제가 사용되지 않는 메모리 공간을 초기화해서 주소값과 데이터를 할당해줌.

• 인덱스는 추상화된 개념이고, 주소값은 그 추상화를 구현한 실제 하드웨어 메모리 측면의 주소값인 것이다.
• 사실은 구현한 메모리 주소값 또한 운영체제가 할당해주는 값이지 실제 메모리는 그냥 셀로만 이루어져 있음.

---

✅ 2. 배열의 추상 자료형

(1) 추상자료형

• 객체 및 관련된 연산의 정의로 구성됨.
• 자료구조 구현전의 설계 단계
• 자료의 추상화 결과를 수학적으로 정의 내린것이 추상자료형이다.
• 이후 이 추상자료형을 구현하면 자료구조가 되는것임.

(2) 자료형

• 메모리 저장 할당을 위한 변수 선언
• 즉, 변수가 메모리를 할당 받기 위해서 필요되는 공간을 정의하는것이 자료형이라고 함.
• 자료구조의 구현 단계(프로그래밍 언어를 이용한 선언)에서도 자료형이 선언이 됨.

(3) ADT Array 객체: <i index, e Element> 쌍들의 집합

• Index: 순서를 나타내는 원소의 유한집합
• Element: 자료형이 같은 원소의 집합

• (1) create: 배열을 생성해내는 연산
• (2) retrieve: 값 찾기
• (3) store: 원하는 위치에 값 저장
• 이것이 수학적으로 만들어진 추상자료형 즉, 설계가 될 수 있음.

(4) 정리

• 기본자료형은 기본적으로 제공해주는 자료형이고, 추상자료형은 내가 임의로 만들 수 있는 느낌
• 즉, 객체 또한 추상자료형 범주 안에 들어간다고 보는게 맞는 것 같음.
• 결론은 자바에서 구현 된 자료구조는 결국 추상자료형을 객체로 구현한 것으로 볼 수 있다.

---

✅ 3. 배열연산의 구현

(1) 배열의 생성

void create(int n) { // n = 5
    int a[n];
    int i;
    for(i=0, i<n, i++){
        a[i] = 0;
    }
}

int a[3]; // 개발자가 호출하면 create() 가 호출이 된다.

• 해당 구현으로 배열을 만들게 되면, 메모리 공간에 정수로 이루어진 배열이 만들어지고 내부에서는 3개의 공간이 할당됨.
• 해당 create() 함수를 내부적으로 호출 한다고 생각하면 된다. 하지만 C 언어에서는 함수 호출은 안하고 있음.

(2) 배열값의 검색(retrieve 연산)

#define array_size 5
int retrieve(int *a, int i) {
    if(i >= 0 && i < array_size )
        return a[i];
    else { 
        printf("Erro\n";
        return(-1);
    }
}

K = a[2]; // 2번째의 값을 반환

• a[2] 를 하면 내부적으로 retrieve() 호출로 2번째의 배열의 값을 반환 받을 수 있다. ( 컴파일러가 해줌 C는 함수 없음 )

(3) 배열값의 저장(store 연산)

#define array_size 5
void store(int *a, int i, int e) { // i = 3, e =35
    if(i >= 0 && < array_size) {
        a[i] = e;
    } else {
        printf("Error\n");
    }
}

a[3] = 3; // 저장 내부적으로 함수 호출 ( C는 아님 )

• a[3] = 3; store() 함수가 호출이 되며 3번째 인덱스의 원소값인 3을 넣을 수 있게 된다.

(4) 정리

• 추상자료형을 기반으로 실제 프로그래밍 언어에서 자료구조를 구현 하게 되는 것이다.
• 메모리는 비트로 된 셀 형태를 띄고 있으며, 비트마다 주소값을 가지고 있다.
• 프로그래밍에서는 비트 단위가 아닌 바이트 단위로 관리가 된다.
• 자료형에 맞는 배열이 만들어지게 되면, 해당 자료형의 비트에 맞게 배열 인덱스의 하나하나 크기가 정해지게 된다. 
• 즉, char(문자) 타입은 1바이트로 8비트이며 char 형태로 배열이 만들어지면 인덱스마다 1바이트(8비트)의 형태를 띄게 된다.

---

✅ 4. 1차원 배열

(1) 1차원 배열의 정의

• A[i] 는 배열의 첫 번째 원소 A[0] 이 저장된 메모리 주소인 a 로부터 시작하여, A[0] 부터 A[i-1] 개까지 i개의 배열 A[]를 지나서 저장됨
• 따라서, A[] 의 메모리 시작주소를 a 라고 가정하면, A[i] 의 메모리 저장 주소는 [a +i*k] 가 됨

(2) 1차원 배열에서의 주소 계산

• 쉽게말해, 하드웨어 메모리 측면에서 1바이트의 인덱스를 가지는 배열이 존재한다고 가정하면 A[0]... 모든 배열 원소값은 1바이트 즉, 8비트의 공간을 가지게 된다. 
• 또한 하드웨어 메모리 측면에서는 비트가 모인 셀 형태를 가지며, 운영체제는 이 비트를 바이트 단위로 쪼개서 관리를 한다. 
• 즉, 주소값은 바이트 단위로 가지게 된다는 의미이다. 
• 또한 배열의 특정 인덱스의 원소값을 얻어내려면 A[0] 배열의 시작주소를 a , i = 인덱스, k = 바이트 수 라고 가정을 하고 A[3] 저장 주소를 구한다고 가정하면 a + i * k 의 값으로 배열의 크기를 구할 수 있다.
• 계산하면 주소 = 0x0001 + 2 * 1 = 0x0003 의 결과를 얻게 된다. 즉, 주소값 0x0003 을 얻을 수 있다.

---

✅ 5. 배열의 확장

(1) 행렬의 배열 표현

• 행렬을 컴퓨터에서 표현하기에는 2차원 배열이 매우 적합함.

(2) 행렬의 2차원 배열 표현

(3) 행 우선 배열

• 1차원 배열을 여러 개 쌓아 놓은 것이 2차원 배열
• 즉, 2차원 배열을 쪼개서 1차원 배열로써 봄으로써 메모리에 2차원 배열을 표현 할 수 있게 된다.

(4) 행 우선 할당

• 가로의 1차원 배열 단위로 메모리 영역을 우선 할당함
• 행을 우선으로 하여, 컴퓨터 메모리에 저장을 하게 된다.
• 프로그래밍 언어마다 약간씩 다를 수 있음.

(5) 열 우선 배열

• 1차원 배열을 여러 개 세워 놓은 것 또한 2차원 배열로 볼 수 있으며, 열을 우선으로 하는 배열이다.
• 해당 열을 메모리 셀의 순서대로 저장이 된다.

(5) 열 우선 할당

• 세로의 1차원 배열 단위로 메모리 영역을 우선 할당함

(6) C 언어 에서의 2차원 배열

• C 언어에서는 행 우선 순서로 저장이 되며, A[3][5] 을 선언하면 다음과 같은 배열이 생성이 된다.

---

✅ 6. 희소행렬의 개념(표현)

(1) 희소행렬

행렬

• 원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 경우 즉, 원소값 0이 과반을 넘어가는 경우 희소행렬이라함.

 

2차원 배열 - 행렬

• 현재 2차원 배열은 메모리셀 72개의 공간을 사용하고 있으며 10개의 실 사용 원소값, 62개의 0 원소값을 가지고 있다.
• 문제는 사용하지 않는 원소값 때문에 메모리의 불필요한 공간을 차지하고 있는 문제가 있음

(2) 희소행렬의 효율적 배열표현

• 0인 원소는 저장하지 않고 0이 아닌 값만을 따로 모아서 저장하는 방식
• 메모리 낭비를 막고 효율성을 향상 시킬 수 있다.
• 불필요한 값인 0을 빼고 행과 열의 인덱스값과 원소값을 매칭해서 만드는 방식
• 하지만, 이방식 또한 메모리 성능은 올라가지만 연산 복잡도가 증가하며 연산 시간이 증가하게 된다는 문제가 있다.
• 즉, 메모리의 성능을 올리면 연산의 시간이 증가한다는 문제가 있고, 반대로 연산의 시간이 감소하면 메모리의 성능이 줄어드는 문제가 발생한다. 정답은 없음.