1. 자료구조

1. 자료구조

자료구조란 프로그래밍에서 데이터를 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.

프로그래밍에서 데이터를 보관하는 방법에 따라서 작업 효율이 달라진다. 예를 들어 숫자들을 무작위가 아닌 오름차순으로 정리를 해 뒀다면 이진탐색(절반씩 나눠서 탐색)을 할 수 있다. 1억개의 데이터가 있을 때 정렬되지 않은 데이터는 평균 5천만번, 정렬된 데이터는 평균 30번이면 원하는 데이터를 찾을 수 있다. 그러나 오름차순 구조는 자료를 찾고 추가할 때는 느리다. 모든 상황에서 효율적인 자료구조는 없기에 원하는 기능에 적합한 자료구조를 선택해야 한다.

2. 시간복잡도(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	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²)

알고리즘의 성능을 평가할 때 최선의 상황은 평가에 적합하지 않고 평균과 최악의 상황을 기준으로 평가한다.

2. List

List는 런타임 중 크기를 확장할 수 있는 배열기반의 자료구조이며 배열요소의 갯수를 특정할 수 없는 경우 사용이 용이하다.

List<int> list = new List<int>();
형태로 사용할 수 있다.

Add() 메서드는 요소를 끝에 추가한다.
Insert() 메서드는 지정한 인덱스에 요소를 추가한다.
Remove() 메서드는 첫 번째로 일치하는 요소를 삭제한다.
RemoveAt() 메서드는 지정한 인덱스의 요소를 삭제한다.
Contains() 메서드는 특정 값이 리스트에 포함되는지 확인한다.

Remove 로 없는 값을 지우려고 하면 오류가 나지는 않고, 아무 일도 일어나지 않는다. 대신 bool값으로 지워졌는지에 대해 알 수 있다. 그러나 RemoveAt에서 없는 인덱스를 지우려고 하면 오류가 난다.

list[1] = 222;, list value = List[1]; 리스트는 배열로 구현되어 있기 때문에 인덱스를 통한 접근이 가능하다.

int index = list.IndexOf(222); 메서드로 해당 값의 인덱스를 찾을 수 있다.
bool contain = list.Contains(222); 메서드로 해당 값을 가지고 있는지 알 수 있다.

리스트는 배열 기반의 자료구조이고, 배열은 크기를 변경할 수 없는 자료구조이다. 리스트는 동작 중 크기를 확장하기 위해 포함한 데이터보다 더욱 큰 배열을 사용한다.

배열은 배열의 크기를 확인하기 위해 Length라는 표현을 쓰는데, list는 Count, Capacity라는 개념을 쓴다. 용량이 몇 개 있는지 확인하는 것은 Capacity, 몇 개의 요소가 있는지 확인하는 것은 Count이다.

총 평가로는 접근에서 좋은 자료구조이다.

<리스트 시간복잡도>
접근 탐색 삽입 삭제
O(1) O(n) O(n) O(n)

3. LinkedList

LinkedList(연결리스트)는 데이터를 포함하는 노드들을 연결식으로 만든 자료구조이며 데이터와 다른 데이터 지점의 참조변수를 가진 노드를 기본 단위로 사용한다. 또한 데이터를 노드를 통해 연결식으로 구성하기 때문에 데이터의 추가/삭제에 유용하다.

List는 추가하거나 삭제할 때 다른 원소들을 밀거나 당겨야해서 비효율적인 연산이 일어나지만 LinkedList는 추가할 때 위치를 이동시킬 필요가 없다. 또한 LinkedList는 하나의 원소가 다음 원소 주소를 참조하고 있음

연결리스트는 노드를 기본 단위로 연결식으로 구현되어 있는데 총 4가지 방법이 있다.
1. node가 한 쪽 방향으로만 참조하는 단일 연결
2. 양방향으로 참조하는 이중 연결
3. 한 쪽 방향으로만 참조하지만 시작과 끝이 연결되어있는 원형 연결
4. 양방향으로만 참조하며 시작과 끝이 연결되어있는 원형 이중 연결

이 중 LinkedList는 이중 연결 구조이다.
사용법은 다음과 같다

LinkedList<int> linkedList = new LinkedList<int>(); 로 선언

AddFirst() 메서드는 요소를 맨 앞에 추가한다.
AddLast() 메서드는 요소를 맨 뒤에 추가한다.
AddBefore() 메서드는 지정한 노드 앞에 요소를 추가한다.
AddAfter() 메서드는 지정한 노드 뒤에 요소를 추가한다.
Remove() 메서드는 지정한 값을 가진 첫 번째 노드를 삭제한다.
RemoveFirst() 메서드는 맨 앞의 노드를 삭제한다.
RemoveLast() 메서드는 맨 뒤의 노드를 삭제한다.
Find() 메서드는 지정한 값을 가진 첫 번째 노드를 반환한다.
Contains() 메서드는 특정 값이 연결 리스트에 포함되는지 확인한다.

LinkedList는 인덱스가 없다. 순회를 인덱스로 할 수 없기 때문에 foreach문 등 다른 방법으로 순회 해야 한다.

총 평가로는 삽입과 삭제에서 좋은 자료구조이다.
<LinkedList의 시간복잡도>
접근 탐색 삽입 삭제
O(n) O(n) O(1) O(1)

4. Stack

Stack은 선입후출(FILO), 후입선출(LIFO) 방식의 자료구조이다. 가장 최신 입력된 순서대로 처리해야 하는 상황에 유용하다.

Stack<int> stack = new Stack<int>(); 으로 선언할 수 있다.

Push() 메서드는 요소를 스택의 맨 위에 추가한다.
Pop() 메서드는 스택의 맨 위 요소를 제거하고 반환한다.
Peek() 메서드는 스택의 맨 위 요소를 제거하지 않고 반환한다.
Contains() 메서드는 특정 값이 스택에 포함되는지 확인한다.
Clear() 메서드는 모든 요소를 제거한다.

삽입에서는 O(1)의 시간 복잡도를 가지고 있다. 그러나 만약 내부 배열의 최대 크기에 도달했다면 두 배 크기로 재할당{O(n)}한다.

탐색에서는 요소들이 쌓여서 원하는 것을 바로 꺼낼 수 없기에 O(n)의 시간 복잡도를 가지고 있다.

읽기에서는 가장 마지막에 추가된 데이터 반환하기에 O(1)의 시간 복잡도를 가지고 있다.

삭제에서는 가장 마지막에 추가된 데이터를 반환 및 스택에서 제거하기에 O(1)의 시간 복잡도를 가지고 있다.

Stack은 비어있었을 때 꺼내면 오류가 난다.

if(stack.Count > 0)

stack.TryPop(out int pop); // TryPop은 성공하면 true, 아니면 False 반환
stack.TryPeek(out int pop); // TryPeek도 사용 가능

while (stack.Count > 0)
{
	Console.WriteLine(stack.Pop());
}

따라서 위 처럼 확인을 하고 꺼내는 것이 안전하다

5. Queue

Queue는 선입선출(FIFO), 후입후출(LILO) 방식의 자료구조이다. 입력된 순서대로 처리해야 하는 상황에 유용하다.

Queue<int> queue = new Queue<int>();로 선언할 수 있다.

Enqueue() 메서드는 요소를 큐의 뒤쪽에 추가한다.
Dequeue() 메서드는 큐의 앞쪽 요소를 제거하고 반환한다.
Peek() 메서드는 큐의 앞쪽 요소를 제거하지 않고 반환한다.
Contains() 메서드는 특정 값이 큐에 포함되는지 확인한다.
Clear() 메서드는 모든 요소를 제거한다.

Queue방식의 자료구조는 삽입을 할 때는 괜찮지만 삭제를 할 때마다 나머지 데이터를 앞당겨야되는 n번의 작업이 발생한다. 따라서 아래의 단계가 자동으로 거쳐진 후 C#에서 사용할 수 있게된다.

• 전단 & 후단
  큐는 head와 tail을 표시하여 삽입할 위치와 삭제할 위치를 지정한다. 표시할 위치를 지정해두기만 하면 당겨야하는 n번의 작업이 발생하지 않는다

그러나 큐의 배열 마지막 위치까지 사용하면 빈자리가 없어 저장 불가한 상황이 발생할 수 있다. 들어있는 요소는 3개인데 자리는 1000개가 생성될 수 있는 것이다.

• 순환배열
  따라서 끝에 도달한다면 늘리지 않고 처음으로 돌아가서 빈 공간을 활용하는 방식으로 문제를 해결한다. 마지막 위치 도달 시 다시 가장 앞 위치를 사용하여 빈 공간을 재활용하는, 순환 구조를 사용한다.

그러나 head가 tail을 침범하여 값을 덮어쓸 수 있는 문제가 생길 수 있다.

• 포화상태 확인
  따라서 head와 tail이 일치하는 경우를 비어있는 경우로 판정한다. tail이 head 이전 위치에 있는 경우를 실제로는 한 자리가 비어있지만 가득 찬 것으로 판정한다. 즉, 1 칸이 비어있는 경우를 꽉 찬 것이라고 판단한다.

6. 메모

Stopwatch 클래스로 코드의 시간을 확인할 수 있음
StopWatch sw = new StopWatch();
sw.Start();
sw.End();