한반가

2021.06.14 - [이론공부/자료구조] - 자료구조 공부 #21 (그래프2) 정렬 정렬은 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는것 컴퓨터 공학을 포함한 모든 과학기술 분야에서 가장 기본적이고 중요한 알고리즘 중 하나 정렬은 자료 탐색에 있어서 필수적 ex) 영어사전에서 단어들이 알파벳 순으로 정렬되있지 않다면 복잡할 것이다. 정렬의 대상 일반적으로 정렬시켜야하는 대상은 레코드(record) 레코드는 필드라는 작은 단위로 구성 키 필드로 레코드와 레코드를 구별함 정렬 알고리즘 개요 모든 경우의 최적인 정렬 알고리즘은 존재하지 않는다. 각 응용 분야에 적합한 정렬 방법을 사용해야 함 레코드 수의 많고 적음 레코드 크기의 크고 작음 key의 특성 (문자, 정수, 실수) 메모리 내부/외부 정..

2021.06.08 - [이론공부/자료구조] - 자료구조 공부 #20 (그래프) 신장 트리 그래프 내의 모든 정점을 포함하는 트리 n개의 정점을 가지는 그래프의 신장트리는 n-1개의 간선을 가진다 신장 트리는 그래프의 최소 연결 부분 그래프 이다. 신장트리는 깊이 너비 우선 탐색 도중에 사용된 간선만 모으면 만들 수 있다. depth_first_search(v): v 를 방문되었다표시; for all u ∈ (v에 인접한 정점) do if (u가 아직 방문되지 않았으면) then (v,u)를 신장 트리 간선이라고 표시; depth_first_search(u) 최소비용 신장트리 네트워크(그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결 MST의 응용 (Minimun Spanning Tre..

2021.05.25 - [전체글] - 자료구조 공부#19 (우선순위 큐, 힙) 그래프 연결되어 있는 객체 간의 관계를 표현하는 자료구조 ex) 앞서 배운 트리도 이와 비슷함, 전기회로 소자간 연결, 지도에서 도시들의 연결 깊게 말하면 그래프는 트리보다 좀더 넓은 의미를 포함하고 있다. 그래프 G는 (V,E)로 표시 정점(vertices) 여러가지 특성을 가질 수 있는 객체 V(G) : 그래프 G의 장점들의 집합 노드 라고도 불림 간선(edge) 정점들 간의 관계 의미 E(G): 그래프 G의 간선들의 집합 링크 라고도 불림 그래프 표현 방법 그래프 종류 네트워크(network) 가중치 그래프는 네트워크 라고도 함 간선에 비용, 혹은 가중치가 할당된 그래프 예시 정점 : 각 도시 간선 : 도시 연결 도로 가..

2021.05.19 - [전체글] - 자료구조 공부 #18 (트리연산) 우선순위 큐 우선순위를 가진 항목들을 저장하는 큐 선입선출 순서가 아니라 우선순위가 높은 데이터가 먼저 나가게 설계됨 스택이나 선입선출 큐를 우선순위 큐로 구현 할수 있음 자료구조 삭제되는요소 스택 가장 최근에 들어온 요소 큐 가장 먼저 들어온 요소 우선순위 큐 가장 우선순위가 높은 데이터 응용분야 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서 작업 스케줄링 우선순위 큐 구조(ADT) 가장 중요한 연산은 insert 연산, delete연산이다 우선순위 큐는 2가지로 구분 최소 우선순위 큐 최대 우선순위 큐 우선순위 큐 구현 방법 배열을 이용한 우선순위 큐 연결 리스트를 이용한 우선순위 큐 힙(heap)을 이용한 우선순위 큐 완..

2021.05.16 - [이론공부/자료구조] - 자료구조 공부 #13 (트리순회) 이진트리 노드 갯수 연산 탐색 트리안의 노드의 개수를 계산 각각의 서브트리에 대하여 순환 호출만 한다음, 반환되는 값에 1을 더하여 반환 int get_node_count(TreeNode* node){ int cout = 0; if (node != NULL) count = 1 + get_node_count(node->left) + get_node_count(node->right); return count; } 이진 트리 높이 연산 서브 트리에 대하여 순환 호출하고 서브트리들의 반환값 중에서 최대값을 구하여 반환 int get_height(TreeNode* node){ int height = 0; if (node != NUL..

2021.05.04 - [이론공부/자료구조] - 자료구조 공부 #16 (트리) 이진 트리 순회 트리의 노드들을 체계적으로 방문 하는것 3 가지의 기본적인 순회 방법 전위순회 : VLR 자손 노드보다 루트 노드를 먼저 방문함 중위순회 : LVR 왼쪽 자손노드, 루트, 오른쪽 노드순으로 방문함 후위순회 : LRV 루트 노드보다 자손을 먼저 방문함 전위 순회 루트 노드를 방문 왼쪽 서브트리 방문 오른쪽 서브트리 방문 응용 용도 알고리즘 preorder(x) if x != null thenprint data(x); preorder(LEFT(x)); preorder(RIGHT(x)); 순환 호출(재귀 호출)을 이용함 2021.03.12 - [전체글] - 자료구조 공부#4 (순환, 반복) 자료구조 공부#4 (순환,..