All
배열의 정의
•
배열(Array): 동일한 자료형의 데이터를 연속된 메모리 공간에 저장하는 자료구조
•
특징
◦
고정된 크기
◦
연속된 메모리 공간 사용
▪
배열 원소들은 메모리상에서 연속적으로 배치됨
▪
따라서 주소 계산을 통해 원하는 원소에 곧바로 접근할 수 있음
◦
임의 접근(Random Access)
▪
인덱스(index)를 이용해 O(1) 시간에 원하는 위치의 데이터를 읽거나 수정할 수 있음
▪
예: arr[3] → 배열의 4번째 원소에 즉시 접근
◦
동일한 자료형
배열의 추상 자료형 (ADT: Abstract Data Type)
추상자료형
•
객체와 그 객체와 관련된 연산의 정의로 구성됨
•
자료구조를 실제로 구현하기 전에, 설계 단계에서 먼저 정의하는 이론적 개념
자료형
•
메모리에 저장하기 위한 변수 선언을 의미
•
자료구조의 실제 구현 단계에서, 프로그래밍 언어를 통해 선언됨
ADT Array 정의
Array 객체 : <i ∈ Index, e ∈ Element> 쌍들의 집합
Bash
복사
•
Index 집합: 순서를 나타내는 원소의 유한 집합 (보통 0 ~ n-1)
•
Element 집합: 자료형이 같은 원소들의 집합
ADT 배열의 연산 정의
•
생성 (crate) - Array create(n)
•
조회 (retrieve)
◦
Element retrieve(a, i)
◦
배열 a의 i번째 원소를 반환
◦
조건: i ∈ Index (인덱스 범위 안)
◦
범위를 벗어나면 에러 반환
•
저장 (store)
◦
Array store(a, i, e)
◦
배열 a의 i번째 위치에 원소 e를 저장하고 배열을 반환
◦
조건: i ∈ Index
◦
범위를 벗어나면 에러 반환
배열 연산의 구현
생성
•
크기 n 인 배열 생성후 0으로 초기화
void create(int n) {
int a[n];
for (int i=0; i<n; i++) {
a[i] = 0; // 초기화
}
}
C
복사
조회
•
인덱스가 유효하면 값 반환, 아니면 에러
int retrieve(int *a, int i) {
if (i >= 0 && i < array_size)
return a[i];
else {
printf("Error\n");
return -1;
}
}
C
복사
저장
•
인덱스가 유효하면 값 저장
void store(int *a, int i, int e) {
if (i >= 0 && i < array_size)
a[i] = e;
else
printf("Error\n");
}
C
복사
1차원 배열
•
한줄 짜리 배열로 연속된 메모리 공간에 원소들이 차례대로 저장
메모리 주소 계산
•
배열의 첫 번째 원소 A[0]이 저장된 메모리 주소를 α (알파) 라고 가정
•
각 원소의 크기를 k 바이트 라고 할때
◦
예: int 자료형은 보통 4바이트 → k = 4
•
배열의 i번째 원소 A[i]의 주소는 다음과 같이 계산
주소(A[i]) = α + (i × k)
Plain Text
복사
•
A[0] → α
•
A[1] → α + k
•
A[2] → α + 2k
•
A[3] → α + 3k
•
A[i] → α + i × k
예시
•
배열 int A[5] 선언
•
시작 주소 α = 1000
•
int 크기 k = 4바이트
그럼 주소는:
•
A[0] = 1000
•
A[1] = 1004
•
A[2] = 1008
•
A[3] = 1012
•
A[4] = 1016
→ 주소 계산으로 i번째 원소 바로 접근가능
배열의 확장
•
행렬을 컴퓨텨에서 표현하면 2차원 배열이 적합
행 우선 배열
•
1차원 배열 여러개 쌓아놓은 형태
•
가로의 1차원 배열 단위로 메모리 영역을 우선 할당
열 우선 배열
•
1차원 배열을 여러 개 세워 놓은 형태
•
세로의 1차원 배열 단위로 메모리 영역을 우선 할당
희소행렬(Sparse Matrix)
•
원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬
•
0인 값을 모두 저장하면 메모리 낭비가 되므로, 0이 아닌 값만 따로 모아서 저장
•
(행, 열, 값) 형태로 압축해 저장
•
예시
◦
[0, 0, 5]
[0, 0, 0]
[7, 0, 0]
◦
→ (0, 2, 5), (2, 0, 7)