2.1 선형 데이터 구조(배열)

2. 선형 데이터 구조

2.1 배열 (개념, 특징, 장단점, 종류, 연산 및 응용)

2.1.1 배열의 개념

-> 여러 개의 동일한 데이터 타입의 데이터를 연속된 메모리 공간에 한 번에 만들 때 사용 된다.

( int a1, a2, a3, a4, a5, a6 == int A[6])

-> 배열은 <인덱스, 요소>의 집합이다. 즉 인덱스를 사용하여 요소에 직접 접근할 수 있다.

    ex) int A[5] = {0,5,4,2,4}  

-> int A[3]의 인덱스를 사용하면, 2라는 정수형 데이터 요소에 접근할 수 있다. 

  

 

2.1.2 배열의 장점과 단점

장점	단점
인덱스를 이용하여 원하는 데이터요소를  빠르게 찾을 수 있다. ( O(1) )	1) 자료의 삽입과 삭제가 비효율 적이다. (삽입과 삭제시 모든 요소를 이동 시켜야 한다.)   삽입) 배열에 ABCDE가 저장되어 있고, B 다음에 N을 삽입하려면 C,D,E를 한칸씩 이동해야 한다.   삭제) 배열에 ABCDE가 있고, C를 삭제 하려면, C를 삭제하고 작업을 완료할 수 있지만, 그러면 배열에는 처리되지 않아야 할 정보(Null)가 포함되므로 이를 없애 주어야 한다. 그렇기 때문에 C를 삭제하고 D,E를 한 칸씩 앞으로 이동해주어야 한다
	2) 한번 선언된 배열은 크기를 늘리거나 줄일 수 없다. (배열을 사용할 때 크기가 고정이므로 사용할 데이터 양을 예측하여 배열을 선언하기 때문에 메모리 공간이 낭비되는 경우가 많다.)

 

 

2.1.3 배열의 특징

(1) 배열의 인덱스는 0번부터 시작한다.

(2) 배열의 이름은 배열의 첫번째 배열 요소의 주소가 된다.

 

2.1.4 배열의 종류

(1) 1차원 배열

   -> int A[3]은 3개의 정수형 데이터를 저장하는 공간을 의미 한다. (인덱스는 0,1,2로 접근)

   -> 배열의 인덱스는 0부터 시작 한다.

   -> 배열의 이름 A는 A[0]의 기본주소가 된다.

1차원 배열의 요소	1차원 배열의 메모리 주소
A[0]	기본주소 = Base               /  1024로 가정
A[1]	Base + 1 * sizeof(배열 자료형)   /  1024 + 1*4 = 1028
A[2]	Base + 2 * sizeof(배열 자료형)   /  1024 + 2*4 = 1032

 

(2) 2차원 배열

   -> 1차원 배열이 여러 개 모여서 이루어진 배열이다.

   -> 가로줄을 행, 세로줄을 열이라고 한다.

(int A[2][3] 이면 2행 3열의 배열이 있는 것이다.)

2차원 배열의 요소	2차원 배열의 메모리 주소
A[0][0]	기본주소 = Base               /  1024로 가정
A[1][0]	Base + (행 번호 * 한 행이 가질 수 있는 열의개수 * sizeof(배열 자료형) ) + (열 번호 * sizeof(자료형) ) / 1024 + (1 * 3 * 4) + (0 * 4) = 1036
A[2][2]	Base + (행 번호 * 한 행이 가질 수 있는 열의개수 * sizeof(배열 자료형) ) + (열 번호 * sizeof(자료형) ) / 1024 + (2 * 3 * 4) + (2 * 4) = 1056

* 추신 : 배열의 연산 및 응용 부분은 심화 부분입니다. 

          기초가 부족하다 싶으시면 추후에 보시길 바랍니다.

2.1.5 배열의 연산 및 응용 / 다항식

-> 배열의 응용이란 수학에 나오는 다항식을 배열을 이용하여 표현하는 것을 말한다.

 

(1) 배열의 응용 : 다항식

 -> 4x^2 + 6 = 12 (4는 계수, x는 변수, ^2는 차수, 6과12는 상수)

    -> 다항식에서 가장 큰 차수를 그 다항식의 차수라고 부른다. (여기서는 차수가 2)

    -> 이러한 다항식을 프로그램 안에 표현하고 연산할 때 어떤 자료구조를 이용할 것인지 

        알아보자.

 

(2) 다항식 표현의 첫 번째 방법

    -> 다항식의 모든 차수에 대한 계수 값을 배열에 저장.

    -> 다항식 예시 )  10x^5 + 6x +3  -->  10x^5 +  0 * x^4  +  0 * x^3  +  0 * x^2  +  6x + 3

    -> 위의 다항식에서 모든 차수에 대한 계수 값들의 리스트인 ( 10, 0, 0, 0, 6, 3) 을 배열 coef에 

        저장하는 방법을 사용한다.

    -> 여기서 다항식의 최고 차수는 변수 degree에 저장 한다.

 

 

(3) 첫번째 방법의 장점

      -> 다항식의 덧셈이나 뺄셈 시에 같은 차수의 계수를 쉽게 찾을 수 있으므로 알고리즘이 

          간단해 진다.

(4) 첫번째 방법의 문제점

      -> 다항식의 항의 계수가 0인 희소 다항식의 경우 공간의 낭비가 심하다. 

         ( 10x^100 + 6의 경우 101개 공간 중 단 2개만 사용된다.)

  * 추신 : 다항식의 최고차 항부터 배열에 차례대로 저장되어 있음을 유의하라.

(5) 다항식 덧셈 프로그램 코드 및 해설

 

 

  1) 구조체 A, B의 coef 배열을 스캔 하면서 차수가 큰 항을 구조체 C로 이동한다.

  2) 차수가 같으면 구조체 A,B의 coef 배열 값을 더하여 C의 coef에 대입한다.

  3) 2개의 다항식 모두 차수가 최고 차 항에서 0까지 존재하므로 while 루프가 끝나면 모든 항들이 

     처리되는 것이 보장 된다.

 

 

 

 

(6) 두번째 방법

-> 두번째 방법은 다항식에서 0이 아닌 항만을 하나의 전역 배열에 저장하는 방법이다.

-> 다항식의 0이 아닌 항들은 (계수, 차수)의 형식으로 구조체 배열에 저장 된다.

-> 즉 10x^5 + 6x + 3의 경우 ( ( 10, 5), ( 6, 1), (3, 0) ) 으로 표시하는 것이다.

-> 이 방식을 이용하면 배열에 하나 이상의 다항식을 저장할 수 있다.

(7) 두번째 방법의 다항식 표현

-> A = 8x^3 + 7x + 1, B = 10x^3 + 3x^2 + 1

-> avail 변수는 현재 비어 있는 요소의 인덱스를 가리킨다.

(8) 두번째 방식의 단점

-> 우선 하나의 다항식이 시작되고 끝나는 위치를 가리키는 변수를 관리해야 한다.

-> 또한 차수도 저장해야 하기 때문에, 다항식에 따라서 계수만을 저장하는 첫 번째 방식보다 

    공간을 더 많이 필요할 수 있다.

 

(9) 두번째 방법의 덧셈 알고리즘

1) 두개의 다항식 A, B를 더하여 다항식 C를 구하려고 한다

2) 우선 A와 B의 각 항의 차수를 비교하여 차수가 같으면 A와 B의 각 항의 계수를 더하여 

   C로 옮긴다.

3) 차수가 다르다면 A와 B중 차수가 큰 항을 C로 옮기면 된다.

4) 이와 같은 과정을 어느 한쪽 다항식이 끝날 때 까지 계속 한다.

 

(10) 두번째 방법의 덧셈 알고리즘 구현

 

 

1) As와 Ae는 다항식 A의 처음과 마지막을 가리킨다.

2) attach 함수는 해당 항목을 배열 terms의 다음 빈 공간에 더하는 함수이다. 이때 avail 변수가 증가 된다.

2.1.6 배열의 연산 및 응용 / 희소행렬

   

   0 0 0 1 0 2

   0 6 0 0 0 0

   0 0 0 7 0 0

   -> 예를 들어 위와 같은 행렬 A가 있다고 하자.

-> 행렬 A는 많은 항들이 0으로 되어 있고, 이는 희소 행렬이라고 한다.

-> 이것은 메모리의 불필요한 낭비를 가져온다. 따라서 데이터가 0이 아닌 값만 저장할 필요가 있다.

​

  (1) 희소행렬 표현법

3 6 4 ---------> 3은 희소행렬의 전체 행의수, 6은 전체 열의수, 4는 0이 아닌 데이터의 개수

0 3 1 ---------> 둘째줄은 0이 아닌 데이터의 행과 열의 위치와 데이터 값 표시(행,열,값)

0 5 2

1 1 6

2 3 7

  --> 일반 적인 행렬 표현 법보다 더 적은 메모리 공간으로 표현이 가능 해진다.

 

(2) 일반행렬을 희소행렬로 바꾸는 함수

 

(3) 희소행렬의 전치행렬

  -> 전치행렬이란 기존의 행렬에서 행과 열의 위치를 바꾼 행렬을 말한다.