C# 자료구조 (배열의 활용)
전 페이지에서는 기본적인 배열을 설명했으니 이번엔 배열을 한번 활용을 해보겠다.
동적 배열 (Dynamic Array)
배열은 초기화 할때 배열의 크기를 먼저 정하기 떄문에 처음에 지정한 고정크기를 유지하게 된다.
하지만 코드를 실행하면서 크기를 늘려야되는 상황도 생길것이고 미리 크기를 알수 없어서 생성 할수도 없을수도 있다.
이렇게 배열이 꽉차서 추가를 해야하거나 배열의 크기가 작아져서 축소를 하기위한 기능을 만든게 동적배열이라고 할수있다.
코드를 적어보겠다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 동적배열
{
public class DynamicArray<T>
{
private T[] arr;
private const int GROWTH_FACTOR = 2;
public int Count { get; private set; }
public int Capacity
{
get { return arr.Length; }
}
public DynamicArray(int capacity = 16)
{
arr = new T[capacity];
Count = 0;
}
public void Add(T element)
{
//배열이 찼을 때 확장
if (Count >= Capacity)
{
int newSize = Capacity * GROWTH_FACTOR;
var temp = new T[newSize];
for (int i = 0; i < arr.Length; i++)
{
temp[i] = arr[i];
}
arr = temp;
}
arr[Count] = element;
Count++;
}
public T Get(int index)
{
if (index > Capacity - 1 || index >= Count)
{
throw new AccessViolationException("Element not found");
}
return arr[index];
}
}
class Program
{
static void Main(string[] args)
{
DynamicArray<int> arr = new DynamicArray<int>();
arr.Add(5);
arr.Add(2);
arr.Add(7);
}
}
}
DynamicArray 클래스에선 처음에 모든 타입을 받을수 있는 T타입 배열 변수만 적고
GROWTH_FACTOR 은 우리가 추가해야하는 배열을 * 2 를 하기 위해서 만든 상수이다.
이렇게 한 이유는 배열을 일일이 추가를 해야할때 일일히 배열들을 복사해서 하게되면 시간복잡도는 O(n)이며 메모리가 계속 낭비가 된다.
하지만 처음의 크기를 널널하게 생성을 하고 추가를 하면 추가할때 즉시 빈공간에 추가를 할수있게 되면서 시간복잡도는O(1)로 축소 시킬수 있다.
배열의 사이즈가 꽉찰때만 O(n)으로 2배를 다시 추가하고 다시 O(1)으로 빈 배열크기에 추가하게된다.
DynamicArray를 생성할때 미리 16크기를 정한 매개변수를 넣고 배열을 생성하게 한다.
Count 프로퍼티는 현재 배열이 얼마나 추가했는지 확인하는 프로퍼티이고
Capacity 프로퍼티는 우리가 처음에 지정한 배열의 크기를 나타내는 프로퍼티이다.
Add() 메서드는 현재 배열의 마지막 인덱스에다 추가해야하는 요소를 넣을때 호출하는 메서드로 Count가 Capacity보다 숫자가 높거나 같을때 다시 2배로 크기를 생성하고 복사하며 그러지 않을때는 현재 Count 프로퍼티 인덱스에다 전달받은 인자값을 추가를 하고 ++하게된다.
Get() 메서드는 생성했던 배열의 특정 인덱스를 출력할때 호출하는 메서드로 매개변수 index가 Count OR Capacity - 1보다 크면 예외처리를 하게 하였다.
원형 배열 (Circular Array)
고정된 크기의 배열을 마치 양 끝이 연결된 것처럼 사용할 수 있게 한 자료구조
흔히 원형 버퍼(Circular Buffer), 링 버퍼(Ring Buffer)라고 불리운다.
마지막 배열 인덱스를 도착할때 다음 인덱스를 첫번째 인덱스로 순환하는 구조이다.
원형 배열은 배열 자체는 고정된 크기를 갖는 일반 배열과 같지만 사진으로 보았듯이 배열을 순환하게 만들어야 하므로
배열 인덱스를 증가시킬때 나머지 연산자를 이용하여 마지막 배열의 다음인덱스를 돌아오게 하기위해 나머지가 0으로 떨어져야 한다
이런 형태로 코드를 쓸수있다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 원형배열
{
class Program
{
static void Main(string[] args)
{
char[] arr = "abcdefgh".ToCharArray();
int selectNumber = 8;
for (int i = 0; i < arr.Length; i++)
{
int index = ((selectNumber -1) + i) % arr.Length;
Console.WriteLine(arr[index]);
}
}
}
}
이렇게 코드를 짜면 마지막 인덱스에는 0으로 나누어 떨어지기 때문에 selectNumber 변수에 arr 배열 크기에 한해서는 어떤 숫자를 넣어도 무조건 한번씩 순환을 해서 출력하게 된다.