Koo's.Co

1. 우선순위 큐 - 우선순위 큐는 각 원소들이 우선순위를 갖고 있는 추상 자료형이다. - FIFO 구조를 갖는 큐와 다르게 우선순위 큐는 들어온 순서와 상관없이 우선순위가 높은 원소가 먼저 나간다. - 원소를 추가하거나 제거할 때 우선순위를 갖고 수행해야 한다. - 우선순위 큐와 힙은 같지 않다. 우선순위 큐는 힙 외에도 배열이나 연결 리스트로도 구현 가능하다. - 배열을 이용해 우선순위 큐를 구현하면 삽입할 때 최악의 경우 시간 복잡도가 O(N)이 된다. (추가하는 위치 이후에 있는 모든 원소들을 뒤로 한 칸씩 옮겨줘야 하기 때문에) - 연결리스트로 구현할 때도 삽입 위치를 찾을 때 최악의 경우 O(N)이 소요되기 때문에 배열이나 연결 리스트보다는 힙을 이용한 우선순위 큐가 훨씬 효율적이다. 2. 힙..

1. 힙? - 힙은 최댓값이나 최솟값을 하기 위해 사용되는 완전 이진트리 형태의 자료구조이다. - 부모 노드는 항상 자식 노드보다 더 높은 우선순위를 가진다. - 힙은 완전 이진트리로 정렬된 구조가 아니다. - 부모 노드가 자식 노드보다 항상 작은 힙을 최소 힙, 부모 노드가 자식 노드보다 큰 힙을 최대 힙이라 한다. - 형제 노드 간의 대소 관계가 보장되는 이진 탐색 트리와 다르게 힙은 형제 노드 간의 대소 관계는 보장되지 않는다. - 힙은 부모 노드와 자식 노드 간의 대소 관계만을 보장한다. - 우선순위 큐와 힙은 다른 개념이다. 우선순위 큐는 각 원소들이 우선순위를 갖는 추상적인 자료형으로 여러 방법으로 구현할 수 있는데 그중에서 힙을 많이 사용하는 것이다. 2. 최소 힙과 최대 힙의 비교 파이썬에..

이진 탐색 트리를 구현하기에 앞서 기본적인 트리의 구현을 해보려 한다. 오늘 구현할 트리는 별도의 기능을 갖지 않고 트리의 순회를 중점적으로 보려 한다. 순회란 트리를 돌면서 어떤 원소가 있는지 확인하는 작업을 말한다. 이 때 어느 원소를 먼저 보는지에 따라 순회의 종류가 달라진다. 트리의 순회는 재귀 방법으로 쉽게 구현할 수 있다. 위의 트리를 코드로 구현해 보자 1. 트리의 구조 class Node(object): def __init__(self, item): self.item = item self.left = self.right = None class BinaryTree(object): def __init__(self): self.root = None - Node class에서 item원소는 루트(..

1. 트리란? - 노드로 구성된 비선형 자료구조로 계층구조를 나타낼 때 사용 - 하나의 루트 노드를 가짐 - 루트 노드는 0개 이상의 자식 노드를 가짐 - 그래프의 한 종류로 사이클을 갖지 않는 그래프 - 나무의 가지처럼 계속 뻗어 나가는 계층구조로 나무를 뒤집은 모습을 생각해보자 - 컴퓨터에서 폴더 안에 폴더와 파일이 있는 구조도 트리 구조 2. 트리 관련 용어 - 간선(Edge): 노드들을 연결하는 선 - 루트 노드(Root Node): 부모 노드가 없는 최상위 노드, 트리는 하나의 루트 노드를 갖는다 - 단말 노드(Leaf Node): 자식이 없는 노드 - 부모 노드(Parent Node): 자식 노드를 갖는 상위 노드 - 자식 노드(Child Node): 부모 노드가 갖는 노드들 - 깊이(dept..

스택과 마찬가지로 파이썬에서는 데큐를 이용하면 큐의 기능을 모두 사용할 수 있다. enqueue 연산은 append로, deque 연산은 popleft를 사용하면 된다. 여기서는 이중 연결리스트를 이용해 큐를 구현해보려 한다. 구현하려는 큐의 추상 데이터 타입은 다음과 같다. empty(): 비었다면 True를, 아닐 경우 False를 반환 enqueue(item): 큐에 rear에 item을 삽입 deque(): 큐에 front에 있는 item을 출력 __len__(): 큐의 크기를 반환 1. 큐 이전에 구현한 이중 연결리스트를 이용해 큐를 구현하려 한다 from LinkedList import DoubleLinkedList class Queue(object): def __init__(self): se..

이중 연결리스트는 단순 연결리스트와 다르게 앞뒤 노드, 양쪽 방향으로 링크를 갖는 구조이다 단순 연결리스트의 구조를 이해하고 있으면 이중 연결리스트는 쉽게 이해할 수 있다결리스트는 단순 연결리스트와 다르게 앞뒤 노드, 양쪽 방향으로 링크를 갖는 구조이다 단순 연결리스트의 구조를 이해하고 있으면 이중 연결리스트는 쉽게 이해할 수 있다 이중 연결리스트는 단순 연결리스트와 다르게 이전 노드에 접근이 가능하다는 장점이 있다 이전 노드에 접근할 수 있다는 말은 특정 노드 이전의 값을 삭제하거나 역으로 출력하는 등 추가적인 연산이 가능하다 구현하려는 이중 연결리스트의 추상 데이터 타입은 다음과 같다 empty(): 리스트가 비었다면 True, 아닐 경우 False를 반환 append(data): 리스트의 맨 뒤에 ..

큐란? 큐는 스택과 함께 대표되는 선형 자료구조이다. 큐는 스택과 다르게 들어오는 방향과 나가는 방향이 정해져 있다. 선입선출(FIFO) 자료구조로 큐 안에 먼저 입력된 원소가 큐에서 꺼낼 때도 제일 먼저 출력된다. 계산대에 줄을 선 사람들 (들어온 순서대로 먼저 계산을 하고 나가는 모습) 이나 프린터기에서 먼저 들어온 순서대로 인쇄가 되는 모습을 생각하면 된다. 큐 안에 원소를 집어넣는 enque 연산, 맨 먼저 입력된 원소를 출력하는 deque 연산을 갖고 추가적으로 필요에 따라 가장 앞선 원소를 확인하는 front 연산이나 가장 마지막 원소를 확인하는 rear 연산을 구현할 수 있다. 큐를 배열로 구현할 때는 몇가지 문제점이 존재한다. enqueue를 할 때는 문제가 발생하지 않지만 deque를 할..

파이썬에서 제공하는 리스트를 사용하면 스택의 기능을 모두 사용할 수 있다. push연산은 append, pop연산은 그대로 pop을 이용하면 된다. 여기서는 노드를 이용해 스택을 구현해보려 한다. 구현하려는 스택의 추상 데이터 타입은 다음과 같다. empty() : 비었다면 True를, 아닐 경우 False를 반환 push(item) : 스택에 item을 삽입 pop() : 스택에 마지막으로 들어온 item을 반환, 스택이 비어있는 경우 False를 반환 peek() : 스택에 마지막으로 들어온 item을 반환 __len__() : 스택에 크기를 반환 1. 노드 class Node(object): def __init__(self, item, pointer): self.item = item self.poi..

스택이란? 스택은 원소의 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 선형 자료구조이다. 나중에 들어온 원소가 제일 먼저 나가는 후입선출(LIFO: Last In First Out) 구조를 갖는다. 책을 상자 안에 쌓아서 넣을 때, 나중에 쌓은 책을 먼저 빼는 모양을 생각할 수 있다. 스택 안에 원소를 집어넣는 push연산, 삽입된 원소를 빼내는 pop연산, 제일 위에 있는 원소값을 반환하는 peek연산을 갖는다. 컴퓨터 내부에서 프로그램에 대한 정보를 저장하는 자료구조에도 쓰이는 등 컴퓨터 내부에서도 많이 사용된다. 간단하게 구현가능하면서도 여러 상황에 응용할 수 있어 많이 쓰이는데 힙 영역에 데이터를 저장하거나 재귀함수를 호출하는 과정도 스택 형태로 사용된다.