본문 바로가기
728x90

자료구조5

[자료구조] Union-find 자료구조 python [자료구조] Union-find 자료구조 python 살펴볼 주요 개념: Union find란? Union find 구현(python) 1. Union find란? 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조. 다수의 노드들 중에 연결된 노드를 찾거나 노드들을 합칠 때 사용하는 알고리즘이다. union find는 서로소 집합(disjoint set)을 찾아내는 것에 활용된다. union find와 비슷한 것은 python에서는 set()이 있다. set은 membership 연산(어떤 원소가 집합에 속하는 지를 T/F로 알려주는)과 합집합(union), 교집합(intersection), 여집합(difference) 등의 연산을 제공한다. 하지만 파이썬의 se.. 2022. 5. 17.
[자료구조] Binary Search Tree(BST, 이진탐색트리) 정의와 python 구현 [자료구조] Binary Search Tree(BST, 이진 탐색 트리) 정의와 python 구현 살펴볼 주요 개념: 더보기 - Binary Search Tree의 정의 - Binary Search Tree 구현 방법 1. Binary Search Tree의 정의 이진탐색 트리는 탐색에 효율적인 트리이다. 이진트리의 규칙은 다음과 같다. 각 노드의 왼쪽 subtree의 값은 노드의 key값 보다 작거나 같아야 하고, 오른쪽 subtree의 값은 노드의 key값 보다 커야 한다. 12의 자리에 1이 올 수는 없다. 왜냐하면, 1이 부모 노드인 13보다 작은 수 이더라도, 10의 오른쪽 subtree이기 때문에 10보다 큰 수가 와야 하기 때문이다. 즉, 12 노드 자리에는 10~13까지만 key값으로 사용.. 2022. 5. 15.
[자료구조] Singly Linked List(한 방향 연결리스트) class 구현 (python) [자료구조] Singly Linked List(한 방향 연결리스트) class 구현 살펴볼 주요 개념: 더보기 - 한 방향 연결리스트의 클래스 구성(Node, SinglyLinkedList) - 클래스 내부 메소드 한 방향 연결리스트를 파이썬으로 구현하기 위해서는 두 개의 클래스가 필요하다. 노드 클래스를 통해 각 노드를 정의하여 링크로 잇고, 이어진 리스트를 연산에 활용하는 singlyLinkedList 클래스가 필요하다. 아래에서는 두 가지 클래스를 구현해보도록 한다. 1. 한 방향 연결리스트의 클래스(node) class Node: def __init__(self, key = None, value = None): self.key = key self.next = None def __str__(self.. 2022. 5. 14.
[자료구조] Linked List(연결리스트)의 특징 [자료구조] 살펴볼 주요 개념: 더보기 - Linked List의 정의 - 한 방향 연결리스트 vs 양 방향 연결리스트 1. Linked List(연결리스트)의 정의 연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 여기서 하나의 박스가 노드라고 보면된다. 박스의 옆부분이 링크 부분이며 각 노드 안에는 key값 또는 key값 value값 쌍이 들어간다. 다음 노드를 계속 가리키면서 하나의 줄줄이 소세지 같은 모습을 한다. 연결 리스트의 종류로는 한 방향 연결 리스트, 양 방향.. 2022. 5. 14.
[자료구조] 스택, 큐, 덱 [자료구조] 스택, 큐, 덱 들어가며. 스택, 큐, 덱은 알고리즘이라기 보다는 data를 관리하는 구조라고 할 수 있다. 스택, 큐, 덱을 활용한 알고리즘이 BFS, DFS 등등이 되는 것이다. 비유를 하자면, 우리가 운동할 때 힘(input)을 들여 수축과 이완(자료구조)을 통해 어떤 자세(알고리즘)를 반복 수행해서 근육을 얻고 지방을 태우는(Output) 과정을 수행하는 것에 비유를 할 수 있겠다. 운동은 굽히고 펴는 것부터 시작한다. 이처럼 기본적인 것이 자료구조이며, 이를 잘 알고 이에 대한 특성을 잘 활용할 때 좋은 알고리즘을 통해 뛰어난 프로그램을 만들 수 있는 것이다. 1. 기본적인 개념 더보기 배열(Array) vs 리스트(list) 가장 기본이 되는 순차적(sequential) 자료 구조.. 2022. 4. 27.
728x90

티스토리툴바