- 스택
정의
스택은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 후입선출(LIFO) 형태의 선형 자료구조이다.
장점
- 구조가 단순해서 구현이 쉽다.
- 데이터 저장/읽기 속도가 빠르다.
단점
- 저장공간의 크기를 사전에 정의해줘야 한다.
- 저장공간의 낭비가 발생할 수 있다. (미리 최대 개수만큼 저장 공간 확보해야 함)
향후전망
저장공간의 낭비를 줄일 수 있는 자료구조가 나올 수 있겠다.
- 다중 스택
정의
하나의 기억공간에 여러 개의 스택으로 저장하는 자료구조
등장배경
스택의 오버플로를 해결하기 위해 등장
장점
공유 공간을 활용하여 저장공간을 절약할 수 있다.
단점
특정 스택 내부에만 원소가 많아서 다른 스택을 침범하는 문제가 발생할 수 있다.
- 스택의 후위 표기법(Postfix Notation)
중위 표현식 → 후위 표현식
- 예시 A * B + C
- 예시 A + B * C
- 큐
정의
큐는 삽읻된 순서대로 먼저 삽입된 데이터가 먼저 삭제되는 선입선출 (FIFO) 형태의 선형 자료구조이다.
장점
- 구조가 단순해서 구현이 쉽다.
- 데이터 저장/읽기 속도가 빠르다.
단점
- 앞에 요소를 한개 제거하고(dequeue) 첫번째인 front 위치를 한칸 뒤로 이동을 하게 되면, front가 +1 씩 커지면 앞에 있는 빈공간은 필요가 없어진다. 즉, 100개의 데이터가 들어 있고, front 위치가 99 위치에 있다면, 그 앞쪽에 있는 빈공간은 아무 쓸모 없어진다.
향후전망
저장공간의 낭비를 줄일 수 있는 자료구조가 나올 수 있겠다.
- 이동 큐
정의
전체 노드를 앞으로 이동시키는 큐
등장배경
큐의 단점 보완 위해 등장
장점
기억 공간의 낭비 줄임 (앞에있는 빈공간)
단점
노드가 많을 경우 옮기는데 많은 시간이 소요됨 ( 99999개라면 그만큼 한개씩 앞으로 이동해야되니까)
향후전망
노드가 많을 경우에도 적은 시간이 소요될 수 있는 자료구조
- 원형 큐
정의
원형 형태를 가진 큐
등장배경
이동 큐 단점 보완 위해 등장( 노드가 많을 경우 옮기는데 많은 시간이 소요)
장점
이동 큐처럼 노드를 이동하지 않아도 됨
-> Rear 값만 변화시켜 유용 공간에 직접 삽입
- 데크
정의
큐에서 양쪽에서 입/출력이 가능한 자료구조
장점
큐에서 양쪽에서 입/출력이 가능
- 그래프
정의
그래프는 여러 개의 노드(node)와 이들을 연결하는 간선(Edge)으로 이루어진 자료구조
용어
인접(Adjacent)
정점 0과 1은 간선으로 연결 → 이 때 두 노드는 인접(Adjacent)하다.
차수(Degree)
→ 무방향 그래프에서 하나의 정점에 인접한 정점의 수
무방향 그래프의 차수의 합 : 그래프 간선 수 x 2 (양쪽 통행 가능하니까)
진입 차수(in-degree)
→ 방향 그래프에서 외부에서 오는 간선의 수
진출 차수(out-degree)
→ 방향 그래프에서 외부로 향하는 간선의 수
특징
무방향성(Unidirectionality)
그래프의 간선은 방향성이 없을 수 있으며, 양쪽 방향으로 모두 이동할 수 있습니다.
이러한 그래프를 무방향 그래프(undirected graph)라고 부른다.
양쪽의 방향으로 이동할 수 있지만, 무방향 그래프라고 부른다. 무방향의 의미가 방향의 강제하는 일방통행이 없다는 의미라고 생각할 수 있다.
방향성(Directionality)
그래프의 간선은 방향성이 있을 수 있으며, 한쪽 방향으로만 이동할 수 있다.
이러한 그래프를 방향 그래프(directed graph) 또는 유향 그래프(digraph)라고 부른다.
가중치(Weight)
그래프의 간선에는 가중치(weight)를 부여할 수 있다.
가중치를 부여한 그래프를 가중치 그래프(weighted graph)라고 부르며, 보통은 거리, 비용, 우선순위 등을 나타내는 데 사용된다.
연결성(Connectivity)
그래프에서 노드와 노드 사이에 경로가 존재하면, 두 노드는 연결되었다고 말한다. 그래프가 연결되어 있는 경우 연결 그래프(connected graph)라고 부르며, 그렇지 않은 경우 비연결 그래프(disconnected graph)이다.
사이클(Cycle)
그래프에서 한 노드에서 시작하여 경로를 따라가면서 마침내 자기 자신으로 돌아오는 경로를 사이클(cycle)이라고 부른다. 사이클이 없는 그래프를 비순환 그래프(acyclic graph)라고 부르며, 사이클이 있는 그래프를 순환 그래프(cyclic graph)라고 부른다.
차수(Degree)
그래프에서 한 노드에 인접한 간선의 수를 차수(degree)라고 부른다. 무방향 그래프에서는 노드의 차수가 연결된 노드의 수와 같으며, 방향 그래프에서는 인접한 노드의 수와 나가는 노드의 수로 구분된다.
종류
무방향 그래프(Undirected Graph)
간선에 방향이 없는 그래프이다
노드와 간선으로 이루어져 있으며, 노드 사이의 관계는 양방향이다.
방향 그래프(Directed Graph)
간선에 방향이 있는 그래프이다.
노드와 간선으로 이루어져 있으며, 노드 사이의 관계는 일방향이다.
완전 그래프(Complete Graph)
모든 노드가 서로 연결된 그래프이다.
노드 수가 n일 때, 간선 수는 n(n-1)/2 입니다.
완전 그래프는 항상 연결그래프를 포함한다.
연결 그래프(Connected Graph)
무방향 그래프에서, 모든 노드 사이에 경로가 존재하는 그래프이다.
다중 그래프(Multi Graph)
두 정점 사이에 두 개 이상의 간선이 존재하는 그래프
DFS vs BFS 간단비교
깊이우선탐색 (Depth First Search)
- 한 노드의 자식을 끝까지 순회한 후 다른 노드 순회
- 자식 우선
- 스택(LIFO) 사용
너비우선탐색 (Breadth First Search)
- 한 단계씩 내려가면서 같은 레벨에 있는 노드들을 먼저 순회
- 형제 우선
- 큐(FIFO) 사용
신장트리
깊이 우선 탐색이나 너비 우선 탐색을 하게 되면
사이클을 갖지 않는 최소 부분 그래프가 생기는데
이 부분 그래프를 그래프 G에 대한 신장 트리라고 한다.
1)이동큐 등장배경
2)완전그래프
3)복귀주소 예를 들어 설명하시오
