본문 바로가기
728x90

Python38

[자료구조] 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.
python 로또 번호 추출기 2탄 python으로 로또 추출기를 만든지 한 달 넘게 지났다. 자바로 했던 것을 파이썬으로 옮겨 놓는 것이 1탄이었다면, 무식했던 방법을 새로운 정렬 알고리즘을 통해 다시 만들어보고자 한다. 기존의 코드의 단점은 1000만 개 이상의 번호를 만들면 과도한 시간이 걸리는 것이었다. 2022.04.18 - [프로그래밍/재미있는 코딩놀이] - python 로또 번호 생성기 그래서 최근에 배운 계수정렬을 활용하면 딕셔너리를 활용하지 않고 충분히 많이 만들어진 로또 번호를 6개 골라낼 수 있을 것 같았다. 왜냐하면 계수 정렬에 필요한 리스트의 크기가 45이면 충분했기 때문이다. 메모리 용량도 그렇게 많이 잡아먹지 않고, 빠르게 연산할 수 있다고 생각했다. 바로 실행에 옮겼다. ** 기존 코드 import random.. 2022. 5. 15.
[자료구조] Binary Tree(이진트리) 구현과 traversal(순회) 구현 python [자료구조] Binary Tree(이진트리) 구현과 traversal(순회) 구현 python 살펴볼 주요 개념: 더보기 - Binary Tree 구현 방법 - Tree traversal의 종류와 구현 방법 1. Binary Tree 구현 방법 리스트, 재귀적 리스트, 노드 클래스 구현의 방법이 있다. 노드 클래스 구현만 살펴본다. class Node: def __init__(self, key): self.key = key self.parent = self.left = self.right = None def __str__(self): return str(self.key) 2. Tree traversal의 종류와 구현 방법 Traversal(순회) : 노드들을 순서에 따라 방문하며 key 값을 출력하는 것.. 2022. 5. 15.
[자료구조] Heap 기초 개념 알아보기(python) [자료구조] Heap 기초 개념 알아보기(python) 살펴볼 주요 개념: 더보기 - 힙이란? - 힙을 충족하는 트리 형태 - 힙 직접 구현 1. 힙이란? 힙 성질(heap property)을 만족하는 이진트리(Binary Tree)이다. * 힙 성질 - 모양성질 : 레벨 별로 모든 노드가 꽉 차있고, 마지막 레벨의 노드만 왼쪽에서부터 차있는 형태 - heap 성질 : 모든 부모노드의 key값이 자식노드의 key값보다 작지 않다. 힙 성질을 만족하는 트리를 리스트화 해서 표현하면 다음과 같다. A = [15, 12, 6, 11, 10, 2, 3, 1, 5] 루트 노드에는 리스트에서 가장 큰 값이다. 힙은 insert와 remove(최대값 삭제), maxHeapify 연산을 지원한다.(max heap) 각.. 2022. 5. 15.
[자료구조] Tree 기본 개념 알아보기 [자료구조] Tree 기본 개념 알아보기 살펴볼 주요 개념: 더보기 - 트리의 개념 - 트리의 표현법(python) 1. 트리의 개념 트리(tree)는 부모 - 자식 간의 관계의 노드로 구성되어 있다. 한 방향 연결리스트와 비슷하다. 한 방향 연결리스트의 경우, 한 부모에 한 자식 밖에 없는 트리구조인 것이다. 트리는 두 개 이상의 자식 노드를 가질 수 있다. 세 개 이상의 자식을 가지는 2, 3, 4 트리와 같은 것도 존재한다. 각각의 노드에는 key값이 들어가 있다. 각각의 용어 설명을 해보자면 다음과 같다. 루트 노드 : 맨 꼭대기에 위치한 조상과 같은 노드 링크 or 에지 : 부모 노드와 자식 노드 사이를 이어주는 선 리프 노드 : 더 이상의 자식 노드가 없는 노드 형제 노드 : level이 같고.. 2022. 5. 15.
[자료구조] hash table(해시 테이블) python class 구현하기 [자료구조] hash table(해시 테이블) python class 구현하기 살펴볼 주요 개념: 더보기 - 해시 테이블의 개념, 특징, 용도 - 해시 함수 - 해시 충돌 회피 - 해시 테이블 클래스 구현(python) 1. 해시 테이블의 개념, 용도, 중요 요소 (1) 해시 테이블의 개념 : 해시 테이블이란 키값에 데이터를 저장하는 데이터 구조이다. key를 통해 데이터(value)를 받아올 수 있으므로 삽입, 삭제, 탐색 연산이 획기적으로 빨라진다. 파이썬에서는 딕셔너리 타입이 해시 테이블의 특징을 가지고 있다. : 해시 테이블은 테이블 사이즈 만큼 배열을 생성하여 사용한다. 특정한 함수(해시 함수)를 통해 key를 인덱스로 mapping을 하고, 테이블 내의 공간에 데이터를 저장하는 것이다. : 파.. 2022. 5. 15.
728x90

티스토리툴바