08/11

이우석·2023년 8월 11일

SBS 국기수업

목록 보기

17/120

자료구조

Array List
연속된 데이터의 묶음입니다
모든 자료구조의 가본형이 되는 자료구조 입니다.
C++에선 Vector 클래스로 구현되어 있습니다.

Array 입장에서, Array List는 Array 기능의 확장이라 볼 수 있다.
Element는 indexr값에 의해 접근, 수정, 삭제가 가능합니다.
잘못된 index에는 에러를 던집니다 (리턴이 아닌 throw)

Array List interface methods (TODO)
Get(index)
Set(index, Object)
Add(index, Object) : 뒷쪽의 다른 요소 밀어냄
Remove(index) : 뒷쪽의 다른 요소 당김

Array List Interface methods (선택)
Size() : 현재 Array List에 담긴 element의 수를 반환합니다.
IsEmpty() : 현재 array List가 비어 있는 지 여부를 반환합니다.

Array를 이용한 Array List 구현
크기가 N인 A를 이용
변수 n Array List의 현재 크기를 항상 저장해야한다.
Get(index) 메서드는 o(1)시간 안에 A[i]값을 반환합니다.
Set(index, object) 메서드는 o(1)시간 안에 A[i] = o를 수행합니다. (구현하기에 따라 t = a[i]를 먼저 수행한 후 A[i] = o를 수행하고 리턴값으로 t를 반환합니다)

Array List에 데이터 삽입 (Insertion)
Add(index, object) 메서드 동작을 위해 index번째 공간에 object를 저장할 수 있도록 n-1개의 데이터가 한칸씹 움직일수 있는 동작과 충분한 시간이 필요하다.
Worst case (i=0 일때)의 동작시간은 o(n)시간이 필요합니다.

Array List에 데이터 제거 (Remove)
메서드가 동작하면제거된 i번쨰 공간이 빈 공간으로 남지 않도록 n-i-1 개의 데이터가 한 칸 왼쪽으로 움직이는 동작 수행이 필요합니다.
(A[index+1], A[n-1])
Worst case (i=0) 일때 의 동작시간은 o(n)의 동작 시간이 필요합니다.

Performance

Array(배열)을 확용한 구현방법에서의 Performance

저장공간의 사용안 데이터의 크기인 n 만큼 사용됩니다.
Size, IsEmpty, Get, Set 메서드의 동작시간은 o(1)입니다.
Add, Remove 메서드의 동작시간은 o(n)입니다.

Circular Array를 사용하면 특별하게 Add(0, x)와 Remove(0)의 동작시간이 o(1) 입니다.

Add 메서드의 동작 과정 중 Array의 공간이 가득 찼을 때, 다음과 같은방법으로 반응을 구현할 수 있습니다.

Exception 을 던진다.
기존의 Array보타 1 혹은 충분히 긴 Array를 생성해 기존 데이터를 복사해 넣고 추가된 데이터를 집어 넣는다.

배열을 활용한 구현 방법에서의 Performance

저장공간의 사용은 데이터의 크기인 n 만큼 사용됩니다.
Size, isEmpty, Get, Set 메서드의 동작시간은 o(1)입니다.

[과제1]
ArrayList를 Class로 직접 구현해보기

element의 자료형은 object 이다.

Add, Insert 성공 여부를 bool로 리턴
(insert에선 인덱스 번호를 지정하기에 false인 경우가 생김)
false 리턴하며 메시지 출력

Remove 성공 여부를 bool로 리턴, 에러메시지 출력

Set, Get은 프로퍼티로 만든다. (인덱서 활용) [] 이용한다. null을 반환할 수도 있음

Count와 IsEmpty는 프로퍼티로 만든다.

Capacity를 만들어 현재 크기를 리턴한다.

Capacity가 부족할 경우 8씩 증가한다.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LearnAlgorithm_DataStructure
{
	internal class MyArrayList<T>
	{
		public MyArrayList()
		{
			MyArray = new T[0];
		}

        private const int CapacityUnit = 8;
        private T[] MyArray;
		public int Size
		{
			get { return _Size; }
		}
		private int _Size = 0;

		public T this[int index]
		{
			get
			{
                if (_Size <= index)
				{
                    throw new IndexOutOfRangeException();
                }

				return MyArray[index];
            }

			set
			{
				if (_Size <= index)
				{
                    throw new IndexOutOfRangeException();
                }

                MyArray[index] = value;
            }
		}

        public int Count
		{
			get
			{
				if (MyArray == null)
				{
					return 0;
				}

				return _Size;
            }
		}

		public bool IsEmpty
		{
			get { return Count == 0; }
		}

		private void Expand()
		{
			Array.Resize(ref MyArray, MyArray.Length + CapacityUnit);
		}

		public bool Add(T value)
		{
			if(MyArray.Length <= _Size)
			{
                Expand();
            }

            MyArray[_Size++] = value;

			return true;
		}

		public bool Insert(int index, T value)
		{
            if (index >= _Size || index < 0)
			{
                Console.WriteLine($"Insert Error : 잘못된 index {index}");
                return false;
			}

			if(_Size + 1 > MyArray.Length)
			{
				Expand();
			}

			int lastIdx = _Size - 1;
			for(int i = lastIdx; i >= index; i--)
			{
				MyArray[i + 1] = MyArray[i];
			}
            MyArray[index] = value;

			_Size++;

            return true;
		}

		public bool Remove(int index)
		{
            if (index >= _Size || index < 0)
            {
                Console.WriteLine($"Remove Error : 잘못된 index {index}");
                return false;
            }

			int end = _Size - 1;
            for (int i = index; i < end; i++)
            {
                MyArray[i] = MyArray[i + 1];
            }

			_Size--;

            return true;
		}

		public int Capacity()
		{
            return MyArray.Length;
		}

		public void test()
		{
            Console.WriteLine($"Count : {Count}");
            Console.WriteLine($"Capacity() : {Capacity()}");

            string output = string.Empty;
			foreach (var item in MyArray)
			{
				if (item != null)
				{
					output += item;
				}
				else
				{
					output += "(null)";
				}

				output += ", ";
			}

            Console.WriteLine(output.TrimEnd(' ').TrimEnd(','));
        }
	}
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LearnAlgorithm_DataStructure
{
    internal class Program
    {
        static void Main()
        {
            try
            {
                

                #region [string]
                {
                    var myArrayList = new MyArrayList<string>();

                    Console.WriteLine("===== Count =====");
                    myArrayList.test();
                    Console.WriteLine($"IsEmpty : {myArrayList.IsEmpty}");
                    Console.WriteLine();
                    Console.WriteLine();

                    Console.WriteLine("===== 1개 값 Add =====");
                    myArrayList.Add("하나");
                    myArrayList.test();
                    Console.WriteLine($"IsEmpty : {myArrayList.IsEmpty}");
                    Console.WriteLine();
                    Console.WriteLine();

                    Console.WriteLine("===== 7개 값 Add =====");
                    myArrayList.Add("둘");
                    myArrayList.Add("둘");
                    myArrayList.Add("둘");
                    myArrayList.Add("둘");
                    myArrayList.Add("둘");
                    myArrayList.Add("둘");
                    myArrayList.Add("둘");
                    myArrayList.test();
                    Console.WriteLine();
                    Console.WriteLine();

                    // 8개 이후
                    Console.WriteLine("===== 4개 값 Add =====");
                    myArrayList.Add("셋");
                    myArrayList.Add("셋");
                    myArrayList.Add("셋");
                    myArrayList.Add("셋");
                    myArrayList.test();
                    Console.WriteLine();
                    Console.WriteLine();

                    Console.WriteLine("===== Insert(0, \"넷\"); =====");
                    myArrayList.Insert(0, "넷");
                    myArrayList.test();
                    Console.WriteLine();
                    Console.WriteLine();

                    Console.WriteLine("===== Insert(3, \"넷\"); =====");
                    myArrayList.Insert(3, "넷");
                    myArrayList.test();
                    Console.WriteLine();
                    Console.WriteLine();

                    Console.WriteLine("===== Insert(-1, \"넷\"); =====");
                    myArrayList.Insert(-1, "넷");
                    myArrayList.test();
                    Console.WriteLine();
                    Console.WriteLine();

                    Console.WriteLine("===== Insert(100, \"넷\"); =====");
                    myArrayList.Insert(100, "넷");
                    myArrayList.test();
                    Console.WriteLine();
                    Console.WriteLine();

                    Console.WriteLine("===== Remove(0); =====");
                    myArrayList.Remove(0);
                    myArrayList.test();
                    Console.WriteLine();
                    Console.WriteLine();

                    Console.WriteLine("===== Remove(11); =====");
                    myArrayList.Remove(11);
                    myArrayList.test();
                    Console.WriteLine();
                    Console.WriteLine();

                    Console.WriteLine("===== Remove(20); =====");
                    myArrayList.Remove(20);
                    myArrayList.test();
                    Console.WriteLine();
                    Console.WriteLine();

                    Console.WriteLine("===== GET myArrayList[0] =====");
                    Console.WriteLine(myArrayList[0]);
                    myArrayList.test();
                    Console.WriteLine();
                    Console.WriteLine();

                    Console.WriteLine("===== SET myArrayList[0] = \"하나둘셋\" =====");
                    Console.WriteLine(myArrayList[0] = "하나둘셋");
                    myArrayList.test();
                    Console.WriteLine();
                    Console.WriteLine();
                }
                #endregion [string]

                
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.ToString());
            }

            Console.ReadKey();
        }
    }
}

Linked List
연속된 데이터의 묶음입니다.
Node, Link(Pointer), Head, Tail(option) 로 구성되어 있습니다.

Linked List는 다음과 같은 세부 구현 형태가 있습니다.

Singly Linked List
- Link가 한쪽 방향으로만 연결되어 있는 형태
Doubly Linked List
- Link가 양쪽 방향으로 연결되어 있는 형태
Circularly Linked List
- Tail Node의 Link가 Head와 연결되어 있는 형태 (위 두개는 Tail 의 next link는 null)
- 실은 Head와 Tail의 구분이 없다. (하지만 편의룰 위해 아무 Node 하나에 Cursor를 둔다)

[과제2]
Doubly Linked List 를 Class로 직접 구현해보기

element의 자료형은 object 이다.

Add, Insert 성공 여부를 bool로 리턴
(insert에선 인덱스 번호를 지정하기에 false인 경우가 생김)
false 시 리턴 전 메시지 출력

Remove 성공 여부를 bool로 리턴, 에러메시지 출력

Set, Get은 프로퍼티로 만든다. (인덱서 활용) [] 이용한다. null을 반환할 수도 있음

Count와 IsEmpty는 프로퍼티로 만든다.

head, tail을 반드시 만든다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LearnAlgorithm_DataStructure
{
	public class LineNode<T>
	{
		public T Value;
		public LineNode<T> PrevLink;
		public LineNode<T> NextLink;

		public LineNode()
		{
			Value = default(T);
			NextLink = PrevLink = default(LineNode<T>);
		}

		public LineNode(T value)
		{
			Value = value;
			NextLink = PrevLink = null;
		}

		public LineNode(T value, LineNode<T> prev)
		{
			Value = value;
			PrevLink = prev;
			NextLink = null;
		}

		public LineNode(T value, LineNode<T> prev, LineNode<T> next)
		{
			Value = value;
			PrevLink = prev;
			NextLink = next;
		}
	}

	class MyLinkedList<T>
	{
		public int Count { get { return _Count; } }
		private int _Count = 0;

		public bool IsEmpty { get { return _Count == 0; } }

		public LineNode<T> Head, Tail;

		public MyLinkedList()
		{
			Head = null;
			Tail = null;
		}

		public T this[int index]
		{
			get { return Find(index).Value; }
			set
			{
				LineNode<T> node = Find(index);
				if (node == default(LineNode<T>))
				{
					Console.WriteLine("SET 오류 : node를 찾을 수 없음");
					return;
				}

				node.Value = value;
			}
		}

		public LineNode<T> Find(int index)
		{
			if (index < 0 || index >= _Count)
			{
				Console.WriteLine($"오류 : {index}는 인덱스 범위를 벗어남");
				return default(LineNode<T>);
			}

			int mid = _Count / 2;
			int fromStart = Math.Abs(mid - index);
			int fromEnd = Math.Abs(index - mid);
			LineNode<T> result;

			if(fromStart >= fromEnd)
			{
				result = Head;
				for (int i = 0; i < index; i++)
				{
					result = result.NextLink;
				}
				
				return result;
			}

			result = Tail;
			for (int i = _Count - 1; i > index; i--)
			{
				result = result.NextLink;
			}

			return result;
		}

		public bool Add(T value)
		{
			if (_Count >= 2)
			{
				LineNode<T> Prev = Tail;
				Tail = new LineNode<T>(value, Prev);
				Prev.NextLink = Tail;
				_Count++;
				return true;
			}

			if (_Count == 0)
			{
				Head = new LineNode<T>(value);
				_Count++;
				return true;
			}

			if (_Count >= 1)
			{
				Tail = new LineNode<T>(value, Head);
				Head.NextLink = Tail;
				_Count++;
				return true;
			}

            Console.WriteLine("Add 오류 : 기타 오류 발생");
            return false;
		}

		public bool Insert(int index, T value)
		{
			LineNode<T> oldNode = Find(index);
			if (oldNode == default(LineNode<T>))
			{
				return false;
			}

			var newNode = new LineNode<T>(value, oldNode.PrevLink, oldNode);
			if (oldNode.PrevLink != null)
			{
				oldNode.PrevLink.NextLink = newNode;
			}
			oldNode.PrevLink = newNode;
			_Count++;

			if (index == 0)
			{
				Head = newNode;
			}
			else if(index == _Count - 1)
			{
				Tail = newNode;
			}

			return true;
		}

		public bool Remove(int index)
		{
			LineNode<T> removeNode = Find(index);
			if (removeNode == default(LineNode<T>))
			{
				return false;
			}

			if (index == 0)
			{
				Head = removeNode.NextLink;
			}
			else if (index == _Count - 1)
			{
				Tail = removeNode.PrevLink;
			}

			if (removeNode.PrevLink != default(LineNode<T>))
			{
				removeNode.PrevLink.NextLink = removeNode.NextLink;
			}

			if (removeNode.NextLink != default(LineNode<T>))
			{
				removeNode.NextLink.PrevLink = removeNode.PrevLink;
			}

			return true;
		}

		public void Print()
		{
			string output = string.Empty;
			LineNode<T> current = Head;
			while (current != null)
			{
				output += current.Value;
				output += ", ";
				current = current.NextLink;
			}
			Console.WriteLine(output.Trim(' ').TrimEnd(','));
		}
	}
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LearnAlgorithm_DataStructure
{
	internal class Program
	{
		static void Main()
		{
			LinkedListTest();

			Console.ReadKey();
		}

		static void LinkedListTest()
		{
			var myLinkedList = new MyLinkedList<object>();
            Console.WriteLine("=== 값 3개 Add ===");
            myLinkedList.Add(1);
			myLinkedList.Add(2);
			myLinkedList.Add(3);
			myLinkedList.Print();
            Console.WriteLine();

			Console.WriteLine("=== Get, Set ===");
            Console.Write("GET : myLinkedList[1] = ");
            Console.WriteLine(myLinkedList[1]);
			Console.WriteLine("SET : myLinkedList[1] = 4;");
			myLinkedList[1] = 4;
            myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Insert(0, 5) ===");
			myLinkedList.Insert(0, 5);
			myLinkedList.Print();
            Console.WriteLine();

			Console.WriteLine("=== Insert(2, 5) ===");
			myLinkedList.Insert(2, 5);
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Insert(4, 5) ===");
			myLinkedList.Insert(4, 5);
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Remove(5) ===");
			myLinkedList.Remove(5);
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Remove(0) ===");
			myLinkedList.Remove(0);
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Remove(3) ===");
			myLinkedList.Remove(3);
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Remove(1) ===");
			myLinkedList.Remove(1);
			myLinkedList.Print();
			Console.WriteLine();
		}

		static void ArrayListTest()
		{
			try
			{
				#region [string]
				{
					var myArrayList = new MyArrayList<string>();

					Console.WriteLine("===== Count =====");
					myArrayList.test();
					Console.WriteLine($"IsEmpty : {myArrayList.IsEmpty}");
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== 1개 값 Add =====");
					myArrayList.Add("하나");
					myArrayList.test();
					Console.WriteLine($"IsEmpty : {myArrayList.IsEmpty}");
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== 7개 값 Add =====");
					myArrayList.Add("둘");
					myArrayList.Add("둘");
					myArrayList.Add("둘");
					myArrayList.Add("둘");
					myArrayList.Add("둘");
					myArrayList.Add("둘");
					myArrayList.Add("둘");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					// 8개 이후
					Console.WriteLine("===== 4개 값 Add =====");
					myArrayList.Add("셋");
					myArrayList.Add("셋");
					myArrayList.Add("셋");
					myArrayList.Add("셋");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Insert(0, \"넷\"); =====");
					myArrayList.Insert(0, "넷");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Insert(3, \"넷\"); =====");
					myArrayList.Insert(3, "넷");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Insert(-1, \"넷\"); =====");
					myArrayList.Insert(-1, "넷");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Insert(100, \"넷\"); =====");
					myArrayList.Insert(100, "넷");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Remove(0); =====");
					myArrayList.Remove(0);
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Remove(11); =====");
					myArrayList.Remove(11);
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Remove(20); =====");
					myArrayList.Remove(20);
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== GET myArrayList[0] =====");
					Console.WriteLine(myArrayList[0]);
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== SET myArrayList[0] = \"하나둘셋\" =====");
					Console.WriteLine(myArrayList[0] = "하나둘셋");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();
				}
				#endregion [string]   
			}
			catch (Exception ex)
			{
				Console.WriteLine(ex.ToString());
			}
		}
	}
}

이우석

게임 개발자 지망생, 유니티 공부중!

이전 포스트

08/10

다음 포스트

08/11

SBS 국기수업

08/10

08/14

0개의 댓글