2강. 배열

학습개요

배열은 자료의 추상화된 의미와 구체화된 의미가 유사한 자료구조입니다. 자료간의 관계가 추상화되었을 때와 구체화되어 저장되었을 때가 동일하다는 의미입니다. 배열은 자료에 해당하는 원소(원소값)와 몇 번째에 해당하는 지를 의미하는 인덱스로 구성됩니다.

즉, 배열은 순서를 표현하는 인덱스와 값을 표현하는 원소값의 쌍으로 이루어집니다. 이러한 특성은 2차원 배열이나 3차원 배열에서도 지켜집니다. 즉, 1차원 배열의 확장된 모양이 2차원 배열이며 3차원 배열이 되는 것입니다. 마지막으로 희소 배열을 표현할 때는 메모리 사용의 효율성을 높이기 위해 새로운 형태의 2차원 배열을 사용합니다.

학습목표

1. 배열의 추상 자료형을 이해할 수 있다.
2. 배열의 원소의 순서와 저장 위치에 대해서 이해할 수 있다.
3. 1차원 배열이 확장된 2차원 배열의 메인 메모리의 연속 할당을 이해할 수 있다.
4. 희소행렬을 효율적으로 다룰 수 있는 자료구조를 이해할 수 있다.

연습문제

1. 자료 구조의 유형 중 선형 구조에 해당하는 것은 무엇인가 ?
   1. 배열 
   2. 그래프
   3. 트리
   4. 히프
      –
2. 배열은 자료에 해당하는 (가)와 몇 번째에 해당하는 지를 의미하는 (나)로 구성됩니다. 즉, 배열은 순서를 표현하는 (나)와 값을 표현하는 (가)의 쌍으로 이루어집니다.
   1. 지문 (가), (나)에 적합한 것은 ?
      1. 인덱스, 원소(원소값)
      2. 원소값, 레코드
      3. 레코드, 원소값
      4. 원소(원소값), 인덱스
         –
3. 순서를 가진 원소들의 순열로서 물리적 순서가 논리적인 순서와 일치하는 하여 논리적 순서를 의미하는 자료구조는 무엇인가 ?
   1. 트리
   2. 배열
   3. 스택
   4. 큐

정리하기

1. 배열은 인덱스와 원소값(<index, value=””>)의 쌍으로 구성된 집합으로서, 정의된 각 인덱스는 그 인덱스와 관련된 값을 갖습니다.
2. 배열의 순서는 메모리 공간에서 저장되는 ‘원소값의 물리적 순서’를 의미합니다.
3. 배열의 각 원소의 물리적인 위치(메모리 주소)의 순서가 배열의 인덱스의 순서(논리적인 순서)와 일치합니다.
4. 배열의 인덱스값을 이용해서 배열의 원소값에 접근하기 때문에 직접 접근(direct access)입니다.
5. 배열의 물리적인 저장 순서는 배열의 인덱스에 의해서 결정되며, 그 순서에 따라 메인 메모리에서의 저장 위치의 순서가 됩니다.
6. create(n)은 n개의 원소들을 저장할 수 있는 공백 배열(empty array)을 생성합니다. 배열을 생성할 때 n개의 원소들을 저장할 수 있는 공간은 만들어지지만 그 안에 채워진 원소값들이 아직은 없다는 것을 의미합니다.
7. 연산 retrieve(a,i)는 배열 a와 인덱스 i를 매개 변수로 전달받아 인덱스 i 위치에 대응되는 원소값 e가 있다면 원소값 e를 반환하고 그렇지 않은 경우 에러 메시지를 반환합니다.
8. 연산 store(a, i, e)는 배열 a와 인덱스 i, 원소값 e를 매개 변수로 전달받아 Index를 검사하여 i값이 유효할 경우 <i, e=””>쌍이 되게 원소값을 i번째 인덱스에 저장하고 배열 a를 반환합니다.
9. 가장 기본적인 배열은 1차원 배열이며, 한줄짜리 배열을 의미하므로 인덱스는 하나입니다. 한줄짜리 배열은 메모리 영역도 한줄로 할당받습니다.
10. 2차원 배열의 행우선 저장방식은 하나의 행이 모두 연속적으로 메모리 영역을 할당받고, 다음 행이 메모리 영역을 연속적으로 할당받는 방식입니다.
11. 2차원 배열의 열우선 저장방식은 하나의 열이 모두 연속적으로 메모리 영역을 할당받고, 다음 열이 메모리 영역을 연속적으로 할당받는 방식입니다.
12. 원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬을 희소행렬(sparse matrix)이라 합니다.