배열(Array)이란
같은 자료형에 같은 크기를 가진 원소들을 순서를 정해 나열시킨 집합을 배열이라고 함.
원소들간 순서는 인덱스라고 부르고 참조의 기준도 된다.
배열을 만들어 관리할 경우 선언과 변수명을 반복해 정할 필요가 없어지고 관리와 사용성이 올라간다.
원소를 나열하는 순서의 갯수에 따라 ~차원 배열로 표현함 (2차원 배열 같은거)
언어에 따라 인덱스 시작 숫자가 다른데 C는 0부터 시작되고, 베이직이나 포트란은 1부터 시작한다.
C에서 배열 선언 예시)
- int intArray[3]; - 인트형 3개 배열 선언 (1차원)
- int intArray[2][2]; - 인트형 2개 1차원 배열이 2개 있는 배열 선언 (2차원)
다차원 배열
배열의 인덱스가 차원을 구분하는 기준.
1차원 배열
- 위의 int intArray[3];을 선언할 경우 3개의 메모리 공간을 할당 받고 4바이트씩 3개, 총 12바이트를 사용한다.
2차원 배열
- 두개의 인덱스가 존재하고 각각의 인덱스는 열과 행을 표현한다.
- 메모리의 공간은 행과 열의 우선순위에 따라 실제 순서가 결정된다.
([2][2] 배열일 경우 행우선으로 하면 [0][0] [0][1] [1][0] [1][1] 이런 순서로 저장되고, 열우선이면 [0][0] [1][0] [0][1] [1][1] 요런 순서로 저장)
3차원 배열
- 2차원 배열을 한 편으로 부르고 이 편들이 복수개로 저장되는 개념.
- 인덱스 순서는 [편][행][열]로 정의한다.
- 물리적 저장은 항상 편을 우선순위로 하며, 각 편들은 행,열 우선순위에 따라 다르게 저장된다.(2차원 배열 저장 참조)
리스트(LIST)란
- 리스트는 자료를 나열한 목록을 의미함.
- 나열한 원소들간 순서가 있을 경우 선형이나 순서 리스트라고 함.
- 배열과 같이 동일한 기억공간에 저장된 경우 선형(순서) 순차 리스트, 각각의 기억 공간을 가지고 위치를 알릴 포인터가 있을 경우 선형(순서) 연결 리스트라 한다.
(결론: 리스트는 배열의 개념을 포함한 더 큰 범위의 개념)
- 원소의 크기를 확실히 알수 없으니 크기 할당에 낭비나 어려움이 있음.
- 표현방법은 자료를 기준으로 할 경우 집합으로 하고 순서를 기준으로 할 경우엔 배열 방식을 따르며, 연결 리스트는 자료형 상황에 따라 맞춰 다르게 표현된다.
1. 집합형
- 표현식은 A = {원소1, 원소2, 원소3} 와 같음.
- 단순 집합임으로 원소간 순서는 없음.
- 순서가 없음으로 삽입 삭제가 간편하지만, 원소간 순서 나열이 어려움.
2. 배열형
- 순서를 가짐으로 선형, 순서 리스트라고 불림.
- 순서 특성을 따름으로 배열의 특성과 비슷함.
- 연속된 공간에 원소가 저장되어 삽입이나 삭제시 자리 이동이 많이 발생하는 단점.
- 리스트가 공간 할당에 어려움이 있지만 순서 덕분에 참조의 효율이 증가함.
- 자료가 n개일때 삽입시 평균 이동 횟수는 (n+1)/2이며, 삭제시엔 (n-1)/2이다.
- 자리 이동이 많더라도 이용 효율은 밀도가 1일때 가장 좋다고 한다.
- 삽입 연산시에 추가 공간이 필요함으로 공간 할당에 따라선 삽입 연산에 제한이 올 수 있음.
3. 연결 리스트
- 각각의 공간에 따로 저장되어 있음으로 삽입, 삭제 연산이 효율적.
- 구현 방법은 복잡.
- 할당 공간의 제한이 없음.
- 연산 시간 복잡도는 상수 시간만 존재.
배열 표현법 (C 기준)
- 각 원소의 크기는 자료형에 따라 결정된다.
- 각 원소의 위치는 시작 주소가 a일 때 a + (n * type) byte로 결정된다.
(n은 인덱스, type은 자료형 크기)
(int형 3개짜리 배열일 경우 각 원소의 주소는 a, a+4, a+8 바이트가 된다)
- 2차원 이상일 경우 행과 열의 우선순위에 따라 물리적 저장 순서가 결정된다.
(다차원 배열 중 2,3 차원 배열 참조)
- 2차원 배열 A[n1][n2]에서 A[i][j]의 주소값은
행우선시 a + (i*n2+j) * type
열우선시 a + (j*n1+i) * type
으로 계산된다.
(n은 인덱스, type은 자료형 크기)
희소 행렬
- 행렬의 표준 표현은 2차원 배열로 A[MAX_ROWS][MAX_COLS] 로 표현되고 보통 행은 i, 열은 j로 사용되어 원소를 가르키는 표현은 A[i][j]로 사용된다.
- 행과 열이 동일할 경우 정방 행렬이라 부른다.
- 행렬의 내용 중 빈 값이 있는 경우 희소 행렬이라 한다.
- 희소 행렬의 경우 원소값 추출을 통한 새로운 행렬을 만들어 표현하는게 일반적이다.
- 원소값 추출이란 행렬중 빈 값이 아닌 원소의 좌표를 모으는걸 의미한다.
- 원소값 추출을 통해 도출된 좌표는 <행 열 값>의 순서를 가지며 이 좌표로 새 2차원 행렬을 만들어 희소 행렬을 표현한다.
예시)
A[4][4]인 희소 행렬에 빈 값이 아닌 원소가 2개일 경우 원소값 추출을 하면
<2,1,9>, <3,3,2> 좌표 2개가 나오며
(2행 1열에 9값) (3행 3열에 2값)
희소 행렬의 상태를 표현할 좌표값 <4,4,2> (4행 4열의 행렬이며 빈 값이 아닌 원소 2개)
을 추가하여 최종적으로
[4 4 2]
[2 1 9]
[3 3 2] 와 같은 B[3][3] 행렬로 새롭게 표현되는걸 희소 행렬의 표현방식이다.
(결론은 그냥 빈 값 다 빼고 좌표로 행렬을 만들어 공간 낭비를 줄이는것)
- 공간 효율은 증가했으나 좌표값을 통한 값을 찾아 가는 과정이 필요함으로 연산 효율은 떨어진다.
전치 행렬
- 보수의 개념같이 행렬의 행과 열을 바꾸는것.
- A행렬의 전치 행렬은 A𝞣로 표현한다.
- a[2][3]의 전치 행렬은 b[3][2]
- 전치 행렬과 본래 행렬이 동일할 경우 대칭 행렬이라 부른다.
- 희소 행렬일 경우엔 빈 값은 전치 연산을 하지 않는다.
- 전치 연산 알고리즘 예시
for(i=0; i<=m-1; i++)
for(j=0; j<=n-1; j++)
b[j][i] = a[i][j];
- 시간 복잡도는 반복 수행 결과값과 같음으로 O(mn)이 된다.
