[자료구조] 정리

Postfix

Prefix

순회

• 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문
• 중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문
• 후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문
• 층별 순회(level order traverse) : 위 쪽 node들 부터 아래방향으로 차례로 방문

큐

우선순위 큐

큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오지만 우선순위 큐는 다르다.
들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다.

우선순위 큐를 구현하는 방법

• 배열을 기반으로 구현하는 방법
• 연결리스트를 기반으로 구현하는 방법
• 힙을 이용하는 방법 -> 주로 사용됨

선형 큐

초기 상태의 공백 큐는 저장된 원소가 없으므로 front와 rear를 -1로 설정한다.
rear = n-1이면 포화상태

원형 큐

배열의 처음과 끝이 연결되어 있다고 생각하는 것
초기 공백 상태일 때 front와 rear값이 0
공백 상태 조건 front = rear
포화 상태 조건 (rear+1) % n = front
삽입 rear = (rear+1) % n
삭제 front = (front+1) % n

Dequeue

큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐.
스택과 큐의 성질을 모두 가지고 있다.

큐의 사용

작업 버퍼 큐, 프로세스 스케줄링, 대기 행렬을 모델링하는 시뮬레이션(큐잉이론)에서 사용한다.

트리

비선형 자료구조 중에서 계층관계를 가진 계층형 자료구조

이진트리

모든 노드가 2개의 서브 트리를 가지고 있는 트리

포화 이진트리(Full binary tree)

높이가 5인 포화 이진트리의 노드 수 = 31개

완전 이진트리(Complete binary tree)

레벨 1부터 k-1까지 노드가 채워져 있고 마지막 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리

Minimum spanning tree

spanning tree : 그래프의 모든 정점을 포함하는 트리 형태의 서브 그래프
Minimum spanning tree : 스패닝 트리 중에서 간선의 가중치 합이 가장 작은 스패닝 트리

크루스칼 알고리즘

무방향 연결 그래프가 주어질 때, 최소 스패닝 트리라고 부르는 서브 그래프를 찾는 알고리즘.
유니온 파인드 자료구조를 사용한다.

1. 모든 간선을 끊어 놓는다.
   

2. 가중치 순으로 간선을 정렬한다.
   

3. 정렬된 간선을 순서대로 선택한다.

4. 선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 간선을 최소 스패닝 트리에 포함 시키고 두 정점을 연결한다.

5. 3, 4 반복

결과

시간복잡도

간선 E개 정렬 = O(elog₂e)
union-find를 통한 vertex 비교 O(V)
따라서 O(elog₂e)
Edge 정렬이 적을수록 빠르다.

프림 알고리즘

예시 그래프

1. 임의의 정점을 선택하여 비어있는 T에 포함시킨다. T is tree
   

2. T에 있는 노드와 T에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

3. 찾은 간선이 연결하는 두 노드 중, T에 없는 노드를 T에 포함시킨다.
   

4. 모든 노드가 T에 포함될 때 까지 2,3을 반복한다.
   

시간복잡도

주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하므로 O(n^2)
그래프에 간선이 많이 존재하는 ‘밀집 그래프(Dense Graph)’ 의 경우는 Prim 알고리즘이 적합하다.

힙

최대힙, 최소힙
힙소트

그래프

연결되어있는 원소간의 관계를 표현하는 자료구조
연결할 객체를 나타내는 정점과 객체를 연결하는 간선의 집합으로 구성된다.
그래프 G를 G=(V,E)로 정의하는데 V는 정점들의 집합, E는 간선들의 집합이다.

그래프 구현 방법

• 순차 자료구조 방식 (인접 행렬)
• 연결 자료구조 방식 (인접 리스트)

DFS

시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색하다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간전이 있는 정점으로 되돌아와서 다른 방향의 간선으로 재탐색

• 스택사용

BFS

시작 정점에서 인접한 정점들을 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법.
가까운 정점을 먼저 방문하고 멀리있는 정점들은 나중에 방문하는 순회방법

• 큐 사용

그래프 종류

방향 그래프

무방향 그래프

연결 그래프

단절 그래프

완전 그래프

가중치 그래프

참고 사이트

수기 표기법
순회
프림 알고리즘
크루스칼 알고리즘
자료구조 정리