그래프(Graph)

그래프는 정점들의 관계를 간선으로 표현하는 자료구조입니다.

그래프 구성

1. 유한한 정점의 집합
2. 정점을 이어주는 선인 간선의 유한한 집합.

그래프의 종류

1. 방향 VS 무방향
   방향 그래프의 경우 간선이 방향을 가지지만 무방향 그래프의 경우 간선이 방향을 가지지 않습니다.

2. 가중치 VS 비가중치
   가중치 그래프의 경우 간선에 가중치를 가지지만 비가중치 그래프의 경우 간선이 가중치를 가지지 않습니다.

그래프의 연산들

1. 간선을 나타낼 방법 정하기
2. 정점을 나타낼 방법 정하기
3. 간선 추가
4. 정점 추가
5. 간선 검색
6. 정점 검색
7. 간선 삭제
8. 정점 삭제
9. 그래프 순회(DFS, BFS)

그래프를 나타내는 방법

아래와 같은 그래프를 어떻게 컴퓨터의 물리적인 공간으로 표현할지 알아보겠습니다.

1. 인접 행렬

2. 인접 리스트

트라이(Trie)

접두사 트리라고도 불리며 문자열의 모음을 저장하는 자료구조입니다.
검색을 할 때 일부 단어만 입력해도 전체 검색 단어를 보여주는 기능에 쓰입니다.

트라이의 연산들

1. 노드 나타내기
2. 노드 추가
3. 노드 검색
4. 노드 삭제
5. 순회

세그먼트 트리(Segment Tree)

세그먼트 트리는 일반적으로 값의 집합에 대한 쿼리가 많을 때 사용합니다.
최소값, 최대값, 합계 등등 을 구할 수 있습니다.
세그먼트 트리는 배열을 사용하여 구현됩니다.

접미사 트리(Suffix Tree)

주어진 문자열의 모든 접미사를 저장하는 자료구조입니다.
왜 모든 접미사를 저장하는지 궁금할 수 있는데 텍스트에서 패턴을 찾기 위해 사용합니다.