[C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘(3) / 선형 자료 기초
배열, 동적 배열, 연결 리스트 비교
프로그래밍은 데이터를 저장하고, 그것을 꺼내서 잘 활용하는 것이 게임이고 프로그래밍인 것이다.
자료 구조는 크게 선형 자료구조와 비선형 자료구조로 나눌 수 있다.
선형 구조 : 자료를 순차적으로 나열한 형태
- 배열
- 연결 리스트
- 스택 / 큐
비선형 구조 : 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태.
- 트리
- 그래프
ex) 파일구조
자료구조와 알고리즘을 공부할 때
자료구조와 알고리즘은 책으로 복잡하게 외우는 것은 쓸모가 없다. 애초에 이 학문은 실생활 문제를 해결하고 도움을 주기 위해 발전한 학문이기에, 최대한 현실상황에 맞게 생각을 하면서 어떤 식으로 언제 활용할 것인지 공부하는 것이 오래 남는다.
배열
- 사용할 방 개수를 고정해서 계약하고 (절대 변경 불가)
- 연속된 방으로 배정받아 사용
장점 : 연속된 방
단점 : 방을 추가 / 축소 불가
유동적으로 상황에 맞추어 사용할 수 없다는 것이 배열의 가장 큰 문제이다.
동적 배열
- 연속된 방을 배정받아 사용하겠다. (여기까진 일반 배열과 같음.)
- 확장이 가능하다. (이것이 배열과 차이점)
문제점 :
다른 메모리가 사용 중일 수 있기에 이사를 가야 한다. 즉, 호텔 호실로 예를 들자면 101, 102, 103호를 사용하고 있는 와중에 104호까지 추가적으로 사용하고 싶다. 그러나 104호에는 이미 다른 사람이 사용하고 있다.
이럴 때는 이사를 요청해서 301, 302, 303, 304호를 쭈르륵 잡은 다음에 손님들에게 이사를 요청하는 것이다. 새로 온 친구는 304호에 들어간다.
문제라기보다는 부담이 있는데, 이사비용이 있다는 것이다. 그래서 동적 배열을 사용할 때는 어떻게든 이사비용을 줄이는 것을 강구해야 한다. (이사의 횟수도 고려하는 것이 중요함.)
위 문제를 해결하기 위해 다음과 같은 방법을 사용한다.
동적 배열 할당 정책 :
- 실제로 사용할 방보다 많이, 여유분을 두고 (대략1.5 ~ 2배) 예약
- 이사 횟수를 최소화 => 동적 배열의 핵심적인 내용
(이사 횟수를 줄이기 위해) 만약 이사를 하게 될 때 방이 4개 필요하다면 여기서 또 2개를 더 추가로 예약을 해서 방을 사용한다.
데이터가 많아지면 많아질수록 여유분 데이터가 많아지기에 이사 횟수가 점점 줄어들게 된다는 장점이 있다.
코드로 구현할 때도 이 부분을 자세하게 살펴보자.
동적 배열
- 사용할 방 개수를 유동적으로 계약
- 연속된 방으로 배정받아 사용
장점 : 유동적인 계약(방 추가 예약으로 이사 횟수 초기화)
단점 : 중간 삽입/삭제
단점에 대해 조금 더 자세히 설명하자면, 모든 사람들은 다 연속된 방을 사용해야 한다. 그런데, 중간의 방이 비어버리면 어쩔 수 없이 중간의 빈 공간을 매꾸는 식으로 이사를 한다. (중간에 삽입되는 경우도 똑같음.)
연결 리스트
- 연속되지 않은 방을 사용. (핵심)
장점 : 중간 추가 삭제 이점
단점 : N번째 방을 바로 찾을 수가 없음 (임의 접근 Random Access 불가)
동적 배열 구현 연습
로그라이크 게임을 만든다고 가정할 때, 맵 안에 어떤 특정 점이 사라졌다 생겼다 할까? 그것은 아님. 갑자기 있던 공간이 사라지지 않음. 그러면 연결 리스트를 사용하는 것이 썩 좋진 않을 수 있음.
그러면 배열과 동적 배열을 고민해봐야 할 텐데 뭐가 좋을까?
동적 배열의 장점은 배열의 사이즈를 유동적으로 늘렸다, 줄였다 할 수 있음. 그러나 이것도 마찬가지로 맵 사이즈가 게임을 하던 와중에 커졌다 작아졌다 할까? 특별한 기획이 있는 것이 아닌 이상 이것도 아님.
결국 배열을 사용하는게 합리적인 것 같음.
동적 배열은 기본기기에 연습을 한 번 해보자.
동적 배열 사용하기
- Add연산을 통해 값 추가하기.
- 동적 배열 접근하기.
이것이 표준 사용법.
동적 배열 제작하기
동적 배열을 사용할 때 제너릭 타입인 것을 확인할 수 있다.
class MyList<T>
{
const int DEFAULT_SIZE = 1;
T[] _data = new T[DEFAULT_SIZE]; // 실제로 빈 리스트를 만들었을 때 크기가 1인지는 모르겠지만 임의로 설정.
public int Count = 0; // 실제로 사용중인 데이터 개수
public int Capacity { get { return _data.Length; } } // 예약된 데이터 개수 (동적 배열은 여유분으로 메모리를 더 잡아놓기 때문.)
public void Add(T item)
{
// 1. 공간이 충분히 남아있는지 확인한다.
if (Count >= Capacity)
{
// 공간을 다시 늘려서 확보한다.
T[] newArray = new T[Count * 2]; // 2라는 것은 Growth Factor라고 해서 어떻게 배열 크기를 증가시킬 것이냐라는 정책
for (int i = 0; i < Count; i++)
newArray[i] = _data[i];
_data = newArray; // 이러면 newArray배열 시작주소가 _data에 할당된다.
}
// 2. 공간에다가 데이터를 넣어준다.
_data[Count] = item;
Count++;
}
public T this[int index]
{
get { return _data[index]; }
set { _data[index] = value; }
}
/// <summary>
/// 101 102 103 104 105번지를 쓸 때 103번을 없애면
/// 101 102 104 105 105가 된다. 그래서 default(T)를 통해 105도 날린다.
/// (뭐 사실 다른값이 들어갈꺼니 굳이 안밀어도되겠지만 찝찝하니까 민다.)
/// </summary>
/// <param name="index"></param>
public void RemoveAt(int index)
{
// Count - 1인지 Count인지 헷갈리긴 하는데, 이 조건 자체가 i가 Count -1보다 작을 때 들어올 수 있다.
// 즉 Count - 2인데, 그러면 _data[i+1]에 들어갈 수 있는 가장 큰 값이 Count-2인데
// Count - 2 + 1을 하면 Count - 1이다. 그리고 배열의 마지막 유효한 데이터는 Count - 1이니까,
// Count - 1이 배열의 끝을 가리키는게 맞다.
for (int i = index; i < Count - 1; i++)
_data[i] = _data[i + 1];
_data[Count - 1] = default(T); // T라는 형식으 ㅣ초기값으로 마지막의 안쓰는 배열을 밀어버림.
Count--;
}
}
시간복잡도 분석을 해보자.
//O(1) 예외 케이스 : 이사비용은 무시한다.
public void Add(T item)
{
// 1. 공간이 충분히 남아있는지 확인한다.
if (Count >= Capacity)
{
// 공간을 다시 늘려서 확보한다.
T[] newArray = new T[Count * 2]; // 2라는 것은 Growth Factor라고 해서 어떻게 배열 크기를 증가시킬 것이냐라는 정책
for (int i = 0; i < Count; i++)
newArray[i] = _data[i];
_data = newArray; // 이러면 newArray배열 시작주소가 _data에 할당된다.
}
// 2. 공간에다가 데이터를 넣어준다.
_data[Count] = item;
Count++;
}Add함수는
for문 때문에 O(n) 같지만 데이터가 두 배씩 늘어나기 때문에 실행되지 않는다고 가정을 하고, 시간복잡도 계산을 할 때는 무시를 한다. 그래서 뒤에 데이터 값넣는 것만 고려를 하면 상수시간인 O(1)로 친다. (예외 케이스 : 이사 비용은 무시한다.)
// O(1)
public T this[int index]
{
get { return _data[index]; }
set { _data[index] = value; }
}볼 것도 없이 연산이 1개 짜리니 상수시간.
// O(N)
public void RemoveAt(int index)
{
// Count - 1인지 Count인지 헷갈리긴 하는데, 이 조건 자체가 i가 Count -1보다 작을 때 들어올 수 있다.
// 즉 Count - 2인데, 그러면 _data[i+1]에 들어갈 수 있는 가장 큰 값이 Count-2인데
// Count - 2 + 1을 하면 Count - 1이다. 그리고 배열의 마지막 유효한 데이터는 Count - 1이니까,
// Count - 1이 배열의 끝을 가리키는게 맞다.
for (int i = index; i < Count - 1; i++)
_data[i] = _data[i + 1];
_data[Count - 1] = default(T); // T라는 형식으 ㅣ초기값으로 마지막의 안쓰는 배열을 밀어버림.
Count--;
}우선 마지막 두 줄라인은 상수시간이라 무시.
index가 마지막 값이라서 한 번만 실행하는 경우도 있을 것이고, 운 나쁘게 0이여서 처음부터 시작했다면 가장 많이 돌텐데 어떻게 계산해야 할 지 헷갈릴 수 있다.
보통 이럴 떄는 그냥 최악의 경우만 생각하면 된다.
그러면 결론은 O(N)으로 시간복잡도를 생각할 수 있다.
정리
동적배열에 관련해여 정리하자면, 실제 사용되는 데이터 개수와 예약된 데이터 개수를 분리해서 사용한다.
(여유분을 두고 사용한다.) 여태껏 사용하던 공간이 꽉 차면 크기를 늘려 큰 공간을 할당한다. 그래서 데이터가 많아지면 많아질 수록 데이터를 재할당 하는 횟수가 줄어들게 된다. 그래서 Add를 할 때는 상수시간으로 계산한다.
연결리스트