자료구조 강의 2화 :: 배열, 추상자료형, 희소행렬

자료구조 2화를 듣고 배운내용

 

주요 용어

배열: 인덱스와 원소값(index, value) 쌍으로 구성된 집합, 각 인덱스는 그 인덱스와 관련된 값을 정의

2차원 배열: 원소값을 특정하기 위해 필요한 인덱스가 2개인 배열

행 우선 저장 방식 행렬: 하나의 행을 연속적으로 메모리에 할당하고, 그 다음 행을 메모리 영역에 할당

열 우선 저장 방식 행렬: 하나의 열을 연속적으로 메모리에 할당하고, 그 다음 열을 메모리 영역에 할당

희소행렬(sparse matrix): 원소값이 0인 원소가 그렇지 않은 원소보다 많은 행렬

 

 

배열이란?

원소의 메모리 공간의 물리적인 위치를 순서적으로 결정하는 특징

배열의 순서: 메모리 공간에 저장되는 원소값이 물리적 순서

 

한 배열안의 원소들이 모두 같은 자료형, 같은 크기 기억공간을 가진다.

배열의 인덱스값을 이용해서 직접 접근 가능

 

인덱스값: 추상화된 값, 컴퓨터의 내부구조나 메모리의 주소와 상관없이 개발자가 정의

메모리 주소값: 실제 메모리의 물리적인 위치값

 

 

추상 자료형? 자료형?

추상자료형: 객체(데이터) 및 관련된 연산의 정의 예) C로 따지면 printf()

개발자를 위한 것

printf() 같은 추상자료형은 컴파일러 만드는 사람들이 미리 정의해놓은것

 

자료형: 메모리 저장 할당을 위한 선언 예) int, float

메모리 할당을 위한 것

 

크기가 5인 배열이 있다고 하자.

6번째에 값을 넣으면 에러가 뜬다. 그런 내용을 만드는 사람들이 컴파일러는 만드는 개발자.

자료구조는 사실 프로그래밍 언어를 사용하는 개발자를 위해 컴파일러를 만드는 개발자를 위한 내용일 수 있다.

 

 

1차원 배열이란?

하나의 인덱스로 정의된다.

배열 A의 시작 주소를 a라면, A[i] 저장 주소는 [a + i* k ]가 된다.

k는 메모리 할당

 

 

2차원 배열 - 1차원 배열의 확장

배열의 저장 순서에 따라 행 우선 할당, 열 우선 할당이 있다.

행부터 저장하거나, 열부터 저장하거나 컴파일러 개발자, 운영체제 개발자가 언어에 따라 정한다.

 

예) C언어는 행 우선 저장

이걸 이해하면 조금이라도 향상된 실행 속도를 가지게 된다.

행 우선 [0, 0] [1, 0] [0, 1] [1, 1]

열 우선 [0, 0] [0, 1] [1, 0] [1, 1]

C에서는 행 우선이 더 빠르겠지?

 

 

희소행렬

메모리 낭비를 막고 효율을 높이려고 0인 원소는 저장하지 않고,

0이 아닌 값만 따로 모아서 저장하는 방법