자료구조, 알고리즘은 잘 알고 있다고 생각했다. 그러나 현실의 문제가 주어졌을 때
자료구조, 알고리즘을 이용하여 문제를 해결하는 역량이 부족하다는 것을 깨달을 수 있었다.
그래서 다시 한번 자료구조와 알고리즘을 공부하기로 결심하였다.
배열은 인덱스와 원소값(＜index, value＞)의 쌍으로 구성된 집합으로서,
정의된 각 인덱스는 그 인덱스와 관련된 값을 가지며 각각의 값은 모두 같은 자료형이다.
여기서 같은 자료형이라는 의미는 메인 메모리 상에서의 크기가 같다는 의미이다.
배열은 원소의 메인 메모리 공간에서의 물리적인 위치를 순서적으로 결정하는 특징이 있다.
즉, 배열의 순서는 메모리 공간에서 저장되는 ‘원소값의 물리적 순서’를 의미한다.
따라서 배열의 첫 번째 원소가 위치하는 메모리 주소를 알수 있다면,
인덱스를 이용하여 임의의 원소의 메모리 주소를 계산할 수 있다.
ex) A[i] = a(시작 주소) + i(인덱스) x k(자료형의 크기)
배열의 인덱스값을 이용해서 배열의 원소값에 접근하기 때문에 직접 접근(direct access)이다.
배열의 물리적인 저장 순서는 배열의 인덱스에 의해서 결정된다.
그리고 해당 순서에 따라 메인 메모리에서의 저장 위치의 순서가 된다.
[ADT Array]
objects: <index, element> 쌍들의 집합
index는 순서를 나타내는 원소의 유한 집합, element는 타입이 같은 원소의 집합을 의미
주요 연산 : create, retrieve, store
(참고 : a(array), i(index), e(element), n(integer))
1) create(n)
배열의 크기가 n인 빈 배열을 생성하고 배열을 반환한다.
void create(int n) {
int a[n];
int i;
for (i = 0, i < n, i++) {
a[i] = 0;
}
}
2) retrieve(a, i)
배열 a의 i번째 위치에 대응되는 원소값이 있다면 원소값을 반환한다.
그렇지 않은 경우 에러 메시지를 반환한다.
# 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); }
}
3) store(a, i, e)
i가 index에 해당한다면 배열 a의 i번째 위치에 원소값 e를 저장하고 배열 a를 반환한다.
i가 배열 a의 크기를 벗어나면 에러를 반환한다.
# 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");
}관련 흥미로운 문제
원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 2차원 배열이 존재한다고 하자.
이때 2차원 배열의 크기는 (1억 x 1억)이며, 0이 아닌 원소의 개수는 1000개이다.
그런데 0의 값을 저장하기 위해서 불필요하게 많은 컴퓨터 메모리가 요구된다.
따라서 컴퓨터 메모리의 낭비를 막고 처리의 효율성을 높이기 위해 0인 원소는 저장하지 않고,
0이 아닌 원소만을 따로 모아서 저장하는 방법을 찾고자 한다. 어떻게 할 수 있을까?
0이 아닌 각 원소를 (행번호, 열번호, 원소값)의 형태로 나타내면 된다.
첫 번째 행은 행 크기와 열 크기, 0이 아닌 값의 원소의 개수로 표현하고,
두 번째 행부터 0이 아닌 원소를 (행번호, 열번호, 원소값)의 형태로 표현하면 된다.
실제로 데이터를 저장하고 송신하는 과정에서 위와 같이 불필요한 정보들이 담겨 있는 상황이 발생한다.
사실 내가 자료구조를 공부하게 된 이유이기도 하다. 해당 상황에서 자료구조를 조작하여 효율화할 수 있었다면 문제를 조금 더 빠르게 해결할 수 있었을 텐데 그러지 못하여 아쉬울 따름이다.
