05. 순차 자료구조 방식

05. 순차 자료구조 방식

학습 목표

순차 자료구조 방식의 의미와 특징을 알아본다.

선형 리스트의 구조와 연산을 알아본다.

선형 리스트의 자바 프로그램 구현을 알아본다.

선형 리스트의 응용 방법을 알아본다.

1. 선형리스트 

선형 리스트 Linear List or

순서 리스트 Ordered List

순차 자료구조에서는 원소의 논리적인 순서대로 데이터가 메모리에 연속 저장된다. 

- 삽입: 선형리스트에 새로운 원소를 삽입하려면 먼저 원스를 삽입할 위치 포함, 그 이후에 있는 원소들을 모두 한자리씩 뒤로 옮겨서 빈자리를 만든다. 그리고 그 빈자리에 원소를 삽입한다. 

- 삭제: 선형리스트에 원소를 삭제하려면 원소를 삭제하고, 원소를 삭제한 위치 이후에 있는 원소들을 모두 한자리씩 앞으로 옮겨서 빈자리를 채워야 한다. 

2. 선형리스트의 구현

선형 리스트를 순차 구조로 구현하기 위해 배열을 사용한다. 배열은 <인덱스, 원소>의 쌍으로 구성되어 메모리에 연속적으로 할당되는데, 이 때 인덱스는 배열 원소의 순서를 나타낸다. 배열은 순서를 가진 배열 원소들을 메모리에 연속하여 순차 구성하므로 프로그래밍 언어에서 제공하는 배열을 그대로 사용하여 선형 리스트를 구현할 수 있다.

int[] 의 각 원소 위치는 a(시작주소) + (인덱스) * (Integer 4byte) 

n 차원 배열의 구조는 논리적인 구조일 뿐, 메모리에 저장되는 물리 구조는 1차원의 선형구조가 된다.

1) 1차원 배열의 순차표현

e.g. 분기별 노트북 판매량 리스트

int[] sale = new int[] {157, 209, 251, 312};

2) 2차원 배열의 순차표현

e.g. 2007~2008년 년도별 분기별 노트북 판매량 리스트

int[][] sale = new int[][] {{63, 84, 140, 130}, {157, 209, 251, 312}};

행/열 → 물리적 저장방식: 행 우선 순서 저장 or 열 우선 순서 저장

논리 순서를 물리 순서로 변환하는 방법은 프로그래밍 언어의 컴파일러에 의해서 결정된다.

3) 3차원 배열의 순차표현

e.g. 1팀, 2팀 팀별 2007~2008년 년도별 분기별 노트북 판매량 리스트

면/행/열 물리적 저장방식: 첫번째 인덱스인 면 우선 저장 or 열 우선 저장

int[][][] sale = new int[][][] {{{63, 84, 140, 130}, {157, 209, 251, 312}}, {{59, 80, 130, 135}, {149, 187, 239, 310}}};

순차 자료구조는 인덱스를 사용하여 특정 원소에 쉽게 액세스할 수 있다. 그러나 원소를 삽입하거나 삭제할 경우에 물리적으로 원소들을 뒤로 밀어내거나 앞으로 당겨서 순서를 유지해야하기 때문에 추가적인 오버헤드가 발생하게 된다. 따라서 삽입, 삭제 연산이 많이 필요한 문제에서 순차 자료구조를 사용하는 것은 비효율적이다.

3. 다항식의 순차 자료구조 표현

다항식 (Polynomial Operator) 

계수 (coefficient),변수(variable), 지수(exponent), 항(terms), 차수(degree), 상수(constant)

<다항식 기본> https://www.mathsisfun.com/algebra/polynomials.html

1) n 차 다항식 (n+1) length 의 배열로 생성

다항식의 각 항의 계수를 정해진 인덱스의 배열 요소에 저장하여 사용하는 방법은 지수를 따로 저장하지 않기 때문에 표현하기가 쉽고 간단하다. 

i (인덱스)	[0]	[1]	...	[n-1]	[n]
e (지수)	n	n-1	...	1	0
a (계수)			...

 2) 희소 다항식

위와 같이 차수와 항의 개수 차이가 심한 희소 다항식의 경우, 크기가 (1000+1) 개인 배열을 만들어야 할까?  메모리의 낭비 문제가 발생한다. 희소 다항식의 경우 항의 개수에 따라 배열 크기를 결정하는 것이 메모리 사용면에서 효율적이다. <지수, 계수> 쌍을 2차원 배열에 저장한다.

항	[0] 지수	[1] 계수
[0]	1000	3
[1]	1	1
[2]	0	4

- 행의 개수: 희소 다항식의 항의 개수

- 각 행의 0번 열은 지수

- 각 행의 1번 열은 계수

3) 다항식의 추상자료형 

추상자료형 (ADT, Abstract Data Type): 다항식 연산에 필요한 데이터와 연산식을 유사코드로 작성한다.

- 데이터: p 다항식, e 지수, a 계수 정의

지수 () - 계수 () 의 순서쌍 <,  > 의 집합으로 표현된

다항식 

- 연산: 다항식 지수, 계수 차수 확인, 다항식 +/-/* 연산 

공백 다항식, 공백 다항식여부 확인, 지수 e에 대한 계수 a 확인,

다항식 p 에서 최대지수 e (차수) 구하는 확인

다항식 p 에 지수 e 인 항이 없는 경우 새로운 항 <e,a> 를 추가하는 연산, 

다항식 p 에 지수가 e 인 항 <e, a> 를 삭제하는 연산

두 다항식 p1 과 p2 의 합을 구하는 연산

두 다항식 p1 과 p2 의 곱을 구하는 연산

4) 다항식 연산 알고리즘 구현

연산을 구체적으로 구현한다. 구현하기 전에 알고리즘 상세를 유사코드로 작성한다.

addPoly(A, B)

// 다항식 A, B 를 더하여 다항식 C 를 반환하는 알고리즘

 

  C ← zeroP();

  

  while ( A, B 모두 공백이 아닌 경우 ) do {

   case {

   // 각 다항식을 차수 단위로 비교, 추가, 기존식에서 차수 삭제

   A 차수 < B 차수 : B 차수, 계수를 C 에 추가, B 차수 삭제

   A 차수 > B 차수 : A 차수, 계수를 C 에 추가, A 차수 삭제

   A 차수 = B 차수 : 차수와 A, B 의 계수 합을 C 에 추가, A 차수 삭제

}

  

  // 차수 비교 후 남은 나머지 추가

if (A 가 공백이면) then B 나머지 항 C 에 복사

else if (B가 공백이면) then A 나머지 항 C 에 복사

  return C;

 End addPoly() 

4. 행렬의 순차 자료구조 표현

행렬 matrix  

행과 열로 구성된 자료구조

m x n 행렬: m 개의 행, n 개의 열 

m x n 행렬	n x m 행렬

int m = 8;    // 행의 개수  

int n = 7;    // 열의 개수

int[][] matrix = new int[m][n];

2) 희소행렬 Sparse Matrix

기억 공간의 효율적인 사용을 위해서 0이 아닌 값이 있는 원소만 따로 추출하여 배열로 구성하는 방법을 사용한다.

원래의 희소행렬에 대한 정보를 저장하기 위해서 <전체 행 수, 전체 열 수, 0이 아닌 원소의 수>의 쌍을 첫번째 행으로 저장한다.

그리고 원소 정보 <행번호, 열번호, 값>을 한쌍으로 각 원소에 대해 추출, 2차원 배열에 저장한다.

3) 희소행렬의 추상 자료형

ADT Sparse Matrix

- 데이터 : 3 원소쌍 <행 인덱스, 열 인덱스, 원소값> 의 집합

- 연산: 공백행렬 생성, 전치행렬 연산, 두 행렬의 합/곱

a, b 는 희소행렬, c 는 행렬, u, v 는 원소값, i j 는행렬의 행, 열 인덱스

공백 행렬 만들기

행렬의 전치행렬 구하기

차수가 같은 행렬 a, b 의 합을 구하는 연산

a 의 열의 개수와 b 의 행의 개수가 같은 경우 두 행렬의 곱을 구하는 연산

4) 희소행렬의 전치연산 알고리즘 유사코드

희소행렬의 전치연산에 대해서 A 행/열을 B 열/행으로 바꿔치기한다.

유사코드를 작성해보고 실제 구현해본다.  (약간 교과서 예시가 이상해서 각색해보았습니다. ;0)

transposeSM(a[])

 // return c where c[j,i]=v when a[i,j]=v;

 // 전체 행, 열, 수를 확인한다.

 m <- a[0,0]

 n <- a[0,1]

 v <- a[0,2]

 

// (원소수 v + 전체행 나타내는 1) 의 행, 3개 열을 가지는 희소행렬을 생성한다.

 int[][] sparseMatrix = int[v+1][3];

 b[0,0] <- n 행 수 

 b[0,1] <- m 열 수   

 b[0,2] <- v 원소 수

 

// 원소의 수만큼 b 희소행렬로 전치한다. 

 if(v>0) then {

p <- 1;

for (i<-0; i<n; i<-i+1) do {

for (j<-1; j<=v; j<-J+1) do {

if(a[j,1] = i) then {

b[p,0] <- a[p,1];

    b[p,1] <- a[p,0];

    b[p,2] <- a[p,2];

     p <- p+1;

     }

}

}

 }

 return b[];

End transposeSM()

4) 희소행렬의 전치연산 알고리즘 구현

public int[][] transposeSM2(int[][] matrix) {

// 희소행렬 행,열,원소수 확인 

int m = matrix[0][0];

int n = matrix[0][1];

int v = matrix[0][2];

// 공백 희소행렬 생성 & default 값 세팅 

int[][] tsMatrix = new int[v+1][3]; // 5x3 matrix 

tsMatrix[0][0] = n;

tsMatrix[0][1] = m;

tsMatrix[0][2] = v;

// 원소의 수만큼 진행

int p = 1;

while(p<v+1) {

// tsMatrix 의 행 순서대로 (matrix의 열 정렬을 위해-) 

for (int i=0; i<n; i++) {

//모든 원소를 검사 

for (int j=1; j<v+1; j++) {

// 행이 값이 맞으면 tsMatrix 로 복사 

if (matrix[j][1] == i) {

tsMatrix[p][0] = matrix[j][1];

tsMatrix[p][1] = matrix[j][0];

tsMatrix[p][2] = matrix[j][2];

p++;

}

}

}

}

return tsMatrix;

}