탐색 트리란? 탐색트리는 탐색을 위한 트리 기반의 자료구조이다. 이진 탐색은 데이터를 항상 정렬된 상태로 유지해야 되므로, 삽입과 삭제가 빈번한 응용에서는 효율적이지 않다. 해싱은 빠르기는 하나 메모리를 많이 차지하고 오버플로 처리도 해야된다. 그래서 이진탐색트리 (Bst, Binary Search Tree)를 사용할 것이다. - 모든 노드는 유일한 키를 가진다 - 왼쪽 서브트리의 키들은 루트의 키보다 작다. - 오른쪽 서브트리의 키들은 루트의 키보다 크다. - 왼쪽과 오른쪽 서브트리도 이진탐색트리이다. 이진탐색트리의 연산 이진탐색트리를 구현하기 전에 노드 클래스를 구현해보자. // 이진탐색을 위한 노드 클래스 class BSTNode: def __init__ (self, key, value) : sel..

트리란? 계층적인 관계를 가진 자료의 표현에 유요한 자료구조 트리의 용어 - 루트 노드 : 계층적인 구조에서 가장 높은 곳에 있는 노드, 트리에서 모든 노드는 자신의 서브트리의 루트 노드이다. - 간선 : 노드와 노드를 연결하는 선 - 부모 노드와 자식 노드 : 간선으로 직접 연결된 노드 중에 상위 노드와 하위 노드 - 형제 노드 : 동일한 부모 노드를 가진 노드 - 조상 노드와 자손 노드 : 어떤 노드에서 루트 노드까지의 경로상에 있는 모든 노드들과 어떤 노드 하위에 연결된 모드 노드 - 단말 노드 : 자식 노드가 없는 노드, 가장 아래에 있는 노드 - 노드의 차수 : 어떤 노드가 가지고 있는 자식의 수 - 트리의 차수 : 트리가 가지고 있는 노드의 차수 중에서 가장 큰 차수 - 레벨 : 트리의 각층에..

정렬이란? 데이터를 순서대로 재배열하는 작업이다. 데이터들이 서로 비교할 수 있어야 되고, 비교할 수 있는 모든 속성들은 정렬의 기준이 된다. 오름차순과 내림차순이 있다. 정렬해야 하는 대상을 레코드라고 부른다. 그리고 대상에는 여러 속성들이 있을 텐데 이를 필드라고 한다. (ex. 번호,이름, 나이 등등) 이 필드 중에서 정렬의 기준이 되는 것을 키 혹은 정렬 키라고 한다. 비교 기반 정렬 대부분의 정렬 방법들로 레코드의 킷값을 비교하여 정리한다. (기수와 카운팅 정렬은 분배에 의한 정렬이다) 내부 정렬과 외부 정렬 모든 데이터가 메모리에 올라와 정렬이 수행되는 것을 내부 정렬이라고 한다. 일부만을 올려 놓는다면 외부 정렬이라고 한다. 안정성에 따른 분류 안정성이란 동일한 킷값을 갖는 레코드가 여러 개..

연결된 구조란? 배열 구조 vs 연결된 구조 배열 구조 - 모든 데이터를 연속된 메모리 공간에 저장 - n번째 자료의 위치를 금방 찾을 수 있다. O(1) 연결된 구조 - 흩어진 데이터를 링크(포인터)로 연결해서 관리 - n번째 자료의 위치를 찾으려면? O(n) 연결된 구조의 특징 장점 : 메모리 낭비가 없고 용량이 고정되지 않는다. 중간에 자료를 삽입하거나 삭제하는 것이 용이하다. 단점 : n번째 항목 접근에 O(n)의 시간이 걸린다. 노드란? 노드(Node)는 데이터와 링크 필드로 나뉘어져 있다. 맨 앞에 있는 노드를 시작 노드(머리 노드)라고 한다. 맨 뒤에 있는 노드를 마지막 노드(꼬리 노드)라고 한다. 연결 리스트의 종류 - 단순 연결 리스트 : 일자로 연결되어 있음 - 원형 연결 리스트 : 마..

큐란? 선입선출의 자료구조 - 먼저 들어온 데이터가 먼저 처리된다. 전단과 후단이 있다. 전단 : 삭제 통로 후단 : 삽입 통로 큐의 추상 자료형 데이터 : 선입선출의 접근 방법을 유지하는 요소들의 모음 연산 - enqueue(e) : 요소 e를 큐의 맨 뒤에 추가한다. - dequeue() : 큐의 맨 앞에 잇는 요소를 꺼내 반환한다. - isEmpty() : 큐가 비어있으면 True를 아니면 False를 반환한다. - isFull() : 큐 가득 차 있으면 True를 아니면 False를 반환한다. - peek() : 큐의 맨 앞에 있는 항목을 삭제하지 않고 반환한다. 큐의 오류 상황 오버플로우 (OverFlow) : 큐가 꽉 차있는 경우, enqueue()가 수행되면 더 이상 들어갈 수 없게 되는 상..

스택이란? 후입선출 (Last-In First Out)의 자료구조이다. 열린 곳을 스택 상단(Top)이라고 부른다. 삽입과 삭제는 상단으로만 할 수 있고, 중간에는 항목을 삽입하거나 삭제할 수 없다. 스택의 추상 자료형 데이터 : 후입선출의 접근 방법을 유지하는 항목들의 모음 연산 (리스트와 다르게 위치에 대한 정보를 매개변수로 받지 않음) - push(e) : 요소 e를 스택의 맨 위에 추가한다. - pop() : 스택의 맨 우에 있는 요소를 꺼내 반환한다. - isEmpty() : 스택이 비어있으면 True를 아니면 False를 반환한다. - isFull() : 스택이 가득 차 있으면 True를 아니면 False를 반환한다. - peek() : 스택의 맨 위에 있는 항목을 삭제하지 않고 반환한다. 스..