데이터 분석 기술 블로그

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. ..

1. 큐(Queue)의 특성스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조입니다.선입선출구조(FIFO : First In First Out)큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입(First In)된 원소는 가장 먼저 삭제(First Out)된다. 2. 큐의 기본 연산삽입 : enQueue삭제 : deQueue3. 큐의 구현

1. 분할 정복 알고리즘설계 전분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눕니다.정복(Conquer) : 나눈 작은 문제를 각각 해결합니다.통합(Combine) : (필요하다면) 해결된 해답을 모읍니다.2. 퀵 정렬주어진 배열을 두 개로 분할하고, 각각을 정렬합니다.합병정렬과 비슷다른 점 1 : 합병정렬은 그냥 두 부분으로 나누는 반면에, 퀵정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것 오른편에 위치시킵니다.다른 점 2 : 각 부분 정렬이 끝난 후, 합병정렬은 "합병"이란 후처리 작업이 필요하나, 퀵정렬은 필요로 하지 않습니다. 퀵정렬의 최악의 시간 복잡도는 O(n2)로, 합병정렬에 비해 좋지 못합니다.그런데, 왜 "빠른" 정렬이라고..