BURROW

이진탐색트리효율적인 탐색을 위한 이진트리 기반의 자료구조삽입, 삭제, 탐색: O(log n)모든 노드는 유일한 키를 가짐왼쪽 서브트리의 키들은 루트의 키보다 작음오른쪽 서브트리의 키들은 루트의 키보다 큼왼쪽과 오른쪽 서브트리도 이진 탐색트리이진탐색트리의 연산노드의 구조탐색키, 키에 대한 값의 형태class BSTNode: def __init__(self, key, value): self.key = key self.value = value self.left = None self.right = None탐색 연산키를 이용한 탐색루트를 기준으로 작으면 왼쪽 자식부터, 크면 오른쪽 자식부터 다시 탐색과정을 반복하며 탐색키와 동일한 키를 찾을 경우 탐색 성공,..

트리루트라는 특별한 노드를 갖고 그래프를 구성하는 꼭짓점 u, v 간에 u에서 v로 가는 단순경로가 존재하는 비순환의 연결 그래프나무의 가지가 뿌리에서 뻗어나가듯이 트리는 루트를 중심으로 하나 이상의 꼭짓점(노드)들이 비선형이면서 비순환적인 경로로 연결되어 있는 형태노드: 트리인 그래프를 구성하는 꼭짓점루트: 트리인 그래프의 가장 높은 곳에 위치하는 시작 노드서브 트리: 트리인 그래프의 임의의 한 노드를 루트로 하는 트리차수: 트리인 그래프의 임의의 한 노드에 포함된 자식 노드의 개수레벨: 트리인 그래프의 루트 노드를 레벨 0으로 시작하여 자식 노드로 한 단계씩 내려갈 때마다 하나씩 증가하는 단계높이/깊이: 트리인 그래프의 최대 레벨포레스트: 트리인 그래프의 루트 노드와 가지를 제거하여 얻는 서브 트리들..

힙Heap'더미'와 모습이 비슷한 완전 이진트리 기반의 자료 구조가장 큰(또는 작은) 값을 빠르게 찾아내도록 만들어진 자료 구조최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리힙의 연산삽입 연산 - upheap회사에서 신입 사원이 들어오면 일단 말단 위치에 앉히고 능력을 봐서 위로 승진시킴부모 노드와 비교해서 더 클 경우 교환(sift-up)시간 복잡도: O(log n)삭제 연산 - downheap회사에서 사장 자리가 비면 일단 사장 자리에 앉히고 순차적으로 강등시킴자식 노드 중 더 큰 자식 노드와 비교해서 더 작을 경우 교환(sift-down)힙의 구현보통 배열을 이용하여 구현완전 이진트리 ..

트리계층적인 자료의 표현에 적합한 자료 구조트리의 모든 노드는 자신의 서브트리의 루트 노드연결된 위 레벨의 노드는 부모 노드, 아래 레벨의 노드는 자식 노드단말 노드: 자손이 없는 노드, 자손이 있으면 비단말 노드차수: 해당 노드의 자식 노드의 수트리의 차수: 트리를 구성하고 있는 각 노드의 차수 중 가장 높은 차수이진트리모든 노드가 2개의 서브 트리를 갖는 트리공집합이거나 루트와 왼쪽/오른쪽 서브 트리로 구성된 노드들의 집합순환적으로 정의됨서브트리는 공집합일 수 있음이진트리의 서브 트리들은 모두 이진트리이어야 함이진트리의 분류포화 이진트리 (Full Binary Tree)트리의 각 레벨에 노드가 꽉 차 있는 이진트리완전 이진트리 (Complete Binary Tree)높이가 h일 때 레벨 1부터 h-1..

입출력장치입력: CPU가 외부에서 정보를 받아들이는 과정출력: CPU가 외부로 정보를 내보내는 과정입출력 처리: CPU가 입출력장치와 정보를 주고받는 과정입력장치문자, 기호, 소리, 동영상 정보를 컴퓨터가 이해할 수 있는 2진 코드로 변환시켜, 주기억장치에 저장하거나 CPU에 전달하는 역할을 하는 것키보드, 지시장치, 원시 데이터 입력장치키보드문자, 숫자, 특수문자 키들을 통해서 입력을 발생시키고 방향키와 기능키를 통해서 수정과 편집을 쉽게 할 수 있는 가장 널리 이용되는 입력장치기계식 키보드(스프링 방식), 멤브레인 키보드(비스프링 방식) 등1975년부터 PC에 사용되기 시작101 키보드가 가장 기본지시장치마우스: 커서의 이동이나 영역을 지정할 수 있고 아이콘을 선택하고 메뉴를 실행할 수 있는 입력장치..

그래프의 활용최단경로 문제|E|>0인 그래프 G=(V, E)에서 꼭짓점 v₁, v₂ ∈ V 간의 가장 짧은 거리의 경로를 찾는 문제출발점(source): 경로의 시작점도착점(destination): 경로의 목적지가중치 방향 그래프가중치가 부여되지 않은 그래프: 경로의 길이(경로에 포함되는 모서리의 수)로 최단경로가중치가 부여된 경우: 가중치를 계산하여 가중치에 의해 최단거리가 결정가중치가 비용이라면 가중치의 합이 가장 작은 경로가 최단거리이고, 효과라면 가중치의 합이 큰 경로가 최단거리다익스트라 알고리즘그래프 G=(V, E)가 있을 때, V={v₁, v₂, ... , vₙ}이고 시작점이 v₁라고 가정했을 때 다익스트라 알고리즘에 사용되는 기호와 가정C[vᵢ, vⱼ]: 꼭짓점 vᵢ에서 vⱼ로 가는 가중치를..