오늘 배운 내용
- Dictionary
- Graph
딕셔너리(Dictionary)
Dictionary<T>는키(Key)를 통해 저장된 데이터를 찾아가는 방식의 자료구조의 구현체이다.
- Hash Table
- 키(Key)와 값을 한쌍으로 저장하는 자료구조
- 각 키는 해싱(Hashing)되어 값을 가리키는 고유한 식별자 역할을 한다.
- 대부분의 경우 삽입, 삭제, 읽기, 검색 연산이 O(1)으로 빠르다
- Hash Table의 간단한 용어
- 단방향성
- 데이터를 해시 값으로 출력하는 것은 가능하지만 해시 값을 다시 원래의 키 데이터로 돌리는것은 불가능하다.
- 고정된 데이터의 길이
- 해시는 테이블 내에서 고유한 식별자로서 작용한다. 저장되는 데이터에 지문과 같은 역할을 한다.
- 어떤 데이터를 삽입하던 간에 해싱의 결과물은 항상 고정된 데이터의 길이를 가진다.
- 키(Key)
- 데이터를 저장하고 찾기 위해 사용되는 고유한 식별자
- 해시함수를 거쳐 데이터를 보관할 수 있는 식별코드(해시코드)로 전환된다.
- 값(Value)
- 키(Key)를 기준으로 한 위치에 저장되는 데이터
- 키를 통해 값에 엑세스 할 수 있다.
- 해시함수(Hash Function)
- 입력된 키를 해시테이블의 주소(해시코드)로 변환하는 함수
- 해시 함수의 성능을 결정짓는 중요한 요소
- 보관하고자 하는 테이블의 크기 내의 결과를 출력한다.
- 체이닝(Chaining)
- ex) 키가 해시 함수에 입력되어 해싱되고 첫 번째 키는 정상적으로 입력되고, 두번째 해싱 값이 첫 번째 해싱 값과 충돌된 상황.
- 배열의 원소를 연결리스트로 구현해서 같은 키 값을 가지는 데이터를 보관
- 개방 주소법 : 선형 탐사(Open Addressing : Linear Probing)
- 배열을 지정된 폭만큼 순회하면서 빈 공간에 바로 할당하는 방식
- 개방 주소법 : 제곱 탐사(Open Addressing : Quadractic Probing)
- 충돌 시 , 한번더 충돌 시 , 또 충돌 시 제곱 순으로 인덱스를 탐색하고 데이터를 보관하는 방식
- 개방 주소법 : 이중 해싱(Open Addressing : Double Hashing Probing)
- 충돌 시 충돌된 해시 값을 한 번 더 해싱한다. 충돌이 일어나지 않을 때까지 반복한다.
Dictionary
using System;
using System.Collections.Generic; // 이게 필요함
class Program
{
static void Main(string[] args)
{
Dictionary<string, MyClass> dict = new(3);
// 삽입(Add) O(1)
dict.Add("first", new MyClass(5));
dict.Add("second", new MyClass(17));
dict.Add("third", new MyClass(24));
dict.Add("fourth", new MyClass(12));
// 동일한 키를 추가하려고 하면 에러 발생
// TryAdd로 대응 가능함.
dict.TryAdd("first", new MyClass(7));
// 동일한 키를 추가하는데 실패한다면 추가하지않고 그냥 지나침
// 삭제(Remove) O(1)
dict.Remove("third");
// 읽기, 검색 : O(1)
// 추가된 키가없으면 에러 발생
//Console.WriteLine(dict["fourth"].Score);
MyClass mc = null;
if (dict.ContainsKey("first"))
{
dict.TryGetValue("first", out mc);
}
// 값 기반 검색 : 내부를 순회해야 함. O(n)
if (dict.ContainsValue(mc))
{
Console.WriteLine($"값 기반 검색 성공 {mc.Score}");
}
}
}
public class Myclass
{
public int Score { get; private set; }
public MyClass(int score)
{
Score = score;
}
}그래프(Graph)
- 비선형 자료구조이며, 데이터 간의 관계도를 표현하기 위한 자료구조이다.
- 대표적으로 그래프와 트리가 있으며 조건에 따라 그래프와 트리도 여러 종류로 나뉜다.
- 그래프와 트리
- 그래프
- 데이터(원소) 간의 다양한 연결 관계를 표현
- 정점(Vertex, Node)과 이들을 연결하는 간선(Edge)으로 구성된다.
- 간선에는 가중치, 혹은 방향이 포함될 수 있다.
- 반드시 모든 정점이 간선으로 연결되어야 하는 것은 아니다.
- 트리 (Tree)
- 데이터 간의 계층 구조를 정의하는 자료구조
- 각 노드는 하나의 부모 노드를 가진다.
- 루트 노드에서 시작해 리프 노드로 이어진다.
- 모든 노드가 전부 연결되어 있다.
- 비선형 구조는 방사형 스킬 트리 구조에서 사용 가능하다.
- 그래프 탐색 기법
- BFS(너비 우선 탐색) (Queue 사용)
- 주변에 있는 노드들을 탐색하면서 점점 탐색 범위를 넓혀가는 방식
- DFS(깊이 우선 탐색) (Stack 사용)
- 한쪽 방향으로 끝까지 진행한 후에 나머지 방향들도 반복하는 방식
.