[자료구조]기말고사 시험 정리

7장 스택(후입선출:LIFO)

순차 자료구조 방식은 배열을 사용하여 구현하기는 쉽지만, 물리적으로 크기가 고정된 배열을 사용하기 때문에 스택의 크기를 변경하기가 어렵고, 메모리의 낭비가 생길 수 있다.

 

연결 자료구조 방식은 스택에 원소를 삽입할 때마다 연결 리스트에 노드를 하나씩 연결한다.

 

시스템 스택->자바 함수 호출 개념.

 

수식의 괄호 검사->왼쪽 괄호를 만나면 스택에 push하고, 오른쪽 괄호를 만나면 스택을 pop한다.

 

수식의 후위 표기법 반환

전위 표기법	연산자를 앞에 표기하고 그다음에 피연산자를 표기하는 방법 (+AB)
중위 표기법	연산자를 피연산자의 가운데에 표기하는 방법 (A+B)
후위 표기법	연산자를 피연산자 뒤에 표기하는 방법 (AB+)

((A*B)-(C/D))	전위 표기법	-*AB/CD
	후위 표기법	AB*CD/-

8장 큐(선입선출:FIFO)

순차 자료구조 방식을 이용한 큐의 구현

 

선형 큐

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

rear=n-1(배열의 마지막인덱스)이면 포화상태

->배열이 비어 있어도 rear가 마지막인덱스를 가리키면 포화상태로 나타남 메모리 낭비

->해결법1. 원소를 배열의 앞부분으로 이동시켜서 위치를 조정해줘야 한다.

2. 원형 큐를 사용한다.

 

원형 큐

배열의 처음과 끝이 연결되어 있다고 생각하는 것이다.

초기 공백 상태일 때 front와 rear의 값이 0이다.

공백 상태 조건은 front = rear 이다.

포화 상태 조건은 (rear+1) mod n = front 이다.

삽입 rear = (rear+1) mod n

삭제 front = (front+1) mod n

 

연결 큐

순차 자료구조 방식을 이용하여 구현한 큐에는 큐의 길이를 마음대로 변경할 수 없고, 원소가 없을 때에도 항상 처음 크기를 유지하고 있어야 하므로 메모리도 낭비된다. 이와 같은 문제를 극복하기 위해 연결 자료구조 방식을 이용하여 크기에 제한 없는 연결 큐를 사용한다.

초기 공백 연결 큐 생성 -> front = null / rear = null

공백 연결 큐 검사 -> front=null

 

덱-> 큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로서, 스택의 성질과 큐의 성질을 모두 가지고 있당

 

큐의 응용

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

9장 트리

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

 

이진 트리(binary tree)

-> 모든 노드가 2개의 서브 트리를 가지고 있는 트리(최대 2개까지의 자식 노드가 존재)

-> 서브 트리간의 순서가 존재

-> 노드의 개수가 n개이면 간선의 개수는 n-1개

-> 높이가 h이면 최소 h+1개의 노드를 가지며 최대 2^(h+1)-1개의 노드를 가짐

 

포화 이진트리(full binary tree)

->모든 서브트리가 공집합이 아님

->높이가 5인 포화 이진트리의 노드의 수는? 31개

 

완전 이진트리(complete binary tree)

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

 

편향 이진트리(Skewed binary tree)

->최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리

순차자료구조방식을 이용하여 표현->1차원배열

->인덱스0은 사용하지 않음

->노드i의 부모노드의 인덱스는[i/2], 왼쪽 자식노드[i*2], 오른쪽 자식노드[i*2+1]

연결잘구조방식을 이용하여 표현->데이터필드, 왼쪽링크필드, 오른쪽링크필드

 

 

이진 탐색 트리

(1)모든 원소는 서로 다른 유일한 키를 갖는다. (2)왼쪽서브트리에 있는 원소의 키는 그 루트의 키보다 작다. (3)오른쪽서브트리에 있는 원소의 키는 그 루트의 키보다 크다. (4)왼/오른쪽 서브트리들은 모두 이진탐색트리다.

탐색연산

삽입연산

삭제연산

힙이란? -> 완전 이진 트리에 있는 노드 중에서 key값이 가장 큰 노드(최대 힙)나 key값이 가장 작은 노드(최소 힙)를 빠른시간 내에 찾기 위해서 만든 자료구조다.

최대 힙 -> 부모노드의 키값이 자식노드의 key값보다 항상 크거나 같은 크기의 관계(루트가 키값이 가장 큰 노드)

최소 힙 -> 최대 힙의 반대(루트가 key값이 가장 작은 노드)

힙에서의 삽입 연산

1 현재 힙의 크기를 하나 증가시켜서 노드를 확장->임시로 그노드에 삽입 2 부모노드와 비교 ->필요하면 바꾸기 ->부모노드와 비교. 3 더 이상 비교할 필요가 없으면 삽입 연산 종료

힙에서의 삭제 연산

최대힙->가장 큰 원소(루트)를 삭제하여 반환 마지막 노드를 루트 노드에 임시 저장 자식노드와 key값 비교 후 재정렬 최소힙->가장 작은 원소(루트)를 삭제하여 반환 재정렬 마지막 노드를 루트 노드에 임시 저장 자식노드와 key값 비교 후 재정렬

 

10장 그래프

->연결되어있는 원소간의 관계를 표현하는 자료구조(버스노선도나 전철노선도)

연결할 객체를 나타내는 정점과 객체를 연결하는 간선의 집합으로 구성된다.

그래프 G를 [G=(V, E)]로 정의하는데 V는 정점들의 집합 E는 간선들의 집합이다.

그래프는 간선의 방향성 유무에 따라서 [방향 그래프]와 [무방향 그래프]가 있고, 연결 정도에 따라서 [연결 그래프]와 [단절 그래프],[완전 그래프]가 있다. 그리고 가중치를 가진 간선으로 이루어진 [가중치 그래프]가 있다.

 

그래프 관련 용어

->두 정점 a와 b가 연결되어 간선(a, b)가 있을 때, 두 정점 a와 b를 [인접]되어 있다고 하고, 간선 (a, b)는 정점 a와 b에 [부속]되어 있다고 한다. ->정점에 부속되어 있는 간선의 수를 [차수]라고 한다. ->방향 그래프에서는 정점에 부속된 간선의 방향에 따라서 [진입차수]와 [진출차수]가 생기는데, 정점을 머리로 하는 간선의 수는 진입차수가 되고, 정점을 꼬리로 하면 진출차수 그래프에서 간선을 따라갈 수 있는 길을 순서대로 나열한 것을 [경로]라고 한다. 경로를 구성하는 간선의 수는 [경로 길이]가 된다. 모두 다른 정점으로 구성된 경로를 [단순 경로]라고 한다.(a-b-c[O] a-b-a-b-c[X]) 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로를 [사이클]이라 한다.

 

그래프의 구현

그래프를 표현하는 방법은 [순차 자료구조 방식]을 이용하는 2차원 배열의 [인접 행렬 방법]과 [연결 자료구조 방식]인 연결 리스트를 사용하는 [인접 리스트 방법]이 있다.

인접 행렬

->정점에 대해서 두 정점을 연결한 간선의 유무를 저장하는 방법으로 정점의 수에 대한 정방 행렬을 사용한다. ->n개의 정점을 가진 그래프는 n x n 정방 행렬을 사용하고, 두 정점이 인접하면 1, 아니면 0으로 표현한다.

(가로->:진출차수 세로↑:진입차수)

 

 

 

인접 리스트

->각 정점에 대한 인접 정점들을 연결 리스트로 만듬

 

그래프 순회(그래프 탐색)

->하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하는 것

 

깊이 우선 탐색(DFS, Depth First Search) (연습해야됨)

->시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 재탐색(후입선출 구조의 [스택]을 사용)

 

너비 우선 탐색(BFS, Breadth First Search) (연습해야됨)

->시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법으로, 가까운 정점을 먼저 방문하고 멀리있는 정점들은 나중에 방문하는 순회 방법이다(선입선출 구조의 [큐]를 사용)

 

신장 트리와 최소 비용 신장 트리

신장트리

최소의 간선을 이용하여 모든 정점을 연결한 그래프 / 사이클이 없는 단순 연결 그래프 / n개의 정점으로 이루어진 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리

최소 비용 신장 트리

신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장트리

Kruskal 알고리즘Ⅰ 1. 그래프 G의 모든 간선을 가중치에 따라 내림차순으로 정리한다. 2. 그래프 G에서 가중치가 가장 높은 간선을 제거한다. 이때 정점을 그래프에서 분리시키는 간선을 제거할 수 없다. 다음으로 가중치가 높은 간선을 제거한다. 3. 그래프 G에 n-1개의 간선만 남을 때까지 2를 반복한다.   Krushkal 알고리즘Ⅱ 1. 그래프 G의 모든 간선을 가중치에 따라 오름차순으로 정리한다. 2. 그래프 G에 가중치가 가장 작은 간선을 삽입한다. 이때 사이클을 형성하는 간선은 삽입할 수 없다. 다음으로 가중치가 작은 간선을 삽입한다. 3. 그래프 G에 n-1개의 간선을 삽입할 때까지 2를 반복한다.   Prime 알고리즘 ->간선을 정렬하지 않고 하나의 정점에서 시작하여 트리를 확장해 나가는 방법 1. 그래프 G에서 시작 정점을 선택한다. 2. 선택한 정점에 부속된 모든 간선 중에서 가중치가 가장 작은 간선을 연결하여 트리를 확장한다. 3. 이전에 선택한 정점과 새로 확장한 정점에 부속된 모든 간선 중에서 가중치가 가장 작은 간선을 삽입한다. 이때 사이클을 형성하는 간섭은 삽입할 수 없다. 다음으로 가중치가 작은 간선을 삽입한다. 4. 그래프 G에 n-1개의 간선만 남을 때까지 3을 반복한다.