본문 바로가기

문법/Python

 (7)
정렬(sort) 버블정렬(bubble sort)* 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘  데이터가 네 개일때 [1,9,3,2]1차 순회1과 9비교, 자리바꿈없음 [1,9,3,2]9와 3비교, 자리바꿈 [1,3,9,2]9와 2비교, 자리바꿈 [1,3,2,9]2차 순회1과 3비교, 자리바꿈 없음 [1,3,2,9]3과 2비교, 자리바꿈 [1,2,3,9]3와 9 비교, 자리바꿈 없음 [1,2,3,9]3차 순회1과 2비교, 자리바꿈 없음 [1,2,3,9]2와 3비교, 자리바꿈 없음 [1,2,3,9]3과 9비교, 자리바꿈 없음 [1,2,3,9] * n개의 리스트가 있는 경우 최대 n-1번의 로직을 적용* 로직을 1번 적용할때마다 가장 큰 숫자가 뒤에서부터 1개씩..
[Python] Heap(힙) / heapq 모듈 1. 힙(Heap) 이란? 힙 : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림 이에 반해, 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨. 2. 힙(Heap) 구조 힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계를 성립한다. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 항상 크거나/작거나 같다 최소 힙: 부모..
Python None 리턴하는 경우 dfs 문제를 풀다가 값을 넘기려고 하는 것들은 print로 찍어보면 값이 잘나오고 있었지만 마지막 반환된 결과값을 확인하면 None 가 나오고 있었다. 1) 종료조건에서만 반환을 해주면 되었나 마지막 결과값을 종료조건에 반환해주면 되었나 생각했지만 아니였다. 종료조건에 반환이 되면 전 단계로 돌아가는데 이 때 return 값이 없다! return 문이 없으면 None을 반환하게 된다. def dfs(): if 재귀 종료 조건: return cnt dfs() 결국 이 함수에서는 cnt가 종료조건에 반환이 되었다고 하더라도 전 단계에서 반환해주는 값이 없어 None 값을 반환한다. cnt -> None -> None 을 반환하며 돌아가는 것 2) return None 을 사용해야 될 때 ~가 아닌 경우이다..
이진트리(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 --..
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:..
[Python]Deque Deque * 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형 * stack(스택)처럼 써도 되고 queue(큐)처럼 써도 된다. * from colections import deque 추가해서 사용하면 된다. Deque 시간복잡도에 관해 Python 리스트와 Deque의 차이 * List 시간 복잡도 Average Case Amortized Worst Case Copy O(n) O(n) Append[1] O(1) O(1) Pop last O(1) O(1) Pop intermediate[2] O(n) O(n) Insert O(n) O(n) Get Item O(1) O(1) Set Item O(1) O(1) Delete Item O(n) O(n) Iteration O(n) O(n) Get Slice O..
[Python]dictionary(HashMap) 딕셔너리란? * key, value를 한 쌍으로 가지는 자료형 * 딕셔너리에서의 Key는 고유한 값으로 중복되는 Key 값을 설정해 놓으면 하나를 제외한 나머지 것들이 모두 무시된다. * 리스트나 튜플처럼 순차적으로(sequential) 해당 요솟값을 구하지 않고 Key를 통해 Value을 얻는다. 딕셔너리 예시 dic = {'name' : 'jungmin', 'phone' : '010-9***-9***', 'birth':'0703'} 이 때 키 값은 'name', 'phone', 'birth' 'name' 값을 이용해 dic['name'] 을 입력하면 'jungmin' 을 얻을 수 있다. 딕셔너리 쌍 추가하기 dic['city'] = 'Seoul' print(dic) 실행결과 dic = {'name' ..

티스토리툴바