방송대 자료구조 교재 요약 제2 장 - 배열

2장 개관을 읽는데 모든 줄이 킬링 포인트라서 내가 차마 여기에 다 옮기지를 못 하고 있다.

옮기자면 분량이 너무 많고 저작권도 신경 쓰인다.

정광식 교수님의 강의를 만족하며 들었기 때문에 더욱 그렇다.

 

제2 장 배열)

 

개관)

희소행렬이란?

https://www.geeksforgeeks.org/sparse-matrix-representation/

 

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

위 2차원 배열의 모든 행과 열을 다 메모리에 올리면 공간 낭비가 심하다.

그래서 값이 0이 아닌 것만 행,열,값 형태로 정리한다.

 

1. 배열의 정의

배열은 인덱스 순으로 표현되는 메모리 영역이다.

배열의 원소는 모두 같은 자료형으로 각자 해당 자료형의 값과 같은 크기의 기억 공간을 갖는다.

배열의 각 원소의 메모리 주소의 순서가 배열의 인덱스의 순서와 일치해 첫 번째 원소가 위치하는 메모리 주소를 알면 인덱스를 이용하여 임의의 배열 원소의 주소값을 알 수 있다(계산할 수 있다.).

개발자가 알고 있는 인덱스 값은 단순한 정수이지만 메모리의 주소값은 16진수이면서 프로그램이 실행되어야 결정된다.

프로그램이 실행되어 배열이 생성되면 그때 메모리 주소가 정해진다(e.g. 00ffff00).

그리고 개발자는 그 배열의 첫 번째 요소에 인덱스 0으로 접근할 수 있게 된다.

배열은 시작 메모리 주소에서 연속적으로 생성되기 때문에 인덱스가 증가함에 따라 일정하게 그 다음 메모리 주소를 계산할 수 있다.

그래서 arr[2] 이런 식으로 인덱스만 가지고 배열의 값에 접근할 수 있으며 인덱스로 배열의 값을 찾는다면 실행 속도가 O(n)이 되는 것이다(인덱스만 알면 '바로' 검색이 가능하기 때문).

...

2. 배열의 추상 자료형

배열은 크기가 정해진 채로 생성된다.

배열의 ADT에 대해서는 딱히 생각해 본 적이 없는데 교재 24페이지를 보면 C에서의 배열의 ADT가 나와 있다.

...

3. 배열의 연산의 구현

(이제 C로 자료구조를 코드화하는 부분이 시작되는데 이 부분은 별도로 정리하지 않을 것임. C프로그래밍 정리를 따로 해야 하기 때문.)

...

4. 1차원 배열

...

5. 배열의 확장

...

6. 희소행렬의 개념

...

 

내가 온전히 이해하는 것, 너무 기본이라서 굳이 언급하지 않아도 되는 것은 정리를 안 하고 있다 보니

여기서 정리가 끝나버렸다.;