본문 바로가기

문법/Python6

[Python] Heap(힙) / heapq 모듈 1. 힙(Heap) 이란? 힙 : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림 이에 반해, 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨. 2. 힙(Heap) 구조 힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계를 성립한다. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 항상 크거나/작거나 같다 최소 힙: 부모.. 2023. 10. 27.
Python None 리턴하는 경우 dfs 문제를 풀다가 값을 넘기려고 하는 것들은 print로 찍어보면 값이 잘나오고 있었지만 마지막 반환된 결과값을 확인하면 None 가 나오고 있었다. 1) 종료조건에서만 반환을 해주면 되었나 마지막 결과값을 종료조건에 반환해주면 되었나 생각했지만 아니였다. 종료조건에 반환이 되면 전 단계로 돌아가는데 이 때 return 값이 없다! return 문이 없으면 None을 반환하게 된다. def dfs(): if 재귀 종료 조건: return cnt dfs() 결국 이 함수에서는 cnt가 종료조건에 반환이 되었다고 하더라도 전 단계에서 반환해주는 값이 없어 None 값을 반환한다. cnt -> None -> None 을 반환하며 돌아가는 것 2) return None 을 사용해야 될 때 ~가 아닌 경우이다.. 2023. 10. 25.
이진트리(Binary Tree) 출처:https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node) Understand Binary Search Tree through Gifs Binary Search Tree Degredation Gif Insertion of a node into Tree Description --> Binary Search Tree vs Sorted Array Animated Gif Comparing Sorted Array vs Binary Search Tree Description --> Optimal Binary Search Tree from Sorted Array Subtopic --.. 2023. 10. 25.
BFS(너비 우선 탐색) 스택을 이용하는 DFS와 달리 BFS는 반복 구조를 구현할 때 큐를 사용한다. 재귀로 구현 불가 큐를 이용하는 반복구현만 가능하다. graph = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'G', 'H', 'I'], 'D': ['B', 'E', 'F'], 'E': ['D'], 'F': ['D'], 'G': ['C'], 'H': ['C'], 'I': ['C', 'J'], 'J': ['I'] } BFS 구현(큐 2개 사용) visited = deque() need_visited = deque() need_visited.append(list(graph.keys())[0]) 첫번째 키 값인 'A'를 먼저 방문이 필요한 큐에 넣어준다. while need_visited:.. 2023. 10. 23.

티스토리툴바