데이터 분석 기술 블로그

1. 이진 탐색 트리2. 이진 탐색 트리 - 연산3. 이진 탐색 트리 - 성능4. 이진 탐색 트리 - 연산 연습

1. 이진트리의 저장2. 이진 트리의 표현 - 배열배열을 이용한 이진 트리의 표현의 단점편향 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비가 발생합니다.트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우 배열의 크기 변경이 어려워 비효율적입니다.배열을 이용한 이진 트리의 표현의 단점을 보완하기 위해 연결리스트를 이요하여 트리를 표현할 수 있습니다.3. 연습문제4. 수식 트리

1. 이진트리모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리각 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리왼쪽 자식 노드(left child node)오른쪽 자식 노드(right child node)2. 이진트리의 특성레벨 i에서의 노드의 최대 개수는 2i개3. 포화 이진 트리4. 이진트리의 순회(traversal)순회(traversal)란 트리의 각 노드를 중복되지 않게 전부 방문(visit)하는 것을 ㅁ라하는데 트리는 비 선형 구조이기 때문에 선형구조에서와 같이 선후 연결 관계를 알 수 없습니다.따라서 특별한 방법이 필요합니다.순회(traversal) : 트리의 노드들을 체계적으로 방문하는 것입니다.3가지의 기본적인 순회 방법으로는전위 순회(preorder traversal) :..

1. 트리의 정의트리의 개념비선형 구조원소들 간에 1:n 관계를 가지는 자료구조원소들 간에 계층관계를 가지는 계층형 자료구조상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족합니다.노드 중 최상위 노드를 루트(root)라고 합니다.나머지 노드들을 n(>=0)개의 분리 집합 T1,..., TN으로 분리될 수 있습니다.이들 T1, ..., TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라고 합니다.2. 트리의 용어정리

1. BFS (Breadth Frist Search)그래프를 탐색하는 방법에는 크게 두 가지가 있습니다.깊이 우선 탐색(Depth First Search, DFS)너비 우선 탐색(Breadth First Search, BFS)너비 우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식입니다.인접한 정점들에대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용합니다.

1. 버퍼 (Buffer)버퍼데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역입니다.버퍼링 : 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 의미합니다.버퍼의 자료 구조버퍼는 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용됩니다.순서대로 입력 / 출력 / 전달되어야 하므로 FIFO 방식의 자료구조인 큐가 활용됩니다.

우선순위 큐 (Priority Queue)우선순위 큐의 특성우선순위를 가진 항목들을 저장하는 큐FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 됩니다.우선순위 큐의 적용 분야시뮬레이션 시스템네트워크 트랙픽 제어운영체제의 테스크 스케줄링우선순위 큐의 구현배열을 이용한 우선순위 큐리스트를 이용한 우선순위 큐배열을 이용하여 우선순위 큐 구현배열을 이용하여 자료 저장원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조가장 앞에 최고 우선순위의 원소가 위치하게 됩니다.문제점배열을 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생합니다.이에 소요되는 시간이나 메모리 낭비가 큽니다.

1. 선형 큐 이용시의 문제점앞서서 큐(Queue) 즉, 선형 큐에 대해서 배웠습니다.(2024.06.02 - [알고리즘] - 큐(Queue))1-1. 잘못된 포화상태 인식선형 큐를 이용하여 원소의 삽입과 삭제를 계속할 경우, 배열의 앞부분에 활용할 수 있는 공간이 있음에도 불고하고, rear = n - 1인 상태 즉, 포화상태로 인식하여 더 이상의 삽입을 수행하지 않게 됩니다.1-2. 해결방법 1매 연산이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 모두 이동시킵니다.원소 이동에 많은 시간이 소요되어 큐의 효율성이 급격히 떨어집니다.1-3. 해결방법 21차원 배열을 사용하되, 논리적으로는 배열의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용합니다.원형 큐의 논리적 구조입니다.2. ..