1. 자료 구조
프로그래머로서 컴퓨터를 다루기 위해서, 데이터를 적절히 배치하고 사용할 수 있는 능력이 필요할 것이다. 특히나 게임 프로그래머로서 게임의 운영이나 최적화 등을 해야 하는 상황을 생각하면, 효율적인 데이터 관리 능력이 필요할 것이다.
상황에 따라 더 빠르고 효율적인 자료 구조를 선택하고, 데이터를 관리하는 방법에 대해 알아보자.
1.1) 자료 구조란?
- 자료구조
-프로그래밍에서 데이터를 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.
-데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다
- 자료구조의 형태
- 선형 구조 : 자료간 관계가 1 대 1 인 구조
ex) 배열, 연결리스트, 스택, 큐, 덱
- 비선형 구조 : 자료간 관계가 1 대 다 혹은 다 대 다 인 구조
ex) 트리, 그래프
1.2) 알고리즘
알고리즘(algorithm)의 사전적인 의미를 살펴보자면, 문제를 해결하기 위한 일련의 절차나 방법을 의미한다. 특히나 컴퓨터에서의 알고리즘은 어떠한 행동을 하기 위해서 만들어진 프로그램 명령어의 집합으로 볼 수 있다. 우리는 앞으로도 컴퓨터를 이용한 문제 해결을 위한 과정을 거칠 것이다. 따라서 문제 해결 방법을 적절하고 효율적으로 짜는 것이 중요할 것이다.
알고리즘 성능
-효율적인 문제 해결을 위해선 알고리즘의 성능을 판단할 수 있는 기준이 필요하다.
-상황에 따라 적합한 알고리즘을 선택할 수 있도록 하는 기준이 필요하다.
알고리즘마다 성능의 차이가 있고, 장단점이 있을 것이다. 다만 특정 상황에서 어떤 알고리즘이 사용하기 좋은지 판단할 수 있는 기준이 필요할 것이다.
알고리즘 평가 기준
컴퓨터에서 알고리즘과 자료구조의 평가는, 시간과 공간 두 자원을 얼마나 소모하는지에 대한 효율성을 중점으로 두고 판단한다. 또한 일반적으로 시간을 위해 공간이 희생되는 경우가 많다.
- 시간복잡도 : 알고리즘의 시간적 자원 소모량
- 공간복잡도 : 알고리즘의 공간적 자원 소모량
이러한 알고리즘의 평가 기준으로서 Big-O 표기법에 대해 배워보고자 한다.
- Big-O 표기법
-알고리즘의 복잡도를 나타내는 점근표기법으로, 데이터 증가량에 따른 시간 증가량을 계산한다.
-가장 높은 차수의 계수와 나머지 모든 항을 제거하고 표기하며, 알고리즘의 대략적인 효율을 파악할 수 있는 수단이다.
Big-O 표기법은 특히나 효율성을 상한선 기준으로 표기하기 때문에, 최악의 경우 이 정도 성능이 나올 수 있다는 판단 또한 가능하다.
그렇다면 Big-O는 어떻게 판단하는 걸까. 아래와 같은 예시 상황을 생각해 보자.
int Case1(int n)
{
int sum = 0;
sum = n * n;
return sum;
}
int Case2(int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += n;
}
return sum;
}
int Case3(int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
sum++;
}
}
return sum;
}비교를 위해 위와 같은 세 가지 케이스에 관해 함수를 준비했다.
여기에서 각 함수에 값을 늘려가면서, 연산이 어떻게 진행되는지 생각해보자.
- Case1의 경우에는 n에 어떠한 값을 넣든 연산을 진행하는 횟수는 1회일 것이다.
- Case2의 경우에는 n에 입력한 만큼의 값을 더해줘야 하므로, 연산을 진행하는 횟수는 n회일 것이다.
- Case3의 경우에는 n에 입력한 값의 제곱만큼의 값을 더해줘야 하므로, 연산을 진행하는 횟수는
n²회일 것이다.
이와 같은 상황을 아래 표로 정리해보았다.
| 입력값 | Case1 | Case2 | Case3 |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10,000 |
| 1000 | 1 | 1000 | 1,000,000 |
| n | 1 | n | n² |
| Big-O | O(1) | O(n) | O(n²) |
Big-O는 이와 같이 연산을 진행하는 횟수로 성능을 판단할 수 있게 한다.
위와 같은 케이스를 예를 들어 설명하자면, 성능은 O(1) > O(n) > O(n²) 순으로 좋다고 할 수 있다.
- 수행 시간 분석
알고리즘의 성능은 상황에 따라 수행 시간이 달라진다. (컴퓨터의 성능에 따라서도 영향을 받는다)
수행 시간을 분석하는 경우 평균의 상황과 최악의 상황을 기준으로 평가하며, 최선의 상황의 경우 알고리즘의 성능을 분석하는 수단으로 적합하지 않다.
2. 리스트와 링크드리스트
2.1) 리스트(List)
자료 구조 중 가장 단순한 형태인 리스트에 대해 알아보고자 한다.
리스트 (List)
런타임 중 크기를 확장할 수 있는 배열기반의 자료구조로, 배열요소의 갯수를 특정할 수 없는 경우 사용이 용이하다.
2.2) 리스트의 특성
리스트는 크기를 변경할 수 없는 배열에 비해, 크기를 확장시킬 수 있다. 또한 아래와 같은 특성을 지니고 있다.
-
리스트 삽입 : 중간에 데이터를 추가할 때 위치를 찾은 이후, 그 위치부터 있는 데이터들을 한 칸 씩 뒤로 밀어내고 삽입
-
리스트 삭제 : 중간에 데이터를 삭제할 때 그 위치를 찾은 이후, 데이터를 삭제하고 뒤의 데이터를 전부 한 칸 씩 앞으로 이동
-
리스트 용량 : 리스트에 저장된 용량을 넘어서는 데이터가 입력되었을 때, 그 처음 용량과 더 큰 크기의 새로운 배열을 생성한다. 이후 해당 데이터를 새로 생성된 배열에 복사한 후 다음 값을 입력한다.
2.3) 리스트의 기능
- 선언
List<(자료형)> (이름) = new List<(자료형)>();리스트의 선언은 위와 같이 하며, 아래에 리스트에서 많이 쓰이는 기능 목록을 정리하였다.
List<int> list = new List<int>();
1. Add(내용); : 맨 뒤에 추가하기 - O(1)
ex) list.Add(1);
2. Insert(끼워넣을 위치, 내용); : 중간에 끼워넣기 (0이 맨앞이다) - O(n)
ex) list.Insert(2, 3);
// 만약 똑같은 게 여러 개면? 찾은 것 중 맨 앞의 하나만 지움
// 만약 지워야 할 것을 못 찾았으면? 안 터지고 그냥 무시함 (bool로 false가 반환된다)
3. Remove(내용); : 똑같은 거 찾아서 삭제하기 - O(n)
ex) list.Remove(1);
// 만약 크기를 벗어나면? 얘는 터진다
4. RemoveAt(지울 위치); : 위치를 지정하여 지우기 (0이 맨앞이다) - O(n)
ex) list.RemoveAt(2);
// 접근 : 리스트는 배열로 구현되어 있기 때문에 인덱스를 통한 접근이 가능하다. - O(1)
5. list[1] = 222;
6. IndexOf(내용); : 내용으로 적힌 것을 찾기 - 찾으면 인덱스 반환, 만약 못 찾으면 -1로 반환됨 - O(n)
ex) list.IndexOf(2);
7. Contains(내용); : 내용에 적힌 것을 찾고, 있으면 True, 없으면 False - O(n)
ex) list.Contains(2);2.4) 리스트의 성능과 평가
리스트의 성능을 정리하면 다음과 같다.
- 리스트 시간복잡도
| 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|
| O(1) | O(n) | O(n) | O(n) |
접근에서 매우 좋은 방식이나, 탐색/삽입/삭제에서는 한계가 있다고 볼 수 있다.
2.5) 링크드리스트/연결리스트(LinkedList)
C# 게임 프로그래밍 쪽에서는 잘 안 쓰는 편이지만, 기능 자체는 알아두자
LinkedList
-데이터를 포함하는 노드들을 연결식으로 만든 자료구조이다.
-데이터와 다른 데이터 지점의 참조변수를 가진 노드를 기본단위로 사용한다.
-데이터가 노드를 통해 연결식으로 구성하기 때문에 데이터의 추가/삭제에 유용하다.
-노드가 메모리에 연속적으로 배치되지 않고 연결 구조로 다른 데이터의 위치를 확인한다.
배열이나 리스트처럼 데이터가 연속적으로 저장되는 것이 아닌, 연결성으로 데이터를 저장하는 방식을 사용한다.
2.6) 링크드리스트의 종류
1) 단방향 연결리스트
노드가 다음 노드를 참고하는 방식이다.
2) 양방향 연결리스트
노드가 이전/다음 노드를 참고한다.
3) 환형 연결리스트
노드가 이전/다음 노드를 참고하며, 시작 노드와 마지막 노드를 참고한다.
2.7) 링크드리스트의 특징
연결리스트의 경우 데이터를 연속적으로 배치하는 배열과 다르게 연결식으로 구성되어 있다.
따라서, 데이터의 추가/삭제 과정이 다른 데이터의 위치와 무관하게 진행되기에 빠르게 진행된다.
하지만, 데이터의 접근 과정에서 연속적인 데이터 배치가 아니기 때문에 인덱스의 사용이 불가하여 처음부터 탐색해야 한다.
- 연결리스트 삽입 : 새로 추가하는 노드가 이전/이후 노드를 참조한 뒤 이전/이후 노드가 새로 추가하는 노드를 참조한다.
- 연결리스트 삭제 : 삭제하는 노드의 이전 노드가 이후 노드를 참조한 뒤 삭제하는 노드의 이후 노드가 이전 노드를 참조한다.
2.8) 링크드리스트의 기능
- 선언
LinkedList<(자료형)> (이름) = new LinkedList<(자료형)>();링크드리스트의 선언은 위와 같이 하며, 아래에 링크드리스트에서 많이 쓰이는 기능 목록을 정리하였다.
LinkedList<string> linkedList = new LinkedList<string>();
[데이터 추가 기능]
1. AddFirst(내용); // 맨 앞에 추가 : O(1)
2. AddLast(내용); // 맨 뒤에 추가 : O(1)
3. AddBefore(노드위치, 내용); // 노드 기준 앞에 추가 : O(1)
4. AddAfter(노드위치, 내용) // 노드 기준 뒤에 추가 : O(1)
[데이터 삭제 기능]
5. Remove(노드 위치) // 노드 위치 데이터 지우기 : O(1)
6. RemoveFirst(); // 맨 앞에거 지우기 : O(1)
7. RemoveLast(); // 맨 뒤에거 지우기 : O(1)
8. Remove(내용); // 내용을 지우기 : O(n)
[접근]
//linkedList[2] : 연결리스트는 인덱스가 없다(연속적으로 저장하지 않기 때문에 인덱스 사용이 불가능하다)
따라서 접근하려면 node 기준으로 접근해야 한다
9. node.Previous; // 노드 기준 앞쪽
10. node.Next; // 노드 기준 뒤쪽
11. linkedList.First; // 제일 앞
12. linkedList.Last; // 제일 뒤
[탐색]
13. Find(내용) // 찾아서 노드 반환
14. Contains(내용) // 찾아서 있으면 True 없으면 False2.9) 링크드리스트의 성능과 평가
링크드리스트의 성능을 정리하면 다음과 같다.
- LinkedList 시간복잡도
| 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|
| O(n) | O(n) | O(1) | O(1)) |
삽입과 삭제가 매우 좋은 방식이나, 접근/탐색에서는 한계가 있다고 볼 수 있다.
3. 스택과 큐(Stack / Queue)
3.1) 스택
스택 (Stack)
선입후출(FILO), 후입선출(LIFO) 방식의 자료구조로 가장 최신 입력된 순서대로 처리해야 하는 상황에 이용한다.
3.2) 스택의 특성
스택은 리스트의 사용법만 달리하여 구현이 가능하다.
- 데이터 삽입 : 데이터가 들어있는 칸 중에 제일 마지막 칸에 저장된다.
- 데이터 삭제 : 데이터가 들어있는 칸 중에 제일 마지막 칸의 데이터가 삭제된다.
3.3) 스택의 기능
스택에서 주로 사용하는 기능은 아래와 같다.
Stack<int> stack = new Stack<int>();
// 추가 : O(1), 최악(용량이 가득 찼었을때) : O(n) -> 가득 찼을 때 복사하는 과정이 필요해서 n개를 복사해야함
stack.Push(1);
stack.Push(2);
stack.Push(3);
stack.Push(4);
stack.Push(5);
// 꺼내기 : O(1)
Console.WriteLine(stack.Pop()); // 출력 : 5
Console.WriteLine(stack.Pop()); // 출력 : 4
Console.WriteLine(stack.Pop()); // 출력 : 3
// 다음으로 꺼내질 요소 확인
Console.WriteLine(stack.Peek()); // 출력 : 2 (꺼내지는 않음)
// 스택에서 꺼낼 게 없으면 에러이므로 조건을 확인할 것
if(stack.Count > 0)
{
Console.WriteLine(stack.Pop());
}
// 스택이 있는지 확인하고
int a;
stack.TryPeek(out a); // 다음으로 꺼내질 요소 확인
stack.TryPop(out a); // 꺼내기
stack.Push(6);
stack.Push(7);
stack.Push(8);
stack.Push(9);
while(stack.Count>0) // 조건 예시
{
Console.WriteLine(stack.Pop());
}- 스택의 특징
stack도 배열이지만 인덱스로 값을 확인하거나, 변경하는 것은 불가능하다.
3.3) 큐(Queue)
큐(Queue)
선입선출(FIFO), 후입후출(LILO) 방식의 자료구조로, 입력된 순서대로 처리해야 하는 상황에 이용한다.
3.4) 큐의 특성
큐는 배열을 생성하고 순차적으로 데이터를 배치하는 방식으로 사용된다.
- 큐는 배열을 사용하지만, 데이터의 저장 순서는 배열 인덱스가 아닌 head와 tail로 판단한다.
- head를 기준으로 데이터가 처리되며, tail을 기준으로 데이터가 입력된다. 또한 tail은 head가 데이터를 처리하여 비워진 공간을 재활용한다.
- head와 tail이 겹쳐 데이터가 지워지는 것을 방지하기 위하여, 큐 내에서 빈 배열이 하나밖에 남지 않았을 때 가득찬 것으로 판정한다. 배열이 가득찼다고 판정되었을 경우 크기를 늘린 배열을 하나 더 만들고, 현재의 데이터를 복사하여 다시 처리를 시작한다.
3.5) 큐의 기능
큐에서 주로 사용하는 기능은 아래와 같다.
Queue<int> queue = new Queue<int>();
// 추가 : O(1), 최악의 경우 : O(n)
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Enqueue(4);
queue.Enqueue(5);
// 꺼내기 : O(1)
Console.WriteLine(queue.Dequeue()); // 출력 : 1
Console.WriteLine(queue.Dequeue()); // 출력 : 2
Console.WriteLine(queue.Dequeue()); // 출력 : 3
// 꺼내지 않고 확인
Console.WriteLine(queue.Peek());