배열
배열의 정의
일정한 차례나 간격에 따라 벌여 놓음 순서와 관련된 기본적 자료 구조
원소의 메모리 공간의 물리적 위치를 순서적으로 결정하는 특징을 갖는다 배열의 순서는 메모리 공간에서 저장되는 원소값의 물리적 순서
인덱스와 원소값의 쌍으로 구성된 집합
원소들이 모두 같은 자료형과 같은 크기의 기억 공간을 가진다 배열의 인덱스를 이용하여 값에 접근하기 때문에 직접 접근이 가능하다
배열의 인덱스 값: 추상화된 값 -> 컴퓨터의 내부 구조나 메모리 주소와 무관하게 개념적으로 정의 됨 메모리 주소 값: 실제 메모리의 물리적 위치 값 배열의 인덱스 값은 프로그래밍 언어와 컴파일 과정을 통해 메모리 주소와 연결됨
추상화와 구체화가 동일한 자료구조
배열의 추상 자료형
추상 자료형 (수학적) 객체 및 관련된 연산의 정의로 구성됨 자료구조 구현 전의 설계 단계
자료형 메모리 저장 할당을 위한 변수 선언 자료구조의 구현 단계 (프로그래밍 언어를 이용한 선언)
ADT Array 객체
<index, element>쌍들의 집합 index: 순서를 나타내는 원소의 유한 집합 element: 서로 같은 자료형을 갖는 원소의 집합연산 create(생성), retrieve(찾기), store(저장) 원소 삭제는 왜 없을까
배열의 연산 구현
배열의 생성 ``` // 아래 코드는 컴파일러에 의해 구현되는 모습 void create(int n) { int a[n];
int i; for(i=0, i<n, i++) { a[i] = 0 } }
// 사용자가 배열 생성 시 int a[5]; // 길이 5짜리 배열 생성
1
2
- 배열의 검색
// 컴파일러에 의해 구현되는 모습
#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); } }
// 사용자가 배열 탐색 시 int k = 0; k = a[2];
1
2
3
4
- 배열의 저장
// 컴파일러에 의해 구현된 모습
#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); }
// 사용자가 배열 저장 시 a[0] = 1; a[1] = 2; ```
1차원 배열
한 줄 짜리 배열로 하나의 인덱스로 구분한다
A 배열의 0번쨰 인덱스 (시작 주소) 가 a 라고 했을 때 A[3] 의 실제 주소는 a + 3 * k 가 된다 이 때 k 는 데이터의 크기 실제 주소는 16진수를 사용한다
배열의 확장
행렬의 배열 표현 - 2차원 배열을 나타내기 좋다 2차원 배열에서 하나의 데이터를 인덱싱 하기 위해서는 A[x, y] 와 같이 나타낸다
2차원 배열의 주소를 어떻게 표현하는가는 프로그래밍 언어별 컴파일러별 차이가 있을 수 있다 각 언어와 컴파일러의 특징을 알고 있다면 성능을 조금 높일 수 있다
- 행 우선 할당 1차원 배열을 여러게 쌓아놓은 형태로 2차원 배열을 구성한다 첫 1차원 배열 하나의 끝에
A[1, 0]를 이어 붙이는 형식
ex) C언어
- 열 우선 할당 2차원 배열을 열 기준으로 잘라 메모리에 적재한다
[A[0, 0], A[1, 0], A[2, 0]]을 하나의 배열처럼 잘라서 저장
행 우선 할당, 열 우선 할당은 프로그래밍 언어를 만드는 사람의 취향에 따라 선택할 수 있다
희소행렬의 표현
- 희소행렬: 원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 것
희소행렬의 효율적 배열 표현
0인 원소는 저장하지 않고 0이 아닌 값들만 따로 모아서 저장 -> 메모리 낭비를 막고 효율성 또한 향상된다
2차원 배열로 값의 행과 열을 값으로 가지는 배열을 만든다 (좌표 값과 값을 갖는 배열)
메모리와 성능은 대체로 트레이드 오프 관계이다