카테고리 없음

(자료구조) 복습 #1

시아나 2022. 3. 23. 17:50

트리

트리는 계층적인 자료를 표현하는데 적합한 자료구조
사이클을 가지 않는 연결 그래프

용어들 :

  • 노드 : 트리의 구성요소
  • 루트 : 부모가 없는 노드
  • 서브트리 : 하나의 노드와 그 노드들의 자손들로 이루어진 트리
  • 노드의 차수 : 어떤 노드가 기자고 있는 자식 노드의 개수
  • 레벨 : 트리의 각층에 번호를 매기는 것
  • 높이 : 트리가 가지고 있는 최대 레벨

이진 트리

모든 노드가 2개의 서브 트리를 가지고 있는 트리, 서브 트리 간의 순서가 존재함
n개의 노드를 가진 이진 트리는 정확하게 n-1개의 간선을 가짐.
높이가 h인 이진트리는 최소 h개의 노드를 가지며 최대 2^h - 1의 노드를 가짐

이진트리의 분류 :

  • 포화 이진 트리 : 최대의 노드를 가진 이진트리
  • 완전 이진 트리 : 노드를 왼쪽부터 채운 이진트리
  • 기타 이진 트리

이진트리는 배열 or 포인터로 표현가능

  • 배열 표현법 : 기억공간의 낭비가 심해짐
- 노드 i의 부모 노드의 인덱스 = i/2
- 노드 i의 왼쪽 자식 노드 인덱스 = 2i
- 노드 i의 오른 자식 노드 인덱스 = 2i + 1
  • 링크 표현법 : 2차원적으로 연결된 구조
typedef struct TreeNode{
	int data;
    struct TreeNode *left, *right;
}TreeNode;

 

이진 트리의 순회

V : 방문, L : 왼쪽서브트리, R : 오른쪽 서브트리
  • 레벨 순회 : 낮은 레벨부터 차례대로 방문
  • 전위 순회 : VLR
  • 중위 순회 : LVR
  • 후위 순회 : LRV

 

이진 탐색 트리 (BST)

시간복잡도 O(n)

- 모든 원소의 키는 유일한 키를 가짐
- 왼쪽 서브 트리 키들은 루트 키보다 작다
- 오른쪽 서브 트리의 키들은 루트의 키보다 크다
- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

우선순위 큐

데이터들이 우선 순위를 가지고 있는 큐
배열, 연결 리스트, 히프로 구현가능

히프

데이터가 동적일때, 최대값을 많이 찾을 때 사용
완전이진트리이고 key(부모노드) >= key(자식노드)임
삽입, 삭제 시간 복잡도 O(log n), 정렬 시간 복잡도 O(nlog n)

히프의 종류

  • 최대 히프 : 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진트리
  • 최소 히프 : 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진트리

허프만 코드

글자의 사용빈도에 따라 글자를 압축하는 코드
사용빈도가 높은 글자가 낮은 레벨의 노드에 저장됨

그래프

객체 사이의 연결 관계를 표현할 수 있는 자료구조임
정점과 간선들의 유한 집합

  • 정점(vertex), 노드(node) : 여러 가지 특성을 가질 수 있는 객체
  • 간선(edge), 링크(link) : 정점들 간의 관계

그래프는 무방향 그래프와 방향 그래프로 구분됨

  • 네트워크(가중치 그래프) : 간선에 비용이나 가중치가 할당된 그래프
  • 부분 그래프 : 어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프
  • 연결 그래프 : 모든 정점쌍에 대하여 항상 경로가 존재하는 그래프
  • 완전 그래프 : 모든 정점이 서로 연결되어 있는 그래프
  • 정점의 차수(degree) : 그 정점에 인접한 정점의 수
  • 단순 경로 : 경로 중에서 반복되는 간선이 없는 경우
  • 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경로

 

그래프 표현 방법

  • 인접 행렬(배열)로 표현
  • 인접 리스트(리스트)로 표현

깊이 우선 탐색 (DFS)

시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면
가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색 진행

depth_first_search(v):
	v를 방문되었다고 표시;
    for all u <- (v에 인접한 접점) do
    	if (u가 아직 망문되지 않았으면)
        	then depth_first_search(u)

순환 호출이나 스택을 사용

너비 우선 탐색(BFS)

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문

breath_first_search(v):
	v를 방문했다고 표시;
    큐 Q에 정점 v를 삽입
    while(Q가 공백이 아니면) do
    	Q에서 정점 w를 삭제
        for all u <- (w에 인접한 정점) do
        	if(u가 아직 방문되지 않았으면)
            	then u를 큐에 삽입;
                	u를 방문되었다고 표시;

(원형)큐를 사용

최소비용 신장 트리(MST)

- 신장 트리 : 그래프 내 모든 정점을 포함하는 트리
    n개의 정점을 정확히 (n-1)개의 간선으로 연결함.

- 최소 비용 신장 트리
신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리

  • Kruskal의 MST 알고리즘
        탐욕적인 방법(greedy method) 사용
간선(v)의 가중치(w)를 오름차순으로 정렬함.
for(i = 0..w의 개수)
	if( v(i)를 포함했을 때 사이클이 만들어지지 않으면)
    	결과 E에 v(i)를 포함한다.
  • Prime의 MST 알고리즘
    시작 정점에서 출발하여 연결된 간선 중 가장 비용이 적은 간선을 선택
    우선순위 큐를 사용함

최단 경로

네트워크에서 정점 i와 정점 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제

- Dijkstar의 최단 경로 알고리즘
네트워크에서 하나의 시작정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘
시간 복잡도 : O(n^2)

distance[w] = min(distance[w], distance[u] + weight[u][w])

- Floyd의 최단 경로 알고리즘
그래프에 존재하는 모든 정점 사이의 최단 경로를 한 번에 모두 찾아주는 알고리즘

floyd(G) :
	for k <- 0 to n-1
    	for i<-0 to n-1
        	for j<- 0 to n-1
            	A[i][j] = min(A[i][j], A[i][k] + A[k][j])

 

위상 정렬

방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

topo_sort(G)

for i<- 0 to n-1 do
	if(모든 정점이 선행 정점을 가지면)
    	then 사이클이 존재하고 위상 정렬 불가
    선행 정점을 가지지 않는 정점 v 선택;
    v 출력;
    v와 v에서 나온 모든 간선들을 그래프에서 삭제;

정렬

물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것

선택정렬 O(n^2)

최솟값 or 최댓값을 찾아서 필요한 위치와 교환함

selection_sort(A,n):

for( i <- 0 to n-2)
	least <- 최소값
    A[i] <-> least
    i++

삽입정렬 O(n^2)

정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복

insertion_sort(A,n):

for i<- 1 to n-1 do
	 key <- A[i]
     j <- i-1
     while j>=0 and A[j] > key do
     	A[j+1] <- A[j];
        j<-j-1;
     A[j+1] <- key

버블정렬 O(n^2)

인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환함.

BubbleSort(A, n):

for i <- n-1 to 1 do
	for j <- 0 to i-1 do
    	j와 j+1번째의 요소가 크기순이 아니면 교환
        j++;
    i--;

합병 정렬 O(nlogn)

분할-> 정복 -> 결합의 단계를 거침

  1. 분할 (Divid) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할
  2. 정복(Conquer) : 부분 배열을 정렬, 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용
  3. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 통합함.

퀵 정렬 O(nlogn)

  1. 리스트 안에 있는 한 요소를 피봇(pivot)으로 선택
  2. 피봇보다 작은 요소를 피봇의 왼쪽으로 이동하고 피봇보다 큰 요소를 피봇의 오른쪽으로 이동
  3. 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬

- 그외 정렬 : 히프 정렬 O(nlogn), 기수정렬 O(dn), 쉘 정렬 O(n^1.5)

가장 빠른 정렬은 합병 정렬과 퀵 정렬

탐색

정렬되지 않은 배열에서의 탐색

- 순차 탐색 O(n)
처음부터 끝까지 하나씩 탐색

정렬된 배열에서의 탐색

- 이진 탐색 O(logn)
배열의 중앙값을 조사하고 찾는 값이 중앙값보다 작으면 왼쪽 크면 오른쪽을 탐색한다

- 색인 순차 탐색
index라 불리는 테이블을 사용하여 효율을 높이는 방법

- 보간탐색
탐색키가 존재할 위치를 예츨하여 탐색하는 방법 ex) 전화번호부, 사전

- 이진탐색 트리

- AVL 트리
각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브트리의 높이 차가 1 이하인 이진 탐색 트리

- 2-3 트리
차수가 2 또는 3인 노드를 가지는 트리
이진 탐색 트리의 알고리즘과 비슷함

해싱

키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근하는 것
빠른 검색을 위한 자료구조

추상 자료형 사전

- 사전 : (키, 값) 쌍의 집합, 맵이나 테이블로 불리기도함

  • 키(key) : 사전의 단어처럼 항목과 항목을 구별시켜주는 것
  • 값(value) : 단어의 설명에 해당한다.

 

 

저작자표시 비영리 변경금지 (새창열림)