6/7 부트캠프 개발 TIL (자료구조)

오늘 특강에서 들은 내용은 데이터 구조이다.

 

대표적인 자료구조

• 리스트
• 스택
• 큐
• 트리

리스트

리스트는 자료들을 연결하는 형태인데 그림으로 표현하면

이 형태로 되어 있는데 C#으로 표현하면

List<int> scores = new List<int>();

scores.Add(1);
scores.Add(5);
scores.Add(4);
scores.Add(8);
scores.Add(3);
scores.Add(5);
scores.Add(4);

 

 

참고로 위 코드의 리스트는 배열처럼 인덱스별로 출력과 전달이 가능하지만 검색속도는 느리다는 점이다.

그리고 삭제할 시 종류가 있을텐데

scores.Remove(8);   //scores에 있는 8을 제거 (없는 값을 넣으면 예외가 된다)
scores.Clear();		//scores에 있는 데이터들을 모두 제거
scores.RemoveAt(2);   //scores에 있는 2번째 인덱스를 제거
scores.RemoveRange(2,4);   //현재 인덱스부터 4길이까지 제거

 

이렇게 있다.

 

그러나 데이터 구조상에서 생각하는 리스트는 다를 것이다.

바로 LinkedList라는 구조이다. 우선 그림으로 설명하자면

이런 그림을 보게 될 것이다. 여기서 데이터 구조 안에서 가장 많이 접하게 되는 리스트이다.

위의 보여준 그림은 단방향 리스트이다. 하지만 리스트는 이것만 있는 것이 아니라

이런 구조도 있는데 이건 양뱡향 리스트이다.

 

결론적으로 리스트는 데이터 내용과 다음 데이터를 연결해주는 링크로 구성되는 노드끼리 연결하는 구조로 되어있다.

            LinkedList<string> weekday = new LinkedList<string>();

            weekday.AddFirst("Tuesday");
            weekday.AddLast("Wednesday");
            weekday.AddFirst("Monday");

            foreach(var str in weekday)
            {
                Console.WriteLine(str);
            }

LinkedList의 장점은 검색속도가 빠르지만 List처럼 인덱싱이 불가능하고 삽입할 때 맨 앞이나 뒤에서 삽입해야 하는 단점이 있다.

하지만 유니티 상에서 이런 걸 잘 사용하지 않고 다른 분야에서 사용한다.

 

 

스택

스택은 맨 위에있는 걸 먼저 꺼내다는 개념으로 후입선출이라고 기법이다.

그림처럼 바구니에 물건을 집어넣을 때와 꺼낼 때 가장 위에 있는 것부터 꺼내는 것을 보면 이해가 갈 것이다.

집어넣는 것을 PUSH라 하고 꺼내는 것을 POP이라 한다. PUSH는 스택에 데이터를 집어넣는 동작이고 POP은 데이터를 꺼내면서 꺼낸 데이터를 출력할 수 있다.

            Stack<int> stack = new Stack<int>();

            stack.Push(1);
            stack.Push(2);
            stack.Push(3);
            Console.WriteLine(stack.Pop());
            Console.WriteLine(stack.Pop());
            stack.Push(4);

 

큐

큐는 스택과 비슷하지만 들어가는 방향과 나가는 뱡향이 다르다. 선착순의 개념으로 후입선출 기법이다.

파이프처럼 먼저 들어온 것이 먼저 나온 것이다.

들어온 것이 Enqueue, 나온 것이 Dequeue 스택처럼 꺼낼 때 데이터를 출력할 수 있다.

            Queue<int> queue = new Queue<int>();

            queue.Enqueue(1);
            queue.Enqueue(4);
            queue.Enqueue(2);
            Console.WriteLine(queue.Dequeue());
            queue.Enqueue(7);
            Console.WriteLine(queue.Dequeue());

 

 

트리

 

트리는 위의 셋이랑 차이점은 비선형 구조이다. 큐, 리스트, 스택은 선형 구조로 되어있다.

트리는 한 노드 아래에 자식노드들이 뻗어나가는 형태로 되어 있다.

맨 위에 있는 노드가 Root라고 불린다.

 

트리에는 여러가지 종류가 있지만 가장 대표적인 트리 구조는 2진 트리 기법이다.

2진트리 기법은 검색 효율이 가장 나쁘지만 단 2개 자식노드로 이루어져 구분하기 쉽다.

코드로 이진 트리를 구성하기 매우 어려우니 간단한 개념만 짚고 가자.\

 

2진 트리 기법은 데이터를 삽입했을 때 루트 값을 비교하여 왼쪽 혹은 오른쪽으로 자식노드에 삽입한다.

다음에 데이터들을 2진트리로 삽입하면

5, 7, 3, 9, 4, 12, 8

이진트리로 삽입한 결과가 이렇게 된다.

먼저 첫번째 5를 루트에 넣고

7이 5보다 크기 때문에 우측 노드에 삽입하고

3이 5보다 작기 때문에 좌측 노드에 삽입하고

9가 5보다 크고 7보다 크기 때문에 우측 노드에 삽입하고

4가 5보다 작고 3보다 크기 때문에 우측 노드에 삽입하고

12가 5보다 크고 7보다 크고 9보다 크기 때문에 우측 노드에 삽입하고

8이 5보다 크고 7보다 크고 9보다 작기 때문에 좌측 노드에 삽입한다.

 

만약에 9가 있는 데이터를 지우고 싶다면

루트 노드에서 9를 찾기 위해 현재 노드에 있는 데이터를 비교한다.

5 > 7 > 9

9를 제거하고 나머지 자식 노드들은 두 값을 비교하여 제일 작은 값이 중간 노드로 오게 된다.

 

by 스파르타 코딩클럽