Study/자료구조

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

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

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

탐색탐색: 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업맵, 딕셔너리: 탐색을 위한 자료구조, 엔트리 또는 키를 가진 레코드의 집합엔트리키: 영어 단어와 같은 레코드를 구분할 수 있는 탐색키값: 단어의 의미와 같이 탐색키와 관련된 값맵 ADT데이터: 키를 가진 레코드(엔트리)의 집합연산search(key): 탐색기 key를 가진 레코드를 찾아 반환insert(entry): 주어진 entry를 맵에 삽입delete(key): 탐색기 key를 가진 레코드를 찾아 삭제맵을 구현하는 방법리스트 이용: 정렬 / 비정렬 (가장 간단한 구현 방법)이진 탐색 트리 이용: 탐색 성능을 향상 시키고자 하는 경우해싱 구조 이용: 맵을 구현하기 가장 좋은 방법순차 탐색Sequential Search정렬되지 않은 배열에 ..

정렬데이터를 순서대로 재배열하는 것가장 기본적이고 중요한 알고리즘비교할 수 있는 모든 속성들은 정렬의 기준이 될 수 있음오름차순(ascending)과 내림차순(descending)정렬 알고리즘의 종류정렬 장소에 따른 분류내부 정렬: 모든 데이터가 메인 메모리외부 정렬: 외부 기억 장치에 대부분의 레코드단순하지만 비효율적인 방법삽입, 선택, 버블 정렬 등복잡하지만 효율적인 방법퀵, 합, 병합, 기수정렬, 팀 등선택 정렬Selection Sort여러 데이터 중에서 가장 작은 값을 뽑는 작동을 반복하여 값을 정렬최솟값을 찾는 방법첫 번째 값을 현재 가장 작은 값으로 지정지정한 값을 다음 차례의 값과 비교하여 더 작은 값을 현재 가장 작은 값으로 변경하거나 유지마지막 값까지 비교를 마친 후 현재 가장 작은 값으..

연결된 구조흩어진 데이터를 링크로 연결해서 관리배열 구조의 리스트연결된 구조의 리스트모든 노드들을 연속된 메모리 공간에 저장노드들이 물리적으로 떨어진 곳에 위치확보된 공간을 넘어서 새로운 노드를 저장할 수 없음각 노드의 번지도 순차적이지 않음 화살표로 표시된 연결을 따라가면 선형 리스트 순서와 같음용량이 고정되지 않음배열 구조의 리스트연결된 구조의 리스트할당된 메모리 공간을 사용하지 않으면 메모리 낭비필요한 만큼 메모리 할당, 크기의 제한도 없음 - 효율성할당된 메모리 공간을 넘어서는 새로운 항목 삽입 불가 중간에 자료를 삽입하거나 삭제하는 것이 용이배열 구조의 리스트연결된 구조의 리스트항목 삽입/삭제 시 뒤의 모든 항목들을 이동항목 삽입/삭제 시 연결(Link)만 수정연결 리스트의 구조노드(Node)데..