본문 바로가기

파이썬/파이썬 자료구조와 알고리즘8

알고리즘 (1) 기본 정렬 1. 버블 정렬(bubble sort)정렬(sorting): 데이터를 정해진 순서대로 나열하는 것두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘1-1. 버블 정렬 알고리즘 구현하기데이터가 4개일 때(예: data_list=[1, 9, 3, 2])1차 로직 적용1과 9 비교, 자리바꿈 X [1, 9, 3, 2]9와 3 비교, 자리바꿈 O [1, 3, 9, 2]9와 2 비교, 자리바꿈 O [1, 3, 2, 9]2차 로직 적용1과 3 비교, 자리바꿈 X [1, 3, 2, 9]3과 2 비교, 자리바꿈 O [1, 2, 3, 9]3과 9 비교, 자리바꿈 X [1, 2, 3, 9]3차 로직 적용1과 2 비교, 자리바꿈 X [1, 2, 3, 9]2와 3 비교, 자.. 2024. 10. 23.
파이썬 자료구조 (7) 힙 1. 힙(Heap)데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리완전 이진 트리(Complete Binary Tree): 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 2. 힙의 구조힙은 최댓값을 구하기 위한 구조(최대 힙, Max Heap)와 최솟값을 구하기 위한 구조(최소 힙, Min Heap)로 분류할 수 있음최대 힙의 경우 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다완전 이진 트리 형태 3. 힙과 이진 탐색 트리의 공통점 및 차이점공통점: 둘 다 이진 트리차이점힙은 각 노드의 값이 자식 노드보다 크거나 같다(Max Heap) 또는 작거나 같다(Min Heap)이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고 그 다음 부모 노드, 그 다음.. 2024. 10. 21.
파이썬 자료구조 (6) 트리 1. 트리Node와 Branch를 이용해 사이클을 이루지 않도록 데이터를 나뭇가지처럼 연결하는 구성의 구조트리 중 이진 트리(binary tree)형태의 구조로 탐색(검색) 알고리즘 구현을 위해 주로 사용 2. 알아둘 용어Node: 트리에서 데이터를 저장하는 기본 요소(데이터와 연결된 노드에 대한 Branch 정보 포함)Root Node: 트리 맨 위에 있는 노드Level: 최상위 노드를 레벨0으로 했을 때 하위 Branch로 연결된 노드의 깊이를 나타냄Parent Node: 어떤 노드의 상위 레벨에 연결된 노드Child Node: 어떤 노드의 하위 레벨에 연결된 노드Leaf Node: Child Node가 없는 노드Sibling Node: Parent Node가 동일한 노드 3. 이진 트리와 이진 탐색.. 2024. 10. 17.
파이썬 자료구조 (5) 해시 테이블 1. 해시 테이블(Hash Table)키(Key)에 데이터(Value)를 저장하는 자료구조파이썬에서는 해시를 별도 구현할 필요 없음보톨 배열로 미리 hash table 사이즈 만큼 생성 후 사용예) 파이썬 딕셔너리(Dictionary)타입 2. 알아둘 용어해시(Hash): 임의 값을 고정 길이로 변환하는 것해시 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조해시 함수(Hash Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수해시 값(Hash Value) 또는 해시 주소(Hash Address): 키를 해싱 함수로 연산해서 해시 값을 알아내고 이를 기반으로 해시 테이블에 해당 키에 대한 데이터 위치를 일관성 있게 찾을 수 있음슬롯(S.. 2024. 10. 16.
파이썬 자료구조 (4) 더블링크드리스트 더블링크드리스트링크드리스트의 일방향 탐색 기능을 개선한 자료구조양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 가능class Node: def __init__(self, data, prev=None, next=None): self.prev = prev self.data = data self.next = nextclass NodeMgmt: def __init__(self, data): self.head = Node(data) self.tail = self.head def insert(self,data): if self.head == None: self.head = Node(data) .. 2024. 10. 16.
파이썬 자료구조 (3) 링크드리스트 링크드리스트떨어진 곳에 존재하는 데이터를 연결하여 관리하는 자료구조하나 이상의 데이터 필드와 다음 노드의 주소를 저장하는 한 개의 포인터 필드로 구성되어 있음파이썬에서는 리스트 타입이 링크드리스트 역할도 이미 지원함데이터의 삽입과 삭제가 매우 빠름 링크드리스트 용어노드(node): 데이터 저장 단위(데이터, 포인터)로 구성포인터(pointer): 각 노드 안에서 다음이나 이전의 노드와의 연결 정보가 들어있는 공간 링크드리스트 파이썬 구현# 파이썬에서는 링크드 리스트를 구현할 때 클래스를 주로 활용class Node: def __init__(self, data): self.data = data self.next = None # Node 객체와 Node 객체를 연결.. 2024. 10. 16.

티스토리툴바