[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) 연산 필요.
- 삭제 : 복잡,
- 자식이 없는 노드 : 삭제
- 자식이 하나인 노드 : 노드 삭제하고 자식을 삭제된 노드에 대체
- 자식이 둘이 노드 : 삭제된 노드를 후속자 노드(삭제된 노드보다 큰 값 중 최솟값을 갖는 자식)으로 대체
- 후속자 노드에 오른쪽 자식이 있다면 후속자를 삭제된 노드가 있던 원래 자리에 대체, 후속자 노드의 오른쪽 자식을, 후속자 노드의 원래 부모의 왼쪽 자식으로 넣음
그래프 자료 구조
- 관계 리스트 (이차원 배열로 관계 리스트의 작성)
- 특정 노드와 연결된 노드를 알기 위해 모든 데이터베이스를 검색해야 함
- Dictionary를 이용해서 효율적으로 인접노드 검색가능
- 직접 커넥션이 없는 네트워크의 탐색 : 너비 우선 탐색, 깊이 우선 탐색이 존재
너비 우선 탐색
- 현재 정점과 인접한 정점을 방문 → 이전에 방문한 적 없는 정점이면 방문했다고 표기, Queue에 추가.
- Queue을 dequeue 해서 1을 반복
- 연산의 종류 : 큐에서 정점 삭제 / 각 정점마다 해당 정점의 인접 정점을 방문
- O(V) : 그래프의 정점 V개, (간선도 포함해야하므로)
- 간선이 E개, 2E번 인접한 정점 확인 O(E)
- O(V+E)
가중 그래프 : 다익스트라(Dijkstra’s Algorithm)
- 간선에 정보가 포함되어 있는 경우 - 최소 가격을 찾아줌
- 시작 지점 : 현재 정점
- 현재 정점에 인접한 모든 정점 확인하여 시작 정점으로부터 알려진 모든 위치의 가중치를 계산, 기록
- 다음 정점 : 시작 정점에서 도달 가능한, 방문하지 않은, 가장 저렴한 알려진 정점 찾음
- 그래프 내 모든 정점 방문할 때까지 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이 도착지점으로 가는 지표 역할
댓글을 불러오는 중입니다.