[C#] Lec 14 - 노드 기반 자료구조

노드 기반 자료구조

연결 리스트 배열(linked list)

• 일반적인 배열 : 삽입과 삭제가 O(N) 연산
• Linked List : 배열 공간을 임의로 할당, 배열의 원소 하나당 메모리 1개
• 사용량 입장에서는 2배의 공간이 필요, 일반 배열은 비어있는 메모리 공간을 찾아야 하는데, 메모리의 빈 공간들에 할당하여 사용할 수 있으므로 메모리의 효율적인 사용이 가능.
• 삽입 연산 자체 : O(1) 단계. 해당 위치까지 간 뒤에 주소 바꿔주고 할당하고 다시 주소 바꿔주면 됨
• 삽입을 위해서 원하는 삽입 의치까지 읽기(O(N) ) 연산이 필요하므로 linkedlist 에서도 삽입 연산을 위해 O(N) 연산이 필요함
• 배열의 경우 : 앞에 삽입하면 최악 / 끝에 삽입할 때 최선
• 링크드리스트의 경우 : 앞에 삽입하면 최선(읽어줄게 얼마 없어서) / 끝에 삽입할 때 최악
• 삭제 연산 자체 : O(1) 단계. 해당 index의 값 삭제하고 주소만 바꿔주기.
• 삭제 연산을 위해 읽기 O(N) 연산 필요. (삽입과 거의 동일)
• LinkedList에서는 삽입과 읽기 삭제가 동시에 이루어지는 작업의 경우 훨씬 유리함.
• 일반적인 배열 : 병렬 처리 불가능. (순차적 처리만 가능)
• LinkedList : 병렬 처리 가능.
• 이중 연결 리스트 : 가운데 값을, 왼쪽에는 그 앞 index의 주소, 오른쪽에는 그 뒤 index의 주소를 입력. 맨 뒤에 삽입, 삭제도 O(1)로 가능

이진 트리 자료 구조

• 이진 검색이 가장 빠름. (빠른 검색을 위해 이진 검색 도입 필수적)
• 트리 자료 구조 (이중 링크드 리스트를 이용) - 이진 트리 만들기
• 검색이 매우 빠르고 구현이 간단함
• 삽입 : O(log N) 연산 필요.
• 삭제 : 복잡,
  1. 자식이 없는 노드 : 삭제
  2. 자식이 하나인 노드 : 노드 삭제하고 자식을 삭제된 노드에 대체
  3. 자식이 둘이 노드 : 삭제된 노드를 후속자 노드(삭제된 노드보다 큰 값 중 최솟값을 갖는 자식)으로 대체
  4. 후속자 노드에 오른쪽 자식이 있다면 후속자를 삭제된 노드가 있던 원래 자리에 대체, 후속자 노드의 오른쪽 자식을, 후속자 노드의 원래 부모의 왼쪽 자식으로 넣음

그래프 자료 구조

• 관계 리스트 (이차원 배열로 관계 리스트의 작성)
• 특정 노드와 연결된 노드를 알기 위해 모든 데이터베이스를 검색해야 함
• Dictionary를 이용해서 효율적으로 인접노드 검색가능
• 직접 커넥션이 없는 네트워크의 탐색 : 너비 우선 탐색, 깊이 우선 탐색이 존재

너비 우선 탐색

1. 현재 정점과 인접한 정점을 방문 → 이전에 방문한 적 없는 정점이면 방문했다고 표기, Queue에 추가.
2. Queue을 dequeue 해서 1을 반복
   • 연산의 종류 : 큐에서 정점 삭제 / 각 정점마다 해당 정점의 인접 정점을 방문
   • O(V) : 그래프의 정점 V개, (간선도 포함해야하므로)
   • 간선이 E개, 2E번 인접한 정점 확인 O(E)
   • O(V+E)

가중 그래프 : 다익스트라(Dijkstra’s Algorithm)

• 간선에 정보가 포함되어 있는 경우 - 최소 가격을 찾아줌
  1. 시작 지점 : 현재 정점
  2. 현재 정점에 인접한 모든 정점 확인하여 시작 정점으로부터 알려진 모든 위치의 가중치를 계산, 기록
  3. 다음 정점 : 시작 정점에서 도달 가능한, 방문하지 않은, 가장 저렴한 알려진 정점 찾음
  4. 그래프 내 모든 정점 방문할 때까지 1~3 반복
• 과정 자체는 O(N^2)이나, Queue 사용해 cost순 정렬하면 O(NlogN)으로 줄일 수 있음
• 경로 역추적 : linkedlist와 같이 각 노드별로 가장 저렴한 직전노드를 입력

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace PathFinding
{
    class Program
    {
        static void Main(string[] args)
        {
            City atlanta = new City("atlanta");
            City boston = new City("boston");
            City chicago = new City("chicago");
            City denver = new City("denver");
            City elpaso = new City("el paso");
            atlanta.Route.Add(boston, 100);
            atlanta.Route.Add(denver, 160);
            boston.Route.Add(denver, 180);
            boston.Route.Add(chicago, 120);
            chicago.Route.Add(elpaso, 80);
            denver.Route.Add(chicago, 40);
            denver.Route.Add(elpaso, 140);
            elpaso.Route.Add(boston, 100);
            PathFinder pf = new PathFinder();
            pf.Cities.Add(atlanta);
            pf.Cities.Add(boston);
            pf.Cities.Add(chicago);
            pf.Cities.Add(denver);
            pf.Cities.Add(elpaso);
            List<City> path = null;
            int minimumCost = pf.DijkstraPathFinding(atlanta, elpaso, ref path);

            foreach (var item in path)
            {
                Console.WriteLine(item);
            }
            Console.WriteLine(minimumCost);

        }
    }
    public class City
    {
        public string Name { get; set; }
        public Dictionary<City, int> Route { get; set; } = new Dictionary<City, int>();
        public City(string name)
        {
            Name = name;

        }
        public override string ToString()
        {
            return Name;
        }
    }
    public class PathFinder
    {
        public List<City> Cities { get; set; } = new List<City>();
        public int DijkstraPathFinding (City departure, City arrival, ref List<City> path)
        {
            if (!Cities.Contains(departure))
            {
                throw new ArgumentException("Departure city not included in cities.");
            }
            if (!Cities.Contains(arrival))
            {
                throw new ArgumentException("Arrival city not included in cities.");
            }
            City currentCity = departure;
            Dictionary<City, int> costs = new Dictionary<City, int>();
            List<City> visitedCities = new List<City>();
            Dictionary<City, City> parentCity = new Dictionary<City, City>();
            while (true)
            {
                visitedCities.Add(currentCity);
                foreach (var route in currentCity.Route)
                {
                    if (costs.ContainsKey(route.Key))
                    {
                        if (costs[route.Key] > costs[currentCity] + route.Value)
                        {
                            costs[route.Key] = costs[currentCity] + route.Value;
                            parentCity[route.Key] = currentCity;
                        }
                    
                    }
                    else
                    {
                        if (costs.ContainsKey(currentCity))
                        {
                            costs.Add(route.Key, route.Value + costs[currentCity]);
                            parentCity.Add(route.Key, currentCity);
                        }
                        else
                        {
                            costs.Add(route.Key, route.Value);
                            parentCity.Add(route.Key, currentCity);

                        }
                    }
                }
                int minimumCost = int.MaxValue;
                foreach (var item in costs)
                {
                    if (!visitedCities.Contains(item.Key))
                    {
                        if(minimumCost>item.Value)
                        {
                            minimumCost = item.Value;
                            currentCity = item.Key;
                        }
                    }
                }
                if (visitedCities.Count == Cities.Count)
                    break;
            }
            path = new List<City>(); 
            City searchingCity = arrival;
            while (true)
            {
                path.Add(parentCity[searchingCity]);
                searchingCity = parentCity[searchingCity];
                if (searchingCity == departure)
                    break;
            }
            path.Reverse();
            path.Add(arrival);
            return costs[arrival];
        }
    }
}

• A* algorithm : Cost , Heuristic (ex 도착지점까지의 거리) 의 합을 기준으로 국소 최적해 산출
• Heuristic이 도착지점으로 가는 지표 역할