이진트리 이진트리는 모든 노드가 정확하게 두 개의 서브 트리를 가지고 있는 트리이다. 다만 서브 트리는 공백이 될 수 있다. 즉 노드의 유한 집합으로서 공백이거나 루트와 두 개의 분리된 이진트리인 경우 왼쪽 서브 트리와 오른쪽 서브 트리로 구성된다. 여기서 중요한 점은 왼쪽과 오른쪽 서브 트리를 확실하게 구분한다는 것이다. 일반적인 트리에서 두 개의 트리는 같지만 이진트리에서는 두 개의 트리는 다른 트리이다. 이는 이진트리에서는 서브 트리의 위치가 다르기 때문이다. 1) 편향 이진트리(skewed binary tree) 편향 이진트리란 모든 노드가 부모의 왼쪽 자식이기 때문에 왼편으로 편향되어 있거나 반대로 모든 노드가 부모의 오른쪽 자식으로 되어 오른쪽으로 편향되어 있어야 한다. 2) 포화 이진트리(f..

힙(Heap) 힙 자료구조는 완전 이진 트리를 기초로 하는 자료구조이다. 완전 이진트리는 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리를 말한다. 그림과 같은 형태를 띄고 있으며, 몇가지 특징들을 가지고 있다. 힙은 최대힙(Max heap)과 최소힙(Min Heap)으로 나눠진다. 최대힙은 부모노드의 값이 자식노드들의 값보다 항상 크고, 최소힙은 부모노드의 값이 자식노드의 값보다 항상 작다. (위 그림은 최대힙의 예시) 이러한 성질 때문에 항상 느슨한 정렬상태(반정렬 상태)를 유지한다. 힙은 중복값을 허용한다. 힙은 최댓값 또는 최솟값을 쉽게 뽑기 위한 자료구조 임으로 중복을 허용한다. 힙을 배열로 구현 힙은 대체적으로 배열로 구현된다. 완전이진트리를 기본으로 하기 때문에 비어있는 공간이 없..

큐의 종류 1) 큐(Queue) 2) 원형 큐(Circular Queue) 3) 연결 리스트 큐(Linked List Queue) 3-1) 단일 연결 리스트 큐 3-2) 이중 연결 리스트 큐(원형 연결 리스트 큐) 1) 큐(Queue) 입력과 출력을 한쪽 끝(front, rear)으로 제한한다. FIFO(First In First Out, 선입 선출)이라고 하며 가장 먼저 들어온 것이 가장 먼저 나간다. front : 가장 첫 원소 rear : 가장 끝 원소 즉, 큐는 rear로 들어와서 front로 나온다. 함수 enQueue() : 데이터를 rear에 넣는다. deQueue() : 데이터를 front에서 뺀다. isEmpty() : 큐가 비어있는지 확인한다. isFull() : 큐가 가득 차있는지 확..

스택(Stack) 입력과 출력이 한 곳으로 제한되어 있다. LIFO (Last In First Out, 후입선출) 이라고 하며 가장 나중에 들어온 것이 가장 먼저 나오는 자료구조이다. 함수 push() : 가장 뒤에 데이터를 넣는다. pop() : 가장 뒤에서 데이터를 뺀다. isFull() : 스택이 가득 차있는지 확인한다. isEmpty() : 스택이 비어 있는지 확인한다. 구현 push와 pop을 할 때 해당 위치를 알고 있어야 하므로 현재의 위치를 갖고 있는 '스택 포인터(SP)'가 필요하다. 스택 포인터는 다음 값이 들어갈 위치를 가리키고 있다. (처음 기본값은 -1) class stack(size) : sp = -1 stack_size = 0 def __init__(self): self.sp ..

Array Index로 빠르게 값을 찾는 것이 가능 / 선언할 때 크기와 데이터 타입 지정 / 삽입 및 삭제가 느림 ArrayList Index로 빠르게 값을 찾는 것이 가능 / 선언할 때 크기 지정 없음(메모리 동적) / 삽입 및 삭제가 느림 Linked List index로 값을 찾지 못해 검색 느림 / 데이터의 삽입 및 삭제가 빠름 Array vs ArrayList vs Linked List 배열 - 선언할 때 크기와 데이터 타입을 지정해야 한다. - 데이터가 계속 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용하기에 부적합하다. - 중간에 데이터를 삽입하거나 삭제할 때 매우 비효율적이다. (다른 데이터들을 옮겨야 하기 때문에) - 대신, 배열을 사용하면 index가 존재하기 때문에 위치를 바로 ..

Linked List(연결리스트) 란? 배열(Array)은 순차적으로 연결된 공간에 데이터를 나열하는 자료구조이고, 연결 리스트(Linked List)는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 자료구조이다. 배열은 미리 특정한 연결된 공간을 확보하고 데이터를 쓰고 있는 자료구조이고, 연결 리스트는 필요할 때마다 데이터를 추가할 수 있는 구조이다. 배열의 단점을 극복한 자료구조가 연결 리스트라고 볼 수 있다. 단일(단방향) 연결 리스트(Singly Linked List)라고도 한다. 배열과 달리 특정한 데이터를 저장할 때 해당 데이터를 저장하는 공간과 함께, 그 다음에 나올 데이터가 저장되어있는 공간을 가리키는 주소 값을 동시에 가지고 있다. 연결 리스트는 이 두 공간을 하나의 데이터로 ..