Today 공부
- [자료구조/알고리즘] 자료구조 기초
- Stack
- Queue
- Graph
- Tree
- Binary Search Tree
자료구조 기초
자료구조?
대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있습니다.
자료구조의 종류는 매우 많으나, 그 많은 자료구조를 알아두면
어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있습니다.
Stack
데이터(data)를 순서대로 쌓는 자료구조
입력과 출력이 하나의 방향으로 이루어지는 제한적 접근
- ex)브라우저의 뒤로가기,앞으로가기
자료구조 정책:
LIFO(Last In First Out)
FILO(First In Last Out)
Queue
먼저 들어간 데이터(data)가 먼저 나오는 구조
- ex) 톨게이트
자료구조 정책:
FIFO(First In First Out)
LILO(Last In Last Out)
Graph
여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
한개의 점을 그래프에서는 정점(vertex)
하나의 선은 간선(edge)
그래프의 표현 방식: 인접 행렬 & 인접 리스트
인접행렬 :
서로 다른 정점들이 인접한 상태인지 표시한 행렬으로 2차원 배열의 형태이다.
A라는 정점과 B라는 정점이 이어져 있다면 1(true),
이어져 있지 않다면 0(false)로 표시한 일종의 표
- 인접행렬 사용 하는 경우 : 한개의 큰 표와 같은 모습을 한 인접행렬은 두 정점사이에 관계가 있는지 없는지 확인하기에 용이 합니다.
- 가장 빠른 경로를 찾고자 할 때 주로 사용됩니다.
인접 리스트 :각 정점이 어떤 정점과 인접한지 리스트의 형태료 표현
각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있습니다.
- 인접리스트 사용 하는 경우 : 메모리를 효율적으로 사용하고 싶을때
- 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지합니다.
알아둬야 할 그래프 용어 들
- 무(방)향그래프
- 진입차수(in-degree) / 진출차수(out-degree):
- 인접(adjacency) : 두 정점을 이어주는 간선이 있다면
이 두 정점은 인접하다고 야기합니다.- 자기 루프(self loop):
- 사이클(cycle):
Tree
데이터(data)를 순서대로 쌓는 자료구조
무방향 그래프의 한 구조,
하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있어 트리구조라 부른다
- 계층적 자료구조
- 비선형 구조
- 아래로만 뻗어나가 사이클이 없다
Binary Search Tree
데이터(data)를 순서대로 쌓는 자료구조
