알고리즘 강의

STACK

FIRST IN LAST OUT
LAST IN FIRST OUT

꽉 찼는데 PUSH ? OVERFLOW
비었는데 POP? UNDERFLOW
-> 메모리상의 OVERFLOW UNDERFLOW라고 생각하면 될 것 같다.

QUEUE

FIRST IN FIRST OUT
LAST IN LAST OUT

큐 크기 HEAD, TAIL 위치에 따라서 큐가 비었지만 넣지 못하는 순간이 있다. 공간이 비효율적으로 사용됩니다.

-> 이래서 circular QUEUE를 사용합니다.
-> depueue 덱 이것도 있습니다.

사실 head를 0으로 계속 유지하면서 pop할 때 마다 데이터를 끌어와도 되는데 이러면 시간복잡도상의 문제가 많이 생긴다.

GRAPH (비선형)

G(V,E)
V : 정점
E : 간선
현실 세계의 많은 구조들을 모델링 할 수 있는 틀

그래프의 분류 방법
1. 방향의 유무
방향성이 있는 그래프, 없는 그래프 (유향 그래프, 무향 그래프(양방향그래프))

2. 가중치의 유무
   가중치 그래프, 가중치 없는 그래프

용어
CYCLE
하나의 정점에서 간선들을 따라서 다시 본인으로 돌아갈 수 있다면 그것은 CYCLE 그래프

3. 연결의 유무
   연결 그래프 : 모든 정점들이 간선으로 연결된 그래프

그래프의 표현 방법

인접 행렬 -> 이차원 배열 이용

인접 리스트 -> 벡터 사용

좀 복잡하면 인접 리스트를 사용하는 것이 좀 더 좋다.

인접 리스트는 해당 노드에서 인접해있는 노드들을 다 모아둔 것

방향성이 있고 없고에 따라서 인접 리스트, 배열의 표현을 조금 주의해서 봐야합니다.

가중치가 없으면 1(연결) 0(비연결)로 표현한다.

간선에 가중치가 있는 경우 인접 행렬에는 가중치로 표를 채운다.
인접 리스트에는 (정점, 가중치)로 표현을 해준다.

C++ 기준으로 VECTOR 자료형 사용가능 : 배열과 비슷하게 사용 가능
간선에 가중치가 있으면 구조체 등을 사용하면 됩니다.

#include <vertor> 

(JAVA에는 C++의 VECTOR기능 없낭..)

TREE (비선형)

싸이클이 없는 연결된 그래프

트리의 지름
트리에서 임의의 두 노드사이 거리의 최댓값

트리의 정류
일반적인 트리, 이진 트리, 완전 이진트리
이진 트리가 가장 많이 사용되고 가장 좋다!
avl, red-black, spanning tree 이렇게 3가지 종류도 추가적으로 있다.

binary search tree
항상 자기 기준으로 왼쪽에 있는 값은 작고 오른쪽에 있는 값은 크다.

빠르긴한데
균형이 좋게 있다면 빠르지만
비균형 트리면 사실 느리다.

트리의 표현
그래프와 같다
근데 자식과 부모를 따로 구분해두면 좀 편하다.

maxHeap : root가 가장 최대값
minHeap : root가 가장 최솟값

트리의 순회
전위 중위 후위 순회 (재귀로 사용)