자료구조와 알고리즘 ft. 수업

자료구조 기말정리

우선순위 큐 정의 : 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 구현 방법 : 배열, 연결 리스트, 히프를 사용해서 구현 가능 히프 정의 : 무엇인가를 차곡차곡 쌓아올린 더미라는 뜻을 의미하는 자료구조 1. 항상 부모 노드 > 자식 노드 2. 히프는 완전 이진 트리, 완전 이진트리는 높이가 h 일 때 레벨 h-1까지는 Full BT이고, 레벨 h에서는 왼쪽부터 노드가 순서대로 채워진 이진트리이다. 3. 2종류 : 최대 히프(부모 노드 > 자식 노드), 최소 히프(부모 노드 AVL 트리가 개발됨 A..

자료구조 대학 강의 정리

https://blogshine.tistory.com/category/2023%201%ED%95%99%EA%B8%B0/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0 '2023 1학기/자료구조' 카테고리의 글 목록 blogshine.tistory.com

그래프 II

10.5 연결 성분 연결 성분(connected component): 최대로 연결된 부분 그래프 1. 그래프 상의 임의의 정점을 선택해 깊이 우선 탐색이나 너비 우선 탐색을 시작하면 시작 정점으로부터 도달 가능한 모든 정점들이 하나의 연결 성분이 됨 2. 다음에 방문 안된 정점을 선택해서 다시 탐색을 실행하면 그 정점을 포함하는 연결 성분이 구해짐 3. 그래프 상의 모든 정점이 방문될 때가지 이 과정을 되풀이하면 그래프에 존재하는 모든 연결 성분들을 찾을 수 있음 연결 성분 프로그램 void find_connected_component(GraphType *g){ count = 0; for(int i=0; in;i++){ if(!visited[i]){ // 방문되지 않았으면 count++; dfs_mat(..

그래프 I

10.1 그래프란? 그래프 소개 그래프(graph): 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 그래프의 역사 수학자 오일러(Euler)는 "모든 다리를 한 번만 건너서 출발했던 장소로 돌아올 수 있는가?" 라는 문제에 대한 답을 그래프 이론을 이용해서 증명했음 -> 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 경로만 존재함 정점(vertex): 위치 간선(edge): 위치 간의 관계 오일러 경로(Eulerian tour): 그래프에 존재하는 모든 간선을 한 번만 통과하면서 처음 정점으로 되돌아오는 경로 그래프로 표현할 수 있는 것들 도로 영역 간 인접 관계 선수 과목 그래프의 용어 그래프: 정점(vertex)와 간선(edge)들의 집합, G=(V, E) V(G): 그래프 G의 ..

힙

8.3 힙 8.3.1 힙의 개념 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말함 힙 트리는 중복된 값을 허용함에 유리(이진 탐색 트리는 중복된 값을 허용하지 않음) 힙 안의 데이터들은 느슨한 정렬 상태를 유지 -> 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 힙의 목적: 삭제 연산이 수행될 때마다 가장 큰 값을 찾아 내기만 하면 되는 것이므로(가장 큰 값은 루트노드에 있음) 전체를 정렬할 필요는 없음 힙의 종료: 최대 힙(max heap), 최소 힙(min heap) 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리:..

우선순위 큐

8.1 우선순위 큐 추상 자료형 우선순위 큐의 소개 우선순위 큐(priority queue): 데이터들이 우선순뤼를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 됨 자료구조삭제되는 요소 스택 가장 최근에 들어온 데이터 큐 가장 먼저 들어온 데이터 우선순위 큐 가장 우선순위가 높은 데이터 우선순위 큐의 추상 자료형 우선순위 큐 객체: n개의 element 형의 우선순위를 가진 요소들의 모임 연산: create() ::= 우선순위 큐를 생성 init(q) ::= 우선순위 큐 q를 초기화 is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사 is_full(q) ::= 우선순위 큐 q가 가득찼는지 검사 insert(q,x) ::= 우선순위 큐 q에 요소 x를 추가 delete(q) ::= 우선순..

2. 균형 이진 탐색 트리

균형 이진 탐색 트리 이진 탐색 ve 이진 탐색 트리 이진 탐색 = 자료들이 배열에 저장되어 있으므로 삽입과 삭제가 힘듦.(즉, 자료 삽입, 삭제시 앞 뒤의 원소를 이동시켜야함) 이진 탐색 트리 = 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조 이진 탐색 트리에서는 균형을 유지하는 트리라면 탐색 연산은 O(logn)의 시간복잡도를 가지지만, 균형 트리가 아닐 경우에는 O(n)로 시간복잡도가 높아지게 됨 이진 탐색 트리에서 균형을 유지하는 것이 중요함 -> 스스로 균형 트리를 만드는 AVL 트리가 존재함(상당히 복잡하므로 주제 전체를 다루지 않음) 1) AVL 트리 AVL 트리: Adelson-Velskii와 Landis에 의해 제안된 트리로서 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브..

3. 이진 탐색 트리

이진 탐색 트리 이진 탐색 트리(binary search tree) : 이진 트리 기반의 탐색을 위한 자료 구조 탐색(search) : 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 의미 레코드(record) : 하나 이상의 필드(field)로 구성 테이블(table) : 레코드(record)들의 집합 주요 키(primary key) : 각각의 레코드를 구별할 수 있는 키 탐색 작업을 할 때 주요 키가 입력이 되어 특정한 키를 가진 레코드를 찾게 됨 이진 탐색 트리는 이러한 탐색 작업을 효율적으로 하기 위한 자료구조 - 이진 탐색 트리의 정의 이진 탐색 트리: 이진 탐색 트리의 성질을 만족하는 이진 트리 이진 탐색 트리 - 모든 노드 키는 유일함 - 왼쪽 서브 트리의 키들은 루트의 키보..