목표 지점까지 최단 경로를 찾아내는 그래프 알고리즘으로, Dijkstra 알고리즘을 그대로 Continuous한 현실 문제에 적용하기 어려웠던 문제를 보안했다.

그리고 h(x)라는 새로운 함수를 추가해서 기존 Dijkstra 보다 더 빠르게 최단 경로를 찾아낸다.

A* Algorithm의 기본적인 형태는 아래와 같다.

g(x) : 시작 위치에서 “현재 위치 x”까지의 실제 비용

h(x) : “현재 위치 x”에서 부터 “목표 위치”까지의 추정되는 비용

f(x) : 시작 위치에서 “현재 위치 x”까지의 총 추정 비용

따라서, f(x) = g(x)면 Dijkstra와 같다.

알고리즘의 동작은 아래와 같이 진행된다.

1. 아직 처리해야하는 노드들 중 가장 작은 f(x) 값을 가지는 노드를 선택한다.
2. 이 때 해당 노드가 destination이면 Algorithm을 종료한다.
3. 아니라면 방문 했다는 표시를 남기고 현재 노드에서 갈 수 있는 노드들을 본다.
4. 현재 노드에서 갈 수 있는 노드들의 가중치 값을 수정한다.

   

5. f(x) = dist[x] + h(x)를 계산한다.
6. (f(이웃 노드), 이웃 노드) Pair를 Priority Queue에 저장한다.
7. (1)에서 부터 다시 반복한다.

그림으로 알고리즘의 동작을 보자.

아래 그림과 같이 Graph가 있다고 생각하자. 이 때 (1)번에서 시작해서 (7)번까지 최단 경로를 찾는다고 해보자.

Close Set은 최단 경로인지 처리가 완료된 노드들이 들어가는 집합이다. 노드를 중복해서 검사하는 것을 방지

Open Set은 최단 경로를 분석하기 위해 계속해서 노드들이 추가되며, f(x)값이 작은 순서대로 저장된다.

먼저 시작 노드인 (1)을 Close Set에 저장한다.

그 후 이웃 노드들 (2), (3)의 dist를 수정하고 (= 그림에서 g(x)) 수정한 값을 h(x)와 더한다.

이 때 h(x)는 해당 노드에서 도착 노드까지의 측정 함수로써 다양한 함수들이 존재하며 알고리즘 성능에 큰 영향을 미친다. 보통은 "맨하탄 거리", "유클리드 거리"를 사용한다. (그림에서는 대략적으로 (2), (3)의 도착지까지의 거리를 각각 4.6, 9.6으로 측정 했다고 가정)

그 후 Priority Queue에 저장한다.

(2), (3) 노드 중 (2)가 f(x)가 작으니 Priority Queue에서 pop 된 후 Close Set에 저장된다.

(2)와 이웃한 (4), (5) 노드의 dist를 수정하고 h(x)와 더한다. 이 때 (4), (5) 노드는 도착 노드와 연결되어 있으므로 실제 거리와 측정 값이 같다.

h(x)와 더한 값을 Priority Queue에 저장한다.

(5), (6)의 f(x) 값이, (1)에서 추가한 (3) 노드보다 크기 때문에 (3) 노드가 pop 된 후 Close Set에 저장된다.

(3)은 (6) 노드와 연결되어 있으니 (6)의 dist를 수정하고 h(x)와 더한 후 Priority Queue에 저장한다.

Priority Queue에서 가장 작은 f(x)인 (4) 노드가 pop 된 후 Close Set에 저장된다.

(4) 노드는 (5)와 (7) 노드에 연결되어 있다. 하지만 (5) 노드는 (1) - (2) - (4) - (5) 경로의 dist 값 보다 Priority Queue에 저장되어 있는 dist 값이 더 작으므로 이 때 (5)의 dist는 수정하지 않는다.

따라서 (7) 노드만 dist 값을 수정한 후 h(x) 값과 더해 Priority Queue에 추가한다.

Priority Queue에서 가장 작은 f(x)인 (7)을 pop한다.

이 때 Destination Node와 (7)이 같으니 알고리즘을 종료한다.

Path를 구성할 때는 Close Set의 정보를 이용해 Destination 노드부터 계속 이전 노드를 null이 나올 때까지 참조하면 최단 경로가 완성된다.

https://github.com/MunHwaDong/Algorithm/blob/master/graph/AStar.cs

Bubble Sort

반복적으로 가장 큰 값 혹은 가장 작은 값을 찾아 가장 뒤로 보내면서 정렬하는 알고리즘이다.

정렬 되어 있지 않은 원소들을 가지는 S를 생각해보자.

이 때 S를 오름차순으로 정렬한다면 아래 그림처럼 될 것이다.

이제 매번 아래와 같이 “현재 원소와 다음 원소를 비교하고 현재 원소가 더 크다면 두 원소의 위치를 바꿀 것”이다.

이 때 아래 그림과 같이 s0가 가장 큰 값이라면

매번 Swap이 일어날 것이고, i = n-1까지 Swap이 될 것이니 가장 큰 값이 제일 뒤로 가게 된다.

이를 시각화 해보면

그림과 같이 매번 Swap을 하게 될 것이고, 결국 제일 큰 원소(10)이 가장 뒤로 가게 되는 것을 확인 할 수 있다.

s0에 대해 정렬이 끝난 후 S의 상태가 아래와 같다고 생각해보자

s1이 “k-1”번째 까지는 가장 큰 값이니 계속 Swap을 해서 “k-1”번째 위치까지 도달할 것이다.

이 때 s1이 sk보다는 작다고 했으니 Swap이 일어나지 않게 될 것이고 현재 원소 “si (현재 원소)”는 sk가 될 것이다.

이제 sk를 s0를 제외한 “잠재적인 가장 큰 값”이라고 생각해 나갈것이다

똑같이 sk가 s0전까지 가장 큰 값이니 계속 Swap해 나갈 것이고 s0 앞쪽에 위치하게 되면서 해당 원소에 대해 정렬이 끝날 것이다.

3 < 5가 참이니 Swap을 하지 않고 i (위치)만 이동한다.

그 이후로는 “원소 10”의 예시처럼 계속 Swap이 일어나 자기 위치로 이동하게 되는 것을 볼 수 있다.

이것을 반복하면 모든 원소가 오름 차순으로 정렬될 것이다.

private void BubbleSortArray(ref int[] arr)
{
    for (var i = 0; i < arr.Length; i++)
	    for (var j = 0; j < arr.Length - i - 1; j++)
        if (arr[j] > arr[j + 1])
            (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
}

Quick Sort

임의의 원소(Pivot)을 설정하고 재귀적으로 Pivot을 정렬하면서 Pivot을 기준으로 자료를 두 부분으로 나누면서 정렬해 나가는 알고리즘

정렬 되어 있지 않은 원소들을 가지는 S를 생각해보자.

이 때 S를 오름차순으로 정렬한다면 아래 처럼 될 것이다.

이 때 s0가 Pivot이라고 했을 때

s0보다 작을 수 있는 원소의 개수는 n-2개이고, 똑같이 s0보다 클 수 있는 원소의 개수도 n-2개 이다.

이 때 n-2개의 원소들을 Pivot을 기준으로 작으면 왼쪽, 크면 오른쪽으로 정렬한다면 자료 전체는 정렬하지 못했어도 “Pivot 자체는 n-2개의 원소들 사이에서 정렬됨을 알 수 있다.”

이 때 집합을 두개로 나눠보자

Sub1은 s0보다 작은 원소들의 집합이고, Sub2는 s0보다 큰 원소들의 집합이다.

다시 Sub1과 Sub2에 대해서 Pivot을 설정하고 재귀적으로 반복하면 정렬이 된다는 것을 알 수 있다.

이것을 그림을 통해서 보자.

아래와 같이 집합이 존재한다고 해보자.

이 때 Pivot + 1의 위치부터, End Position까지 Pivot과 비교하면서 Pivot보다 작으면 왼쪽, 크면 오른쪽으로 보낼 것이다.

이것을 우리는 2 Pointer Algorithm 기법으로 구현 할 수 있다.

1. 처음 맨 앞 (Start Position)을 Pivot으로 설정한다.
2. Pivot + 1부터 시작하는 “Left”변수와 End Position부터 시작하는 “Right” 변수를 만든다.
3. Left를 1씩 증가시켜 Pivot과 크기를 비교해나간다.
4. 이 때 처음으로 Pivot보다 큰 원소를 만나면 멈춘다.
5. “Right”를 1씩 감소시켜 Pivot과 크기를 비교해나간다.
6. 이 때 처음으로 Pivot보다 작은 원소를 만나면 멈춘다.
7. 아직 Left < Right를 만족한다면, Left 위치의 원소와 Right 위치의 원소를 Swap하고, (3) 으로 돌아간다.
8. Left < Right를 만족하지 않는다면, Pivot과 Right 위치의 원소를 Swap한다.
9. Start Position ~ Right / Right + 1 ~ End Position으로 자료를 두 부분 집합으로 나눠서 (1)부터 반복한다.
10. Start Position ≥ End Position이면 정렬할 원소가 하나 있거나 없는 것이니 반환한다.

그럼 알고리즘대로 위 그림을 정렬해보자

Pivot + 1 위치 (= 4)를 비교했을 때 Pivot이 더 크니 Left 포인터를 증가시킨다.

Pivot + 1 위치 (= 5)를 비교했을 때 Pivot이 더 크니 Left 포인터를 증가시킨다.

계속 진행하면

Left 포인터는 End Position + 1 위치를 가르키게 되며 “Pivot 보다 큰 값을 탐색하는 과정을 끝낸다.”

그 후 “Pivot 보다 작은 값을 탐색하는 과정을 시작한다.”

이 때 Pivot 보다 작은 첫 원소를 가르키는 포인터는, Pivot 보다 큰 첫 원소를 가르키는 포인터 왼쪽에 있을 수 없기 때문에 “Pivot 보다 작은 값을 탐색하는 과정을 끝낸다.”

(Left > Right 일 수 없기 때문에)

그 후 Right 위치 (Pivot 보다 작은 첫 원소 포인터)의 원소와 Pivot을 교환하면 해당 범위에서 Pivot에 대한 정렬이 끝난다.

그 후 Pivot을 기준으로 집합을 두 부분 집합으로 나눈 후 다시 (1)번 부터 반복한다.

Pivot (= 3)과 Left (= 4)를 비교했을 때 4가 더 큼으로 Left의 증가를 멈춘 후 Right 포인터를 움직여 Pivot 보다 작은 값을 찾는다.

Pivot (= 3)과 Right(= 1)을 비교했을 때 1이 더 작으므로 Right의 감소를 멈춘다.

이 때 아직 Left < Right를 만족함으로, Left 위치의 원소와 Right 위치의 원소를 Swap하고,

(3) 으로 돌아간다. (3. Left를 1씩 증가시켜 Pivot과 크기를 비교해나간다.)

Left 위치의 원소 (= 5)는 Pivot보다 큼으로 Left의 증가를 멈추고 Right를 움직여 작은 값을 탐색한다.

Right 위치의 원소 (= 2)는 Pivot 보다 작으므로, 감소를 멈춘다.

이 때 아직 Left < Right를 만족함으로, Left와 Right를 Swap하고 (3)으로 돌아간다.

이 때 Left 위치의 원소 (= 5)는 Pivot보다 큼으로, 증가를 멈춘다.

Right 위치의 원소 (= 5)는 Pivot 큼으로 감소한다.

이제 Left가 Right보다 더 큼으로, Pivot과 Right의 위치를 Swap하고 집합을 다시 두 부분으로 나눈 후 각 부분에 대해서 (1) 부터 반복한다.

이런 과정을 반복하면 아래와 같은 과정을 거친다.

이렇게 정렬이 끝난다.

public static class QuickSort<T> where T : IComparable<T>
{
    private static void Quick_Sort(ref List<T> arr, int st, int en)
    {
        if (st + 1 >= en) return;
        var pivot = arr[st];
        var left = st + 1;
        var right = en;

        while (true)
        {
            while (left <= right && arr[left].CompareTo(pivot) <= 0) left++;
            while (left <= right && arr[right].CompareTo(pivot) >= 0) right--;

            if (left > right) break;

            (arr[left], arr[right]) = (arr[right], arr[left]);
        }

        (arr[st], arr[right]) = (arr[right], arr[st]);

        Quick_Sort(ref arr, st, right);
        Quick_Sort(ref arr, right + 1, en);
    }
}

Red-Black Tree

“자가 균형 이진 탐색 트리 (Self-Balanced-BST)”에 아래 5가지 추가적인 조건을 만족하는 BST의 하위에 속하는 트리이다.

1. 모든 노드는 “Red” 혹은 “Black”의 속성을 가진다.
2. Root 노드는 항상 “Black”이어야 한다.
3. Leaf 노드는 항상 “Black”이어야 한다.
4. “Red” 노드는 자식으로 “Black”만을 가질 수 있다.
5. 임의의 노드에서 해당 노드의 Sub-Tree들에서 각각의 Leaf까지의 Path들은, Leaf까지 가면서 같은 개수의 Black 노드들을 지나가게 된다.

Red-Black Tree의 조건으로 부터 한 가지 사실을 알 수 있다.

이렇게 4번과 5번의 특성을 가지고 Tree의 높이를 항상 log(n)으로 조정할 수 있다.

Insert / Delete 연산에 “노드의 회전” 개념이 필요하기에 먼저 “회전”에 대한 개념부터 시작한다.

Rotate

BST에서 Balance가 무너진 노드에서 다시 Balance 있게 노드를 교환하는 작업

1. Right Rotate

   

2. Left Rotate

   

3. LR Rotate
   1. 부분적으로 L Rotate후 R Rotate, 총 두 번 회전한다.

      

4. RL Rotate
   1. 부분적으로 R Rotate후 L Rotate, 총 두 번 회전한다.

      

Insert 연산

Red - Black Tree를 구현하기 위해, “TNULL” 이라는 특별한 노드를 사용한다.

왜냐하면, “조건 3 : Leaf 노드는 항상 “Black”이어야 한다.” 를 지켜야하기 때문에 null 값을 가지면서, Black인 특수한 TNULL이라는 노드를 사용한다.

아래 예시에서는 TNULL을 필요할 때 제외하고는 생략해서 표현하겠다.

BST의 Insert와 같이 노드간 정의된 대소관계를 통해서 Insert를 진행한다.

새롭게 Insert하는 노드는 “Red”로 설정하고 Insert한다.

(2)에 따라 “Red”로 Insert될 때 Red-Black Tree의 제약 조건에 따라 3가지 경우를 생각해 볼 수 있다.

1. 삽입한 위치가 Root인 경우
   1. 트리에 아무것도 없을 때 (root = null), “50”을 삽입한다고 하자
   2. 트리에 새롭게 삽입되는 노드는 처음에는 Red라 했으니 현재 Root는 “Red”이다.

      

      “조건 2 : Root는 항상 Black이어야 한다.”를 위반하였으니, Root의 색을 Black으로 바꿔준다.

      

    
2. 삽입한 위치의 Parent 노드의 색이 Black일 경우
   1. 부모가 Black인 경우 위반하는 조건이 없으니, 아무것도 하지 않는다.
   2. 트리에 “25”를 삽입해보자.

      

      
      
      
   3. 25는 50보다 작으니, 50의 Left Child가 된다. 이 때 25의 Parent가 Black이니 아무것도 하지 않는다.
    
3. 삽입한 위치의 Parent 노드의 색이 Red일 경우
   1. 이 경우, “조건 4 : Red 노드는 자식으로 Black 노드만 가질 수 있다.” 를 위반한다.
   2. 이 때 “조건 5 : 임의의 노드에서 해당 노드의 Sub-Tree들에서 각각의 Leaf까지의 Path들은, Leaf까지 가면서 같은 개수의 Black 노드들을 지나가게 된다.” 또한 위반될 수 있다.
   3. 따라서, Parent의 Parent 노드와 형제 노드까지 고려해서 노드의 회전과 색 변경이 필요하다.
   4. Parent의 Parent는 “Grand Parent”, Parent의 형제는 Uncle 노드라고 한다.
   5. Parent 노드가 Red일 때, Uncle을 기준으로 다시 두 가지 경우로 나눈다.
      1. Uncle이 Black일 때
         1. 50 → 25에 추가로 10을 삽입해보자.

            

         2. 이 때 새롭게 삽입된 노드 “10”의 Parent가 Red이고, Uncle이 Black (= TNULL)이다.
         3. 또한 Parent (= 25)는 Grand Parent (= 50)의 Left Child이고 새 노드 (= 10)도 Left Child이다.
         4. 이 때는, Left Rotate 수행 후 원래 Grand Parent (=50을) Red로 바꿔주고 Parent를 Black으로 바꿔준다.

            

      2. Uncle이 Red일 때
         1. 이어서 “20”을 삽입해보자.

            

         2. 이 때는 Parent와 Uncle 모두 Black을 바꾼 후, Grand Parent를 Red로 바꿔준다.
         3. 그 후 Grand Parent에 대해 다시 5개의 조건을 검사한다.
         4. 이 경우에는 25가 Root인데 Red이기에 Black으로 바꿔준다.

            

35 → 1 → 23 → 24 → 40 순으로 이어서 삽입을 진행해보겠다.

35의 부모가 Black이니 아무것도 하지 않는다.

1의 부모가 Black이니 아무것도 하지 않는다.

23의 부모가 Red이고 Uncle 또한 Red이니 둘 다 Black으로 바꾼후 Grand Parent를 Red로 바꾼다.

24의 부모가 Red이고 Uncle (= TNULL)은 Black이다.

Parent (= 23)은 Grand Parent (= 20)의 Right Child이다.

새 노드 (= 24)는 Parent의 Right Child이다.

따라서 Left Rotate 한 후 Grand Parent (= 20)를 Red로 바꿔주고 Parent (= 23)을 Black으로 바꿔준다.

40의 부모가 Red이고 Uncle (= TNULL)은 Black이다.

Parent (= 35)은 Grand Parent (=50)의 Left Child이다.

새 노드 (=40)은 Parent의 Right Child이다.

따라서 LR Rotate 한 후 Grand Parent (=50)을 Red로 바꿔주고 자기 자신 (= 40)을 Black으로 바꿔준다.

Delete 연산

Delete 연산은 “삭제 되는 노드의 색”이 중요하다.

이 때 “삭제 되는 노드의 색”은 BST 규칙에 따라 삭제할 때 실제로 Memory에서 삭제되는 노드를 의미한다.

“삭제 되는 노드의 색”은 해당 노드의 자식의 개수를 기준으로 한다.

1. “삭제 되는 노드의 색”의 자식이 없거나, 1개 일 때는 해당 노드의 색을 따른다.

   

2. “삭제 되는 노드의 색”의 자식이 2개 일 때는 해당 노드의 Right Sub-Tree의 최소값이 “삭제되는 노드의 색”이 된다.

   

이 때 “삭제 되는 노드의 색”이 Red 이면 5가지 조건 모두 위반하지 않는다.

하지만 Black이라면 (2), (4), (5) 조건을 위반했을 가능성이 있다.

(2) Root 노드는 항상 “Black”이어야 한다.

(4) “Red” 노드는 자식으로 “Black”만을 가질 수 있다.

(5) 임의의 노드에서 해당 노드의 Sub-Tree들에서 각각의 Leaf까지의 Path들은, Leaf까지 가면서 같은 개수의 Black 노드들을 지나가게 된다.

따라서 “삭제 되는 노드의 색”이 Red라면 아무것도 하지 않고

Black일 때 어떻게 Tree의 조건을 유지시킬지가 중요하다.

삭제 연산을 알아보기 전 필요한 개념들이 있다.

1. Extra - Black : 삭제 되는 노드의 위치를 대체하는 노드에 붙는 특수한 색 속성으로, 노드의 Color와 별개로 추가될 수 있다.
2. Doubly - Black : Black을 가지는 노드에 추가로 Extra - Black 속성이 붙은 노드를 뜻한다.
3. Red - and - Black : Red를 가지는 노드에 추가로 Extra - Black 속성이 붙은 노드를 뜻한다.

   

이 때 삭제를 하면 “Red - and - Black” 혹은 “Doubly - Black” 노드가 생긴다.

Red - and - Black의 경우, 해당 노드를 Black으로 변경하면 모든 조건을 위반하지 않으므로 Black으로 변경하면 끝난다.

하지만, Doubly - Black일 경우 조건이 위반되는 4 가지 경우가 존재한다.

이 4 가지 경우는, Doubly - Black의 형제 노드 색 / 그 형제 노드의 자식들의 색을 기준으로 나뉜다.

1. Doubly-Black의 형제가 Black이고 Right Child가 Red일 경우

   

   

   Doubly-Black의 형제가 Black이고 Left Child가 Red일 경우

   

   Doubly-Black의 형제가 Black이고 그 자식들이 다 Black일 경우

   

2. Doubly-Black의 형제가 Red일 경우

   

Object Pool Pattern

Object Pool은 미리 오브젝트를 예상되는 양만큼 먼저 Instantiate와 초기화 한 후 Pool에 넣어 필요할 때 꺼내 쓰는 Pattern

클라이언트가 Object를 요청했을 때 Pool에 오브젝트가 있다면 “기존에 미리 만든 오브젝트를 재활용”하고, Pool이 Empty일 때만 새롭게 Instantiate한다.

오브젝트가 더 이상 필요 없다면, Destroy하지 않고 오브젝트를 SetActive(false)해서 Pool에 다시 넣는다.

“이 때 Pool에 다시 넣기 전에, 오브젝트의 상태를 다시 처음 상태로 초기화 한 후 넣어줘야한다.”

그렇지 않으면, Pool에서 꺼내 재활용 할 때, 이전 상태 값이 들어가 있어 예상하지 않은 결과가 나타날 수 있다.

Object는 자신이 돌아갈 Pool에 대한 Reference를 가지고 있어서 더 이상 필요 없어지면 스스로 Pool로 돌아가려고 한다.

만약 Pool이 꽉 차 있다면, 돌아가지 않고 이 때 Destroy()가 발생한다.

메모리를 매번 재할당하는 것이 아니라 재활용하기 때문에, GC (Garbage Collector)가 너무 바빠서 생기는 현상인 “Hiccup, GC Spike”를 방지 할 수 있다.

또한 Pool은 Empty일 수는 있지만, Pool에 Object가 넘치지 않기 때문에 Memory 사용이 일관적이고 예측 가능하다는 장점이 있다.

Object Pool Pattern의 다이어그램은 아래와 같다.

Client는 Object Pool에게 미리 생성하고 초기화해둔 Object를 Pool에 요청하고 반환 받은 Pooling된 Object를 사용한다.

기본적인 Object Pool의 유니티 C# 코드는 아래 구조와 같다.

1. ObjectPool.cs

public class ObjectPool : MonoBehaviour
{
    [SerializeField] private PooledObject pooledObject;
    [SerializeField] private uint poolSize;
    private Stack<PooledObject> stack;

    void Start()
    {
        InitPool();
    }

    void InitPool()
    {
        stack = new Stack<PooledObject>();

        PooledObject poolObjectInstance = null;

        for (int i = 0; i < poolSize; i++)
        {
            poolObjectInstance = new PooledObject();

            poolObjectInstance.Pool = this;
            poolObjectInstance.gameObject.SetActive(false);
            stack.Push(poolObjectInstance);
        }
    }

    public PooledObject GetPooledObject()
    {
        if (stack.Count == 0)
        {
            PooledObject newInstance = Instantiate(pooledObject);
            newInstance.Pool = this;
            return newInstance;
        }
        
        PooledObject poolObject = stack.Pop();
        poolObject.gameObject.SetActive(true);
        return poolObject;
    }

    public void ReturnToPool(PooledObject pooledObject)
    {
        pooledObject.gameObject.SetActive(false);
        stack.Push(pooledObject);
    }
    
}

2. PooledObject.cs

public class PooledObject : MonoBehaviour
{
	private ObjectPool _pool;
	public ObjectPool Pool
	{
		get => _pool;
		set => _pool = value;
	}
	
	private void Release()
	{
		_pool.ReturnToPool(this);
	}
}

Queue

1. Queue는 가장 먼저 들어온 원소가 가장 먼저 나가는 "FIFO (First-In-First-Out) 자료 구조 (=집합)"이다.
2. Queue는 가장 앞쪽의 원소에서만 제거가 가능하고 가장 뒤쪽에 원소에서만 추가가 가능하다.
3. Queue의 기본적인 구조는 다음과 같고 중요 메소드가 3개 있다.
   1. Enqueue: 큐의 뒤쪽(rear)에 새로운 요소를 추가한다.
   2. Dequeue: 큐의 앞쪽(front)에서 요소를 제거하고 반환한다.
   3. Peek/Front: 큐의 맨 앞 요소를 조회한다. (제거하지 않음).
4. Queue의 구현은 “배열”로 할 수 있고, “Linked List” 기반으로 구현 할 수도 있다.

   

5. 자세한 구현 코드는 Github에서 확인
   https://github.com/MunHwaDong/Algorithm/blob/master/DataStructure/Queue.cs

Heap & Priority Queue

Heap은 “완전 이진 트리”이며, 빠르게 최대값과 최소값을 찾기 위한 자료 구조이다.

Heap은 “완전 이진 트리” 조건을 만족하면서 한 가지 추가적인 조건을 만족해야 한다.

1. “노드들 사이에는 대소 관계가 정의되며 부모 노드는 자신의 자식 노드들 보다 커야한다”
   (이 때 형제들간의 대소관계는 따지지 않는다.)

위 조건을 만족하면 Root 노드에 최대값이 들어가 있는 “Max Heap”이 되며, 부모가 자식들보다 작아야한다 라는 조건으로 바꾸면, “Min Heap”이 된다.

Max Heap (최대힙)을 가지고 삽입 / 삭제 / 탐색의 과정을 살펴보자

삽입

1. Max Heap에 조건에 따라, 부모 노드는 자신의 자식 노드들 보다 커야한다.
2. “완전 이진 트리”에 조건에 따라, 마지막 레벨을 제외한 모든 레벨에서는 왼쪽, 오른쪽 노드가 모두 존재해야하며 마지막 레벨에서는 가능한 왼쪽부터 노드가 존재해야한다.
3. 이 두 조건을 생각해보면, 트리의 가장 마지막에 새로운 노드를 삽입하고 현재 위치에서 자신과 부모의 크기를 Max Heap의 조건에 맞지 않을 때까지 비교하고 위치를 바꾸는 과정을 반복하면 재귀적으로 “가장 큰 값이 트리의 Root에 존재하게 된다.”
4. 이를 시각화 하기 위해, 원소를 아래 그림과 같은 순서로 삽입한다고 가정하자.

   

5. 원소 “1”을 삽입 한다.

   

6. 이어서 원소 “10”을 삽입한다. 이 때 BST 처럼 Root에서 부터 대소 관계로 자신의 삽입 위치를 찾아나가는 것이 아니고 “완전 이진 트리”이기에 Tree의 끝에 삽입한다.

   

7. “부모는 자신의 자식들보다 커야한다.”는 조건에 위배됨으로 “1”과 “10”을 Swap한다.

   

8. 이어서, “3”을 삽입한다. 조건을 위배하지 않으므로 아무런 일도 하지 않는다.

   

9. 이어서, “15”를 삽입한다. 조건에 위배됨으로 “1”과 “15”를 Swap한다.

   

10. “15”는 다시 “10”보다 큼으로 조건에 위배된다. 따라서 다시 Swap한다.

    

11. “20”을 삽입하고, 조건에 위배되지 않을 때까지 Swap한다.

    

12. 이어서 “4”를 삽입하고, 조건에 위배되지 않을 때까지 Swap한다.

    

13. 마지막으로 “2”를 삽입한다. 조건을 위배하지 않으므로 아무런 일도 하지 않는다.

    

14. 이처럼, 원소를 삽입하고 조건에 맞게 “부모-자식”을 Swap해 나가면 재귀적으로 가장 큰 값이 Root에 존재함을 알 수 있다.

삭제

1. 삭제는 Root에서만 일어나며, Max Heap일 경우 트리에서 가장 큰 값이, Min Heap일 경우 가장 작은 값이 트리에서 삭제 된다.
2. 이 때, 형제들간의 대소관계는 따지지 않는 성질 때문에 Heap을 다시 정렬해야하며 완전 이진 트리의 조건에 맞게 트리 중간에 비는 공간이 생기면 안되기 때문에 마지막 노드를 Root로 삽입한 후 Root부터 재귀적으로 자식들과 대소 관계를 비교하며 위치를 바꿔나간다.
3. 이 과정을 그림으로 시각화 해보기 위해 “삽입” 연산에서 완성한 트리를 생각해보자

   

4. 처음으로 삭제 연산을 하면, “20”을 Return 해주기 위해 잠시 임시 변수에 캐싱해둔 후 “마지막 노드의 값 (= 2)”를 “Root 노드에 덮어 씌운다.”
5. 이는 “완전 이진 트리” 형태를 유지하기 위한 작업이다. 이 작업이 끝나면 마지막 노드를 삭제한다.

   

6. Leaf 노드가 Root에 올라와 있으니, “부모는 항상 자식보다 커야한다.”는 조건을 위배했을 수도 있는 가능성이 있다.
7. 따라서, 이제 Root에서 부터 자식들의 크기를 비교한 후 더 큰 자식과 Swap하고 재귀적으로 반복하면 아래 그림과 같은 결과가 나온다.

   

8. 마지막으로, temp 변수에 캐싱해둔 값을 Return해주면 삭제 연산이 끝난다.

   

Priority Queue

Priority Queue는 우선 순위를 기준으로 노드를 저장하는 자료 구조이다.

Queue라는 자료 구조는, 삽입과 삭제 연산이 자료 구조의 맨 앞과 맨 뒤에서만 발생한다.

위에서 Heap 자료 구조 또한 삽입과 삭제 연산이 맨 앞과 맨 뒤에서만 발생했다.

또한 우선 순위에 맞게 가장 높은 우선 순위를 가진 원소가 맨 앞에 오게 되어서 가장 먼저 Return 될 것이니 Heap 구조로 Priority Queue를 많이 구현하게 된다.

실제 구현 코드는 Github에서 확인

https://github.com/MunHwaDong/Algorithm/blob/master/DataStructure/PriorityQueue.cs

LINQ

Query란 “데이터 집합에서 데이터를 검색하는 문법”

LINQ는 쉽게 말하면 Collection (≈자료 구조)를 작은 DB로 생각하고 Query를 통해 정보를 가공 및 연산을 하는 C# 문법 (기법)이다. (꼭 자료 구조이어만 하는 것은 아님)

LINQ는 두 가지 형태로 쓰인다.

1. Query Syntax
   1. SQL과 같이 Query문을 통해 자료를 가공하는 방식 (SQL에 가까운 문법)
2. Method Chaining
   1. 반환되는 객체의 메소드를 연속적으로 호출하여 Query하는 방식 (기존 프로그램 언어에 가까운 문법)

using System.Linq;

public static void main(string[] args)
{
	//1. 데이터 소스
	int[] number = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		
	////////////////////////////////////////////////////////////
		
	//2. Query
	//2-1. Query Syntax
	IEnumerable<int> even = from num in number where num % 2 == 0 orderby num select num;
	//even은 "반복자 (Iterator)" 타입이다.
	//result : 2, 4, 6, 8, 10
		
	//2-2. Method Chaining
	IEnumerable<int> odd = number.where(num => num % 2 == 0).orderby(num);
	//result : 1, 3, 5, 7, 9
		
	////////////////////////////////////////////////////////////
		
	//3. Query 실행문
	foreach(var num in number) Console.WriteLine($"{num}");
}

LINQ는 3 가지 부분으로 나뉜다.

1. 데이터 소스
   1. LINQ로 Query하기 위해 데이터 소스에 무엇인가 해주어야 하는 과정은 없다.
   2. 데이터 소스가 IEnumerable<T>를 구현한 객체라면 자료 구조뿐 아니라 어떤 데이터 소스도 Query할 수 있다.
2. Query
   1. 데이터 소스 or 소스에서 검색할 데이터를 지정한다.
   2. 필요하다면, orderby, groupby 등의 키워드로 Query 변수에 가공해서 저장할 수 있다.
   3. 중요한 것은, Query 변수에는 데이터가 들어가 있는 것이 아니라 “해당 데이터를 구성하는 방법”이 들어있다.
   4. “지연 실행”으로 나중에 해당 Query 정보가 필요할 때 메모리에 올라가는 것으로 최적화를 구현했다.
3. Query 실행문
   1. 위 “Query” 항목에서 “지연 실행”으로 인해 실제 데이터가 들어가 있지 않다고 했지만, 즉시 실행하여 메모리에 올라가게 하는 Query 연산들이 있다.
   2. Scalar 결과값 (int, float …etc)을 반환하는 Query들은 연산을 위해 내부 구현에서 foreach를 돌기 때문에 Query를 즉시 실행하여 값을 반환한다.
   3. 또한 ToList() or ToArray()를 통해 해당 Query 정보를 List화 해서 메모리에 올려 캐싱 할 수 있다.

using System.Linq;

public static void main(string[] args)
{
	int[] number = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		
	//즉시 실행되어 Scalar값 (여기선 Double형)이 메모리에 올라가 있다.
	var evenNumAver = number.Where(num => num % 2 == 0).Average();
		
	var oddNumList = number.Where(num => num % 2 == 1).ToList();
}

IEnumerable<T> 타입이거나, 여기서 파생된 타입 혹은 IOrderedEnumerable<TElement> 타입인 경우 “지연 실행”을 지원하며 “Query 문에 대한 결과를 만드는 정보”만을 가지고 있게 된다.

중요한 점은, “지연 실행”된 Query에 대해서는 “원본 데이터 소스에 변경이 있다면, 그 변경을 적용한 결과를 실행 시점에 반환한다는 점”이다.

static void Main(string[] args)
{
	List<int> numbers = new List<int>();
		
	for (int i = 1; i <= 10; ++i) numbers.Add(i);
	//numbers의 원소 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
		
	var evenNum = numbers.Where(num => num % 2 == 0).OrderBy(num => num);
		
	foreach (var num in evenNum) Console.Write(num + " ");
		
	Console.WriteLine();
		
	//원본 데이터 소스에 변경
	for (int i = 11; i <= 20; ++i) numbers.Add(i);
	//numbers의 원소 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }
		
	//Query에 대한 변경은 하나도 없지만, 기존 Query를 가지고 출력을 해보면??
	foreach (var num in evenNum) Console.Write(num + " ");
	Console.WriteLine();
}

데이터 소스가 변경 되었음에도, 변경을 적용한 Query에 대한 결과를 출력한다.

Command Pattern

1. Requirements를 캡슐화하여 특정 객체의 행동 및 기능에 필요한 정보(or 메소드들)과 특정 객체를 “분리”시켜 확장성과 유지 보수성을 높인 SW 디자인 패턴이다.
   
   즉, “작업 실행을 아는 객체”에서 “작업을 실행할 객체”를 분리할 수 있다.
   

   

2. Command Pattern에는 3가지 중요 클래스가 있다.
   
   1. Invoker

      

       
      1. Command를 실행하는 방법을 알고, 필요에 따라 Command들을 여러개 보유할 수 있다.
   2. Command <interface>

      

      
      
      1. ConcreteCommand가 반드시 상속받아서 구현해야하는 interface이다.
      2. Invoker가 가지고 있는(따로 저장하고 있거나, 매개 변수로 전달받은) 명령을 실행하기 위한 “공통된” Execute() 메서드를 노출한다.
   3. Receiver
      1. 명령을 받아서 수행할 수 있는 객체
         

         

3. Command Pattern은 대표적으로 다음과 같이 활용 할 수 있다.
   1. 실행 취소
      1. Invoker가 Command를 Stack에 저장했다가, 필요할 때 Pop()해서 재실행 할 수 있다.
   2. 매크로
      1. 여러가지 일들을 한 번에 순차적으로 처리하게 할 수 있다.
4. 아래는 유니티 엔진에서, Input을 받아서 해당 Input이 들어오면 Input에 맞는 Command가 실행되는 예제이다.
   1. PlayerController.cs

      

   2. MoveRight.cs

      

      1. 만약, 플레이어가 "D" Key를 눌렀을 때 "오른쪽으로 이동" 한 후 "공격"하는 행동을 한다고 해보자
      2. 그럼 PlayerCotroller에 "공격"에 대한 메소드를 정의하고 MoveRight의 Execute()에 공격에 대한 메소드를 호출해주기만 하면 1.의 요구사항을 쉽게 구현할 수 있다.
   3. MoveLeft.cs

      

   4. MoveFoward.cs

      

   5. Invoker

      

   6. InputHandler.cs

      

5. 실행하면 아래와 gif와 같이 플레이어 입력에 맞게 해당 Command를 실행하여 움직인다.

   

   https://github.com/MunHwaDong/Assignments/tree/main/Personal%20Study/Command%20Pattern

Stack

1. Stack은 나중에 들어온 원소가 제일 먼저 나오는 LIFO (Last-In-First-Out) 자료 구조 (= 집합)이다.
   

   

   
   
2. Stack은 “정의상 가장 늦게 들어온 원소(= Top)만 확인 할 수 있으며”, 중간에 존재하는 원소들은 확인할 수 없다.
   1. 중간에 있는 원소에 접근할 일이 있다면, Stack을 쓸 문제가 아닐 가능성이 높다.
   2. 이런 제한된 탐색으로 인해, Stack은 “Restrictions Data Structure (제한된 자료 구조)”라고 불린다.
3. Stack의 기본적인 구조는 다음과 같다.
   

   

4. Stack은 Top이 가르키는 원소에 대해서만 연산이 가해지는 특성으로 인해 “삽입”, “삭제”, “탐색”에 대해 O(1)의 시간 복잡도를 가진다.
5. Stack은 LIFO의 특성으로 인해 다음과 같이 활용 될 수 있다.
   1. Undo 기능
   2. DFS (깊이 우선 탐색)
6. Stack의 각 연산들에 대한 구현은 Github 링크 참조 https://github.com/MunHwaDong/Algorithm/blob/master/DataStructure/Stack.cs

Custom Editor 기초

Custom Editor Window

Custom Editor Window는 별도의 툴창을 만드는 기능으로, 기존 Unity Editor를 확장시킨다.

이를 통해, 기획자나 디자이너가 쓸 자동화 툴이나 특정 데이터를 시각화하는데 사용된다.

Custom Editor Window를 구현하기 위해서는 “EditorWindow” 를 상속받아야 한다.

작성한 Editor 스크립트는 프로젝트의 Editor 폴더 안에 위치해야 한다.

public class CustomEditorWindow : EditorWindow
{
    private string text = "Hello Window!!";
    
    private float sliderValue = 0.0f;
    private Color colorValue = Color.white;
    
    //Unity Editor 상단의 Window 항목에 "커스텀 창"을 추가하는 함수
    [MenuItem("Window/Custom Editor")]
    public static void ShowWindow()
    {
        GetWindow<CustomEditorWindow>("My Custom Editor");
    }

    //OnGUI는 Custom Editor Window의 UI를 그리는 함수
    private void OnGUI()
    {
        //텍스트 필드 생성
        //EditorGUILayout, GUILayout을 사용하여 "버튼", "텍스트 필드", "슬라이더"등의 GUI 요소를 쉽게 추가할 수 있다.
        text = EditorGUILayout.TextField("Input Text", text);
    
        //버튼 생성
        if (GUILayout.Button("Print Text"))
        {
            Debug.Log(text);
        }

        colorValue = EditorGUILayout.ColorField("Select Color", colorValue);
        sliderValue = EditorGUILayout.Slider("Slider Value", sliderValue, 0, 100);

        if (GUILayout.Button("Apply Color"))
        {
            Debug.Log($"Slider Value: {sliderValue}, Selected Color: {colorValue}");
        }
        
        //EditorWindow를 상속 받는 객체도 OnEnable()/OnDisable(), Update()를 구현할 수 있다.

        //OnEnable() / OnDisable()
        //  Editor Window가 열릴 때 또는 닫힐 때 호출 되는 함수.
        //  Window가 열릴 때 초기화 작업을 하거나 닫힐 때 특정 행동을 할 수 있다.

        //Update()
        //  Window가 활성화 될 때마다 호출되며, 게임 오브젝트를 실시간으로 업데이트 하거나
        //  Editor의 데이터를 반영할 때 유용
    }
}

어떤 것을 먼저 생성했는지에 따라, 어느 순서로 배치될지 결정됨

슬라이더바를 먼저 생성 했을 때

색상 선택 팔레트 먼저 생성 했을 때

EditorWindow를 활용하여 오브젝트를 쉽게 배치하는 “레벨 디자인 툴”의 예시

사용자가 선택한 프리팹을 여러 개 랜덤 배치하는 툴

1. 주요 메소드
   1. EditorGUILayout.ObjectField()
      1. 프리팹 선택 필드를 생성, Project View에 있는 프리랩을 Drag & Drop해서 등록할 수 있다.
   2. EditorGUILayout.IntField()
      1. 정수를 입력 받을 수 있는 창을 생성
   3. EditorGUILayout.FloatField()
      1. 실수를 입력 받을 수 있는 창을 생성
   4. GUILayout.Button()
      1. Button 오브젝트를 Window에 생성하며 버튼 OnClick 이벤트가 발생하면 Bool값을 return한다.
      2. 따라서, If 문과 같이 사용하는 경우가 많다.
   5. EditorUtility.DisplayDialog()

      

      
      
      1. 예외가 발생했을때 Error Window를 띄우는데 사용된다.
   6. PrefabUtility.InstantiatePrefab()
      1. 프리팹을 씬(Scene)에 인스턴스화 한다.
   7. Undo.RegisterCreatedObjectUndo()
      1. 배치된 프리팹을 Undo 히스토리에 추가하여, 필요할 때 Ctrl+Z로 되돌릴 수 있다.
2. Prefab을 등록하고 버튼을 눌러 월드에 랜덤하게 배치하고 “Ctrl + z”로 Undo하는 모습을 확인 할 수 있다.

자세한 구현 코드는 Github에서 확인

https://github.com/MunHwaDong/Assignments/blob/main/Personal%20Study/Custom%20Editor/LevelDesignTool.cs Study/Custom Editor

LinkedList (개념, 직접 구현)

1. LinkedList는 다음 노드로의 포인터(or 참조)를 가지는 노드들의 “자료 구조”(= 집합)이다.
2. LinkedList의 기본적인 구조는 다음과 같다.
   

   

3. 가장 큰 특징으로 “메모리 공간 상에 비연속적으로 배치”되어 있다는 점이다.
   1. 따라서, 배열처럼 Random Access가 불가능하다.
   2. 배열의 Random Access는, 배열이 시작되는 주소를 가지고 index를 통해 원하는 위치를 바로 계산하여 접근하는 매커니즘이라 가능하지만
      (선형식 ax + b를 생각해서, ax (시작 주소값) + b (index)로 생각하면 좋을 것 같다.)
   3. LinkedList는 메모리상에 연속적으로 배치되어 있지 않기 때문에 저 매커니즘이 불가능하기 때문이다.
4. LinkedList는 두 가지 종류가 있으며, 각 종류에 따라 노드가 저장하는 정보의 수가 차이 난다.
   1. Singly LinkedList
      1. 각 노드가 자신의 다음 노드로의 포인터만을 저장하게 된다.
   2. Doubly LinkedList
      1. 각 노드가 자신의 앞, 뒤의 노드로의 포인터를 저장하게 된다.
      2. 이 경우 앞, 뒤로 자료 구조를 순회 할 수 있지만 추가적인 메모리를 요구한다.
         

         

5. 추가적으로 다음과 같은 특징이 있다.
   1. 맨 앞, 뒤에 대해 “삽입”, “삭제” 연산이 O(1)의 시간 복잡도를 가진다.
      1. Head, Tail (Doubly)의 포인터를 가지고 있으므로
   2. 임의의 위치에 “삽입”, “삭제”하는 연산과 검색 연산은 O(n)의 시간 복잡도를 가진다.
      1. LinkedList는 선형으로 한 줄로 이어져 있는 구조
      2. 해당 위치를 찾으려면 맨 앞 Head부터 쭉 찾아나가야한다.
      3. 최악의 경우 찾는 위치가 맨 끝일 수 있으니 O(n)
6. LinkedList는 아래와 같이 활용 될 수 있다.
   1. 음악 플레이 리스트
   2. 웹 브라우저의 뒤로가기 앞으로 가기
   3. 다항식의 표현
7. 삽입, 삭제, 검색의 구체적인 구현은 github 링크를 참조

Algorithm/DataStructure/LinkedList.cs at master · MunHwaDong/Algorithm

LinkedList (C# Collection)

1. C#에서는 “System.Collection.Generic” 네임 스페이스에서 LinkedList<T>를 제공하고 있다.
2. C#에서 제공하는 LinkedList는 Doubly LinkedList이다.
3. 주요 속성으로 3가지가 있다.
   1. Count
      1. 현재 LinkedList의 Node의 개수를 저장한다.
   2. First
      1. LinkedList의 첫 원소를 가르킨다 (= Head)
   3. Last
      1. LinkedList의 마지막 원소를 가르킨다 (= Tail)
   4. LinkedList가 비어있는 경우, First/Last는 null을 가르킨다.
4. 주요 메소드들은 아래와 같다.
   1. void AddFisrt(T)
      1. LinkedList의 맨 앞에 T를 추가한다.
   2. void AddLast(T)
      1. LinkedList의 맨 뒤에 T를 추가한다.
   3. void AddAfter(LinkedListNode<T>, T) / void AddBefore(LinkedListNode<T>, T)
      1. 주어진 LinkedListNode<T>의 앞/뒤에 T를 추가한다.
   4. Remove(LinkedListNode<T>)
      1. 주어진 LinkedListNode<T>를 삭제한다.
   5. void Remove(T)
      1. LinkedList에서 Remove에 주어진 값(= T)을 검색해서 처음으로 T와 같은 값을 가지는 노드를 삭제한다.
   6. LinkedListNode<T> Find(T)
      1. LinkedList에서 Find에 주어진 값(= T)를 검색해서 처음으로 T와 같은 값을 가지는 노드를 return 한다.

   using System.Collections.Generic;
   
   public static void Main(string[] args)
   {
               LinkedList<int> list = new LinkedList<int>();
   
               list.AddLast(1);
               //1
               list.AddLast(2);
               //1, 2
               list.AddLast(3);
               //1, 2, 3
   
               list.AddFirst(9);
               //9, 1, 2, 3
               list.AddFirst(8);
               //8, 9, 1, 2, 3
               list.AddFirst(7);
               //7, 8, 9, 1, 2, 3
   
               LinkedListNode<int> node = list.Find(9);
               list.AddAfter(node, 10);
               //7, 8, 9, 10, 1, 2, 3
   
               list.AddLast(10);
               //7, 8, 9, 10, 1, 2, 3, 10
   
               list.Remove(10);
               //7, 8, 9, 1, 2, 3, 10
   
               list.Remove(node);
               //7, 8, 1, 2, 3, 10
   }
   

Iterator

1. Iterator는 자료 구조를 순차적으로 탐색할 수 있게 해주는 “디자인 패턴”이다.
2. 이를 통해, 자료 구조의 각 원소를 순회하는 방법을 정의할 수 있고 자료 구조 내부 구현을 숨길 수 있게 해준다.
   

   

3. Iterator는 아래와 같은 기능들을 가진다.
   1. 자료 구조의 각 원소들을 순차적으로 접근하는 기능
   2. 다음 위치로 이동하는 기능
   3. 현재 위치의 요소를 Return하는 기능
   4. 마지막에 도달했는지를 알려주는 기능
4. C#에서는 “IEnumerator<T>”와 “IEnumerable<T>”를 상속받아서 구현할 수 있다.
   1. IEnumerable<T>
      1. 자료 구조를 순회할 수 있는 기능을 제공하며, GetEnumerator() 메소드를 통해 Iterator (C#에서는 열거자, IEnumerator)를 반환한다.
   2. IEnumerator<T>
      1. 각 요소를 순회하는 Iterator로 다음 위치로 이동, 해당 위치의 요소 반환하는 기능을 제공

public class LinkedList<T> : IEnumerable<T>
{
    public Node<T> Head { get; private set; }
    public Node<T> Tail { get; private set; }
    
    //Implement...
    
    //자료 구조에 상속 받아서, Iterator를 제공하는 메소드를 구현한다.
    public IEnumerator<T> GetEnumerator()
    {
        return new MyLinkedListIter<T>(Head);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

//Iterator Class 구현
public class LinkedListIter<T> : IEnumerator<T>
{
		private Node<T> _head;
    private Node<T> current;

    public MyLinkedListIter(Node<T> head)
    {
        _head = head;
        current = null;
    }
    
    //LinkedList의 경우
    //해당 Node의 Next를 참조하면 이동 할 수 있다.
    public bool MoveNext()
    {
        if (current == null)
        {
            current = _head;
        }
        else
        {
            current = current.Next;
        }

        return current != null;
    }
		
		//Iterator(여기선 열거자)를 초기화한다.
    public void Reset()
    {
        current = null;
    }
		
		//현재 위치의 요소(자료)를 Return한다.
    public T Current
    {
        get
        {
            if (current == null) throw new InvalidOperationException();
            return current.Data;
        }
    }

		//Non-Generic형식의 자료를 반환
		//C#의 모든 객체는 object 타입을 상속받으므로
    object IEnumerator.Current => Current;

		//자원을 반환하는 메소드
    public void Dispose()
    {
	    //여기서는 딱히 쓰는 자원이 없으니 빈 메소드로 둔다.
    }
}

Lambda

1. 일급 객체 (First - Class - Object)
   1. 프로그래밍 언어에서 값으로 표현되고 전달 될 수 있는 표현형, 형식이다.
      Ex) C++의 문자열은 문자들의 배열의 주소값이고 값으로써 사용할 수 없으니 일급 객체가 아니다.
2. 고차 함수
   1. 함수의 Argument로 함수를 받거나, Return 값이 함수인 경우 “고차 함수”라고 한다.
3. Lambda
   1. 이름이 없는 익명 함수로써 구현부만 존재하는 함수로 고차 함수의 Argument나 Return값으로 사용된다.
   2. C#의 Lambda는 “대리자 (Delegate)”형식으로 변환 될 수 있고 Lambda의 Argument와 Return 타입으로 대리자의 형식을 정의한다.
      1. Lambda의 Return이 없는 경우(void) : Action<T1, … , T2>
      2. Lambda의 Return이 있는 경우 : Func<T1, … , Tn, Return type>

      //Return이 없는 경우
      Action<string> Concat = (x) => Console.WriteLine(x + "World!");
      
      Action Display = () => Console.WriteLine();
      
      //Return이 있는 경우
      Func<int, int> pow = x => x * x;

   3. Lambda는 2 가지 종류가 있다.
      1. Expression Lambda
         1. ⇒ 연산자 옆에 Expression이 있는 Lambda
         2. Expression-Lambda 같은 경우 값을 반환한다.

         Func<int, int> pow = x => x * x;
         

      2. Statement Lambda
         1. ⇒ 옆에 Statement가 있는 Lambda
         2. Statement는 여러 줄이 될 수 있지만, 보통 2~3줄로 작성한다. (Expression : 계산되고 “값으로” 저장되는 코드, Expression은 어떤 형태로든 값을 만들어 낸다. Statement : 작업을 수행하거나 흐름을 제어하는 등의 코드, Statement는 코드의 Block을 형성하고 프로그램의 흐름을 만들어 낸다.)

         Action<string> Hello = name => 
         		{ string hello = $"Nice to meet you, {name}";
         			Console.WriteLine(hello);
         		}
         

   4. Lambda Argument
      1. 입력 매개 변수는 “( )”를 통해 지정할 수 있다. 입력 매개 변수가 1개 일 때는 ( )를 생략할 수 있다.
      2. “ , “로 두 개 이상의 Argument를 지정할 수 있으며 암시적/명시적으로 타입을 지정할 수 있다.