[자료구조] 2강. 배열 - 정리

주요 용어

용어	해설
배열	인덱스와 원소 값(<index, value>)의 쌍으로 구성된 집합이며, 정의된 각 인덱스는 그 인덱스와 관련된 값을 정의함
2차원 배열	원소 값을 특정하기 위해 필요한 인덱스가 두 개인 배열
행렬의 행우선 저장 방식	하나의 행을 연속적으로 메모리에 할당하고, 그 다음 행을 메모리 영역에 할당하는 방법
열우선 저장 방식 행렬	하나의 열을 연속적으로 메모리에 할당하고, 그 다음 열을 메모리 영역에 할당하는 방법
희소행렬 (sparse matrix)	원소 값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬을 의미함

학습 정리

배열은 인덱스와 원소 값(<index, value>)의 쌍으로 구성된 집합으로서, 정의된 각 인덱스는 그 인덱스와 관련된 값을 갖습니다.

배열의 순서는 메모리 공간에서 저장되는 ‘원소 값의 물리적 순서’를 의미합니다.

배열의 각 원소의 물리적인 위치(메모리 주소)의 순서가 배열의 인덱스의 순서(논리적인 순서)와 일치합니다.

배열의 인덱스 값을 이용해서 배열의 원소 값에 접근하기 때문에 직접 접근(direct access)입니다.

배열의 물리적인 저장 순서는 배열의 인덱스에 의해서 결정되며, 그 순서에 따라 메인 메모리에서의 저장 위치의 순서가 됩니다.

create(n)은 n 개의 원소들을 저장할 수 있는 공백 배열(empty array)을 생성합니다. 배열을 생성할 때 n 개의 원소들을 저장할 수 있는 공간은 만들어지지만 그 안에 채워진 원소 값들이 아직은 없다는 것을 의미합니다.

연산 retrieve(a, i)는 배열 a와 인덱스 i를 매개 변수로 전달받아 인덱스 i 위치에 대응되는 원소 값 e가 있다면 원소 값 e를 반환하고 그렇지 않은 경우 에러 메시지를 반환합니다.

연산 store(a, i, e)는 배열 a와 인덱스 i, 원소 값 e를 매개 변수로 전달받아 Index를 검사하여 i 값이 유효할 경우 쌍이 되게 원소 값을 i 번째 인덱스에 저장하고 배열 a를 반환합니다.

가장 기본적인 배열은 1차원 배열이며, 한 줄짜리 배열을 의미하므로 인덱스는 하나입니다. 한 줄짜리 배열은 메모리 영역도 한줄로 할당받습니다.

2차원 배열의 행우선 저장방식은 하나의 행이 모두 연속적으로 메모리 영역을 할당받고, 다음 행이 메모리 영역을 연속적으로 할당받는 방식이다.

원소 값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬을 희소 행렬(sparsematrix)이라 합니다.