[자료구조] 2. 배열

 

※ 방송통신대학교 컴퓨터공학과의 '자료구조' 강의 내용 기반으로 작성되었음

 

[1] 배열의 정의

🔑 배열의 정의

• 사전적 정의 : 일정한 차례나 간격에 따라 벌여 놓음
• '차례(순서)'와 관련된 기본적인 자료구조
• 원소의 메모리 공간(메인메모리, DDR)의 물리적 위치를 순서적으로 결정하는 특징
• 배열의 순서는 메모리 공간에서 저장되는 '원소값의 물리적 순서'
• 인덱스와 원소값(<index, value>)의 쌍으로 구성
• 원소들이 모두 같은 자료형과 같은 크기의 기억공간을 가짐
• 배열의 인덱스값을 이용해 원소값에 접근하기 때문에 직접 접근이 가능함
• (예) 호수(=인덱스)로 표현되는 순서를 갖는 아파트. 
  아파트 => 배열
  301호 => 인덱스
  입주자 => 원소값
• 배열의 인덱스값 : 추상화된 값. 즉, 컴퓨터의 내부 구조나 메모리 주소와 무관하게 개발자에게 개념적으로 정의됨
• 메모리 주소값은 실제 메모리의 물리적인 위치값 
• 인덱스 == 추상화된 값
• 주소값 == 구체화된 값

 

[2] 배열의 추상 자료형

🔑 추상자료형

• 객체 및 관련된 연산의 정의로 구성됨
• 자료구조의 구현 전 설계 단계
• 자료의 추상화에 대한 결과

 

🔑 자료형

• 메모리 저장 할당을 위한 변수 선언
• 자료구조의 구현 단계(프로그래밍 언어를 이용한 선언)

 

🔑 배열의 추상자료형

• ADT Array 객체 : < i ∈ Index, e∈ Element> 쌍들의 집합
• Index : 순서를 나타내는 원소의 유한집합
• Element : 자료형이 같은 원소의 집합

 

 

 

[3] 배열 연산의 구현

🔑 배열의 생성

• void create(int n)
• 컴파일러에 의해 구현되어 있으며 개발자는 생성자를 통해 자동호출하게 된다.

 

🔑 배열의 검색

• int retrieve(int *a, int i) 
• 예를 들어,  k = a[2]; 라고 작성하면 retrieve 함수를 호출하여 값을 꺼내고 k에 값을 할당한다. 

 

🔑 배열 값의 저장

• void store(int *a, int i, int e)
• 값을 주고 그 값을 지정된 배열의 해당 인덱스에 저장한다.
• a[2] = 3;
  => store(a, 3, 35) 을 컴파일러가 호출

 

 

[4] 1차원 배열

🔑 1차원 배열의 정의

• 한 줄짜리 배열을 의미하며, 하나의 인덱스로 구분된다.
• A[i]는 배열의 첫 번째 원소 A[0]이 저장된 메모리 주소인 a로부터 시작하여, A[0] 부터 A[i-1]개까지 i 개의 배열 A[]를 지나서 저장됨.
• 따라서, A[]의 메모리 시작 주소가 a이고 Element 하나가 k만큼 차지한다고 가정하면, A[i]의 메모리 저장 주소는 [a + i*k] 가 된다. 

 

 

 

[5] 배열의 확장

🔑 행렬의 배열 표현

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

 

 

🔑 행렬의 2차원 배열 표현

 

• 행렬을 2차원 배열로 표현했을 때, 이것을 메모리에 적재(할당)하는 방식이 컴파일러 혹은 프로그래밍 언어마다 다르다. 

 

🔑 행 우선 배열

• 1차원 배열을 여러 개 쌓아 놓은 것이 2차원 배열
• 각 행을 메모리에 순서대로 적재한다. 
• 가로의 1차원 배열 단위로 메모리 영역을 우선 할당함
• 행 위주로 순서를 정해놓고 그것을 1차원 배열처럼 저장함.

 

 

 

 

🔑 열 우선 배열

• 1차원 배열을 여러 개 세워 놓은 것이 2차원 배열

 

 

 

[6] 희소행렬의 표현

🔑 희소행렬

• 원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은(=과반 이상인) 행렬

 

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

• 0인 원소는 저장하지 않고 0이 아닌 값만을 따로 모아서 저장
• 마찬가지로 2차원 행렬로 표현됨.
• 그러나 시작행(0행)의 0번은 행의 개수, 1번은 열의 개수, 2번은 0이 아닌 원소값의 개수로 구성함.
  그 다음 행부터는 차례로 0이 아닌 값을 표현하는데, 그 값의 행 번호, 열 번호, 원소값으로 구성.
• 메모리 낭비를 막고 효율성 향상
• 예를 들어 아래 이미지와 같은 희소행렬이 있을 때, 그대로 표현했다면 8*9인 72개의 메모리가 필요했으나 이러한 효율적 배열 표현을 통해 33개의 메모리로 줄어듦.
• 그러나 이 경우 연산이 문제가 된다 → 연산이 따로 구현되어야 함(복잡해짐) → 계산 시간이 증가함