[C# 자료구조]배열(Array)

2. 배열(Array)

2.1 배열의 기초개념

배열 : 연속적인 메모리 상에 동일한 데이터 타입의 요소들을 순차적으로 일렬로 저장하는 자료구조

• 하나의 배열은 고정된 크기를 가지며, 배열 인덱스를 사용할 경우 각 배열요소를 즉시 엑세스할 수 있음
  예를 들어 배열 A가 100개의 배열요소가 있을 때, A[0], A[50],A[99]등을 엑세스 하는 시간은 동일함.
  모든 해당 요소를 즉시 엑세스하여 배열요소 값을 읽거나 쓸 수 있음.

• 배열은 거의 대부분의 프로그래밍 언어에서 사용할 수 있는 가장 기초적인 자료구조로서, C# 프로그래밍 언어도 물론 배열을 기본적으로 지원함. (주: C/C++에서의 배열이 연속적인 메모리 공간에 대한 주소를 의미한다면, C#에서의 배열은 배열 객체로서 메모리 상의 배열에 대한 정보를 가지며 System.Array클래스로부터 생성되어 System.Array 클래스의 속성과 메서드를 사용할 수 있는 객체 인스턴스이다.)

- 배열의 차원(Dimension) : 한 배열요소를 선택하기 위해 사용하는 인덱스의 수

• 배열 A의 배열 요소가 10개이고 이를 메모리 상에 일렬로 저장하면 아래와 같이 표현할 수 있다. 각 요소는 0부터 시작하는 배열 인덱스를 갖는데, 예를 들어 배열 A의 첫 번째 배열요소는 A[0]이고, 두 번째 요소는 A[1]로 표현한다. (주: 이렇게 배열 인덱스가 0부터 시작하는 것을 Zero-based Indexing이라고 부른다. 인덱스는 0(Zero-based Indexing), 1(One-based Indexing), 또는 n(n-based indexing) 부터 시작할 수 있는데, 많은 프로그래밍 언어가 Zero-based Indexing을 사용함.
• ex) Int[]A = new int[10];

2차원 배열은 행(row)와 열(column)을 갖는다. 배열요소를 선택하기 위해 행과 열 2개의 인덱스가 필요하다.

Int[,]A = new int[3,4];
C#은 1차원 배열을 비롯하여 2차원, 3차원, ... 32차원 배열까지를 지원한다

2.2 가변 배열(Jagged Array)

가변배열은 그 배열의 배열 요소가 배열 타입인 경우를 말하는데, 각 배열 요소는 서로 다른 차원과 크기를 갖는 배열일 수 있다. C#에서 일반 다차원 배열의 경우 [,]와 같이 콤마로 차원을 분리하는 반면,
가변 배열은 [][]와 같이 "배열의 배열"처럼 사각괄호를 겹쳐서 차원을 표현한다. 가변 배열은 일반 다차원 배열로 했을 때 공간의 낭비가 심해지는 경우, 혹은 각 차원마다 다른 배열 크기를 가져야 하는 경우 특히 유용함

int[][]A = new int[3][];
A[0] = new int[2];
A[1] = new int[6]{1,2,3,4,5,6}
A[2] = new int[3]{9,8,7}

2.3 동적 배열(Dynamic Array)

배열은 일정한 크기의 연속된 배열요소들의 집합이고, 배열의 크기는 초기화시 미리 지정된다.
정적 배열(Static Array)은 이렇게 처음 지정한 고정 크기를 그대로 계속 유지하는 배열이다.
C#에서 기본적으로 사용하는 배열 문법, 즉 int[], string[,]같은 식으로 선언된 배열들은 모두 정적 배열에 해당한다.

하지만 배열의 최대 크기를 미리 알 수 없는 경우도 있고, 필요시 배열을 중간에 확장해야 하는 경우도 있다.

이래서 동적 배열이 있다.

public class DynamicArray
{
   private object[] arr = new object[0];  //기존 배열 arr


   public void Add(object element)
   {
       var temp = new object[arr.Length + 1]; //기존 배열arr의 크기보다 1개 더 큰 임시 배열 temp생성
       for (int i = 0; i < arr.Length; i++)  // 기존 배열 arr의 모든 요소를 임시 배열 temp로 복사
       {
           temp[i] = arr[i];  //
       }
       arr = temp;  // 기존배열 arr을 임시 배열 temp로 교체

       arr[arr.Length - 1] = element;  //임시배열 temp의 마지막 요소에 새 요소를 추가함
   }


}
public class DynamicArrayProcess
{
   public static void Main(string[] args)
   {
       var elementAdd = new DynamicArray();
       elementAdd.Add("Hello");

       
   }
}

동적 배열을 만드는 가장 간단한 방식은 새로운 요소가 추가될 때마다 배열 크기를 하나씩 늘려나가는 것이다.
즉, 아래 예제와 같이 새 배열요소를 추가할 때 기존 배열(arr) 의 크기보다 1개 더 큰 임시 배열 (temp)을 생성하고, 임시 배열에 모든 요소를 복사한 후, 다시 임시 배열(temp)을 기존 배열(arr)에 할당하고, 배열 마지막 요소에서 새 배열요소를 추가하는 것이다.

이것의 장점 : 필요할 때마다 배열을 하나씩 동적으로 증가시키는 방식으로 꼭 필요한 공간만을 사용한다

이것의 단점 : 매번 새로운 배열 공간을 생성하고 여기에 기존 배열요소들을 전부 복사해 넣어야 한다. 배열의 크기가 n일때 O(n)의 시간이 소요된다. 예를 들어, 배열의 크기가 1일때 새 요소를 추가하면 기존 배열 요소 1개를 복사해야 하고, 배열 크기가 2일 때는 2개를, 3일 때는 3개를 복사해야 한다. 이러한 방식으로 임의의 배열크기가 n일때, n개를 복사하는 동작을 수행하여야 한다.

이와 같은 단점을 해결하기 위해 흔히 사용하는 동적 배열의 구현 방식은 배열을 2배씩 확장하는 것이다. 즉, 배열 확장이 필요한 경우 배열 크기가 2배인 새로운 임시 배열을 생성하고 모든 기존 배열 요소들을 새 임시 배열에 복사한 후 기존 배열을 해제하는 방식이다. 아래는 이러한 방식으로 구현한 동적 배열의 예제이다.

public class DynamicArray
{
   private object[] arr;
   private const int GROWTH_FACTOR = 2;  //상수 GROWTH_FACTOR 선언
                               //성장인자 ; 배열이 꽉 찼을 때, 배열을 얼마만큼 늘려야 하는가를 정하는 인자
                               //각 각 라이브러리/Framework마다 다르지만 통상 2배 혹은 1.5배를 많이 사용

   public int Count   //Count 프로퍼티  ; 현재 배열요소 수 
   {                       
       get;
       private set;  //해당 필드값을 읽기전용.
   }

   public int Capacity   //Capacity 프로퍼티 ; 최대 수용가능 용량
   {
       get
       {
           return arr.Length;
       }

   }

   public DynamicArray(int capacity = 16)  //capacity 기본값을 가지는 매개변수를 가진 메소드
   {
       arr = new object[capacity];
       Count = 0;
   }

   public void Add(object element)
   {
       //Count가 Capacity보다 크거나 같으면 즉 배열이 꽉 차면 => 배열을 (Growth Factor 만큼) 2배로 확장하고 새 배열요소 추가
       if (Count >= Capacity)     
                                 
       {
           int newSize = Capacity * GROWTH_FACTOR;
           var temp = new object[newSize];
           for (int i = 0; i < arr.Length; i++)
           {
               temp[i] = arr[i];
           }
           arr = temp;
       }

       arr[Count] = element;
       Count++;
   }

   public object Get(int index)
   {
       if (index > Capacity - 1)
       {
           throw new ApplicationException("Element not found");
       }
       return arr[index];
   }


}

위 예제 같은 경우,
처음 배열의 크기는 16, 다음 확장 시 32, 그 다음 확장 시 64 등으로
2배씩 증가함.

따라서, 배열인덱스 0~15 : 새 요소를 추가할 때 즉시 추가
17 : 배열크기 32인 새 배열로 확장한 후, 16개의 기존요소들을 복사

일부 수행에서 일어나는 비싼 수행 비용을 분산시켜 여러 다른 일반 수행들로 분할 상환하여 비용을 계산하는 방식을 분할상환분석(Amortized Analysis)이라 부른다.

이러한 분석을 통해 배열을 하나씩 증가하는 동적 배열 방식(수행시간이O(n))보다 배열을 2배 혹은 1.5배로 증가하는 방식(수행시간이 O(1))이 훨씬 효율적임을 알 수 있다.

2.4 원형 배열(Circular Array)

원형 배열은 고정된 크기의 배열을 마치 양 끝이 연결된 것처럼 사용할 수 있게 한 자료구조로서, 흔히 원형버퍼(Circual Buffer), 링 버퍼(Ring Buffer)라고도 불리운다. 즉, 배열의 크기가 N일 때, 배열의 마지막 요소(N-1)에 도착하면, 다음 배열요소는 첫 번째 요소(0)로 순환하는 구조이다.

원형 배열은 처음 들어간 데이터가 먼저 나오는 FIFO(First in first out)구조의 데이터 버퍼에 적합하며, 비원형의 일반 배열은 마지막에 들어간 데이터가 먼저 나오는 LIFO(Last in first out)구조의 버퍼에 적합하다. 원형 배열은 FIFO구조를 가진 큐(QUEUE)를 구현하거나 데이터 스트맄 버퍼 등을 구현할 때 흔히 사용되곤 한다.

원형 배열에서 배열 자체는 고정된 크기를 갖는 일반 배열과 동일하지만, 이를 특별한 방식으로 사용하는 것이라고 할 수 있다. 원형배열은 배열을 순환하는 구조로 만들어야 하므로, 배열 인덱스를 증가시킬 때 mod 연산자를 사용하여 마지막 배열의 다음 인덱스가 첫 배열 인덱스로 돌아오게 한다.

C#에서 mod연산자는 %로 표시되고 나머지를 구할 때 사용되는데, 예를 들어 10 % 8 은 10을 8로 나눈 나머지 즉 2가 된다.

이러한 mod 연산자를 사용하여 원형배열의 인덱스 증가를 다음과 같이 표현할 수 있다.

index = (index + 1) % A.Length;

위 표현식을 사용하여 ,A[7] 요소를 읽고 다음 요소로 이동한다면, (7+1) % 8 = 0
즉, A[0] 배열 요소로 이동하게 된다.

원형 배열에 보다 익숙해 지기 위해 간단한 사례를 들어보자.

원형탁자에 8명의 사람이 앉아 있다. 각 사람의 명칭은 위에서부터 시계 방향으로 a,b,c,d,e,f,g,h라고 가정하자. 이때, 임의의 사람을 선택해서 그 사람으로부터 시계 방향으로 모든 사람들의 명칭을 순서대로 출력하는 프로그램을 만들어보자. 이 문제를 해결하는 간단한 방법은 abcdefgh 전체를 한번 더 추가해서 뒤에 붙이는 방식이다. 즉, abcdefghabcdefgh와 같이 하면 임의의 시작 인덱스에서부터 순서대로 8개를 읽으면 된다. 예를 들어 c로부터 시작한다면 abcdefghabcdefgh를 읽으면 된다. 그러나, 이러한 방식의 단점은 배열의 크기만큼 중복된 공간이 필요하고 현재의 배열을 중복 복사해야 한다는 점이다. 이러한 중복 복사 방식보다 더 효율적인 방식으로 원형 배열을 사용할 수 있다. 즉, 배열에 a,b,c,d,e,f,g,h를 넣고, 배열 인덱스를 순환하도록 조정하면, 임의의 인덱스에서 시작하여 N개를 순차적으로 출력할 수 있다. 아래 예제는 이를 구현한 샘플이다.

2.5 NET의 배열 클래스

.NET Framework은 고정 배열과 동적 배열을 지원한다.
.NET의 고정 배열은 1차원 배열부터 32차원 배열까지 지원하고, 디폴트로 배열은 최대 2GB까지의 크기를 가질 수 있다. 디폴트로 배열은 최대 2GB까지의 크기를 가질 수 있다. 단, 64bit 환경에서는 app.config에서 gcAllowVeryLargeobjects값을 enable하면 2GB보다 큰 배열을 가질 수 있다. .NET의 고정 배열은 모두 System.Array 추상 클래스부터 파생되는데, 이 클래스는 컴파일러나 시스템에서만 파생클래스를 만들 수 있기 때문에, 개발자가 System.Array로부터 직접 파생클래스를 만들 수 는 없다.

.NET Framework에는 동적 배열을 지원하는 클래스로 ArrayList와 List가 있다. ArrayList는 object 타입의 동적 배열을 가지며, List는 개발자가 임의의 타입(T)을 지정할 수 있는 Generic타입의 동적 배열이다. 예를 들어, List는 정수형 동적 배열이며, List는 문자열 동적 배열이다. 아래 예제는 List 동적배열에 1부터 17까지의 숫자를 차례대로 넣어 본 것으로, 이 동적 배열은 초기 배열 크기가 4이며, 8, 16, 32, ... 등으로 2배씩 증가함을 볼 수 있다.