[자료구조] 배열 - 정리 및 연습문제

이전 포스팅

1. [자료구조] 자료구조란 무엇인가? - 정리 및 연습문제
https://atoz-develop.tistory.com/entry/entry/자료구조-자료구조란-무엇인가-정리-및-연습문제

 

1. 배열의 정의

배열(Array) :
- 인덱스와 원소값의 쌍(<index, value>)으로 구성된 집합
- 배열의 각 원소들은 자료형과 기억 공간의 크기가 같다.
- 메모리의 물리적인 위치를 순서적으로 결정하는 특징이 있다.
- 배열의 논리적인 순서(인덱스)는 메모리에 저장되는 원소값의 물리적인 순서(메모리 주소)와 동일하다.
- 배열의 첫 번째 원소의 메모리 주소와 인덱스를 통해 특정 원소의 주소값을 계산할 수 있다.
- 직접 접근(direct access) : 인덱스를 이용해 접근하므로
- 자료구조의 유형 중 선형 구조에 해당한다.
- 각 원소의 이름은 고유한 이름이 없고 원소의 위치에 따라 정해진다.

 

메모리 영역의 추상화와 구체화(출처: 한국방송통신대학교)

  그림의 좌측은 16진수로 표현되는 메모리의 실제 주소, 가운데는 메모리에 할당된 데이터, 우측은 배열의 인덱스이다. 이처럼 배열의 물리적인 저장 순서는 인덱스의 순서와 동일하다. 인덱스는 개발자가 직관적으로 받아들이기 위한 추상화된 값이다. 이렇게 추상화된 인덱스를 컴퓨터가 해석하여 물리적인 실제 주소로 변환한다.

 

2. 배열의 추상 자료형(ADT)

  이전 포스팅 [자료구조] 자료란 무엇인가?(링크)에서 다룬 것과 같이 추상 자료형이란 자료 집합과 연산 집합의 명세이다.

 

* Object(객체)
<i∈Index, e∈Element> 쌍들의 집합. Index는 순서를 나타내는 정수의 유한집합이고 Element는 타입이 같은 원소의 집합

* Functions(연산)
a∈Array; i∈index; x, item∈Element, n∈Integer인 모든 a, item, n에 대해 다음과 같은 연산이 정의된다. a는 0개 이상의 원소를 갖는 배열, item은 배열에 저장되는 원소, n은 배열의 최대 크기를 정의하는 정수값이다.

① Array create(n) ::= 배열의 크기가 n인 배열을 생성하고 반환한다;
② Element retrieve(a, i) ::=
    if(i∈Index) then {배열 a의 i인덱스에 해당하는 원소값 'e'를 반환한다;}
    else {에러 메시지를 반환한다;}
③ Array store(a, i, e) ::=
    if(i∈Index) then {배열 a의 i인덱스에 원소값 'e'를 저장하고 배열 a를 반환한다;}
    else {i가 배열 a의 크기를 벗어나면 에러메시지를 반환한다;}

 

3. 배열 연산의 구현

다음은 위에서 정의한 배열의 추상 자료형의 연산을 C언어로 구현한 것이다. Element는 정수로 가정한다.

 

3-1. 배열의 생성(create)

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

n=5일 때 배열 생성 결과(출처: 한국방송통신대학교)

 

3-2. 배열의 검색(retrieve)

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

 

1라인: 인덱스의 범위를 #define으로 정의한다. 인덱스 i가 유효 집합에 포함되어 있는지 확인하기 위함이다.

2라인: 배열을 가리키는 변수 a와 인덱스 i를 매개변수로 전달받는다.

3라인: i가 Index 유효 집합 범위에 해당하는지 비교한다.

4라인: 배열의 i번째 원소값을 반환한다.

6~7라인: i가 Index 유효 집합 범위에 해당하지 않는 경우로 "Error" 메시지를 출력하고 -1을 반환하고 종료한다.

 

(출처: 한국방송통신대학교)

  배열에 원소가 위 그림과 같이 저장되어 있다고 가정하면 retrieve(a, 2)는 a[2]인 30을 반환한다.

 

3-3. 배열의 저장

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

 

2라인: 배열을 가리키는 변수 a, 인덱스 i, 원소값 e를 매개변수로 전달받는다.

나머지는 배열의 검색 연산과 마찬가지로 인덱스 i의 값이 Index 유효 집합 범위에 해당하는지 확인하고 아니면 "Error" 메시지를 출력한다.

 

(출처: 한국방송통신대학교)

  store(a, 3, 35)의 결과는 위 그림과 같다.

 

4. 1차원 배열

- 인덱스가 한 개인 한 줄짜리 배열

- 예: A[i]

- 메모리 영역을 한 줄로 할당받는다.

 

(출처: 한국방송통신대학교)

배열 A의 첫 번째 원소 A[0]의 메모리 주소를 a라고 하고 각 자료형의 크기 k를 알면 A[i]의 주소를 계산할 수 있다.

 

1차원 배열 A[i]의 주소 계산

주소(A[i]) = 주소(A[0]) + i * 자료형의 크기

 

6. 2차원 배열

2차원 행렬 (출처: 한국방송통신대학교)

- 인덱스가 2개인 배열

- 예: A[i][j]

- 하나의 원소는 두 개의 인덱스(i, j)의 쌍으로 구분된다.

- i는 행(row), j는 열(column)을 표현한다.

- 행 우선 메모리 연속할당, 열 우선 메모리 연속할당 방법이 있다.

 

6-1. 행렬의 배열 표현

행렬을 프로그램으로 구현할 때 2차원 배열을 많이 사용한다.

 

행렬의 2차원 배열 표현 (출처: 한국방송통신대학교)

행렬은 행과 열로 이루어지므로 컴퓨터에서 표현할 때 동일한 형태인 2차원 배열이 적합하기 때문이다.

 

6-2. 2차원 행렬의 메모리 할당 방식

6-2-1. 행 우선 저장 방식

2차원 행렬의 행 우선 저장 (출처: 한국방송통신대학교)

행 우선 할당 방식은 가로의 1차원 배열 단위로 메모리 영역을 할당받는다. 즉 하나의 행이 연속적으로 메모리 영역을 할당받고 다음 행이 메모리 영역을 연속적으로 할당받는다.

 

[참고] 행 우선 저장 방식의 2차원 배열(MxN) 주소 계산

주소(A[i][j]) = 주소(A[0][0]) + i * N * 자료형의 크기 + j * 자료형의 크기

 

6-2-2. 열 우선 저장 방식

2차원 행렬의 열 우선 저장 (출처: 한국방송통신대학교)

열 우선 할당 방식은 세로의 1차원 배열 단위로 메모리 영역을 할당받는다. 즉 하나의 열이 연속적으로 메모리 영역을 할당받고 다음 열이 메모리 영역을 연속적으로 할당받는다.

 

[참고] 열 우선 저장 방식의 2차원 배열 주소 계산

주소(A[i][j]) = 주소(A[0][0]) + i * 자료형의 크기 + j * M * 자료형의 크기

 

  결국 '메모리에서 물리적인 저장 순서와 추상적인 원소의 순서가 일치한다'는 배열의 성질은 2차원 배열에서도 동일하다. 즉 2차원 배열도 1차원 배열과 마찬가지로 메모리에 순차적으로 저장된다. 따라서 배열의 크기(MxN), 첫 번째 원소의 주소, 인덱스, 자료형의 크기를 통해 특정 원소의 주소를 계산하여 배열의 특성 중 하나인 '직접 접근(direct access)'을 활용할 수 있다.

 

7. 희소행렬(Sparse Matrix)

- 원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬

 

희소행렬 (출처: 한국방송통신대학교)

- 희소행렬을 2차원 배열로 표현 시 메모리 낭비 발생

 

희소행렬의 일반적인 배열표현 (출처: 한국방송통신대학교)

- 따라서 메모리의 낭비를 막고 처리의 효율성을 높이기 위해 0이 아닌 값만을 따로 모아 저장하는 방법 필요

 

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

- 0이 아닌 각 원소를 (행번호, 열번호, 원소값)의 형태로 나타내면 우측과 같은 2차원 배열로 표현 가능

- 우측 배열의 [0,0]은 원본 배열의 행 수, [0,1]은 원본 배열의 열 수, [0,2]는 0이 아닌 원소값의 수를 나타낸다.

- 1행부터는 차례로 원본 배열의 행번호, 열번호, 값을 나타낸다.

- 예로 7행에 5, 3, 91이 저장되어 있는데, 좌측 원본 배열에서 [5,3]에 91이 저장되어 있음을 알 수 있다.

 

8. 연습문제

1. 자료구조의 유형 중 선형 구조에 해당하는 것은 무엇인가?
① 배열
② 그래프
③ 트리
④ 힢

2. 지문의 (가), (나)에 적합한 것은?
(가)의 각 원소의 이름은 고유한 이름이 없고 원소의 위치에 따라 정해지므로 순서를 바꿀 수 없으나, (나)는(은) 각 원소마다 고유한 이름으로 구별할 수 있다.
① 리스트, 배열
② 리스트, 레코드
③ 배열, 리스트
④ 배열, 레코드

3. 순서를 가진 원소들의 순열로서 물리적 순서가 논리적 순서와 일치하는 자료구조는 무엇인가?
① 순서 리스트
② 배열
③ 큐
④ 스택

4. 배열에 대한 설명으로 틀린 것은 무엇인가?
① 인덱스와 원소값(<index, value>)의 쌍으로 구성된 집합이다.
② 원소들이 모두 같은 자료형이다.
③ 구성 원소들의 논리적 관계와 원소의 저장 위치는 무관하다.
④ 메모리의 주소값과 추상화된 인덱스값이 관련되어 있다.

5. 아래는 배열값의 저장을 나타낸 것이다. [가]에 들어갈 가장 알맞은 코드는 무엇인가?
#define array_size 5
void store(int *a, int i, int e) {
    if( [가] ) a[i] = e;
    else printf("Error\n");
}
① i >= 0 && i < array_size
② i >= 0 || i < array_size
③ i <= 0 && i < array_size
④ i <= 0 || i < array_size

6. 다음 설명 중 틀린 것은 무엇인가?
① 배열은 인덱스와 원소값의 쌍으로 구성된다.
② 배열의 순서는 원소값이 저장되는 물리적인 위치와 아주 밀접한 상관이 있다.
③ 배열의 인덱스값을 이용해서 원소값에 직접 접근한다.
④ 배열의 각 원소값의 의미적인 순서는 인덱스의 순서와 일치한다.

7. 다음와 같은 행렬이 행우선 방식으로 저장된다면, [3,4]의 다음에 저장되는 행렬의 원소는 무엇인가?

① [3,5]
② [3,3]
③ [4,4]
④ [4,3]

 

정답 ▼

1 : ①
2 : ④
3 : ②
4 : ③
5 : ①
6 : ④
7 : ①