본문 바로가기

Deque4

[Python] deque의 정의, 함수, 활용 정리 1) Deque 정의 Deque는 "double-ended que"의 약자로 스택과 큐를 일반화 한 것이다. List의 경우 고정 길이 연산에 특화되어 있으며, pop(0)과 insert(0, v) 연산에 대해 O(n)의 메모리 비용이 필요한 반면 Deque의 경우 추가(append)와 꺼내기(pop) 연산을 O(1)의 속도로 지원한다. 2) deque 함수들 3) deque 생성 from collections import deque #deque 선언 queue = deque(['this', 'is', 'deque']) print(queue) # deque(['this', 'is', 'deque']) 4) deque 활용하기 from collections import deque #deque 생성 d = .. 2023. 10. 5.
[Python] deque를 활용하여 리스트 회전하기 deque.rotate()를 사용해서 리스트 회전하기 >>> from collections import deque >>> test = [1, 2, 3, 4, 5, 6, 7, 8, 9] >>> test = deque(test) >>> test.rotate(2) >>> result = list(test) >>> result [8, 9, 1, 2, 3, 4, 5, 6, 7] 알고리즘을 풀다보면 리스트를 회전하는 문제에 많이 직면하게 된다. 이는 python collection 모듈의 deque 자료형을 사용하면 쉽게 처리할 수 있다. 리스트 자료형을 deque자료형으로 바꾼후 rotate()함수를 이용하면 된다. 함수안에 음수를 넣게 된다면 왼쪽 회전 양수는 오른쪽 회전이다. 2023. 10. 5.
[SWEA 5099번] 피자굽기 from collections import deque t = int(input()) answer = [] for _ in range(t): n, m = map(int,input().split()) cheese = list(map(int,input().split())) data = [(i+1,cheese[i]) for i in range(m)] queue = deque([]) for _ in range(n): queue.append(data.pop(0)) while queue: if len(queue) == 1: v = queue.popleft() answer.append(v[0]) break index, remain = queue.popleft() if remain // 2 != 0: queue.appe.. 2023. 9. 21.
[Tree] Queue를 이용한 레벨 순서 순회 레벨 순서 순회는 직관적이어서 쉽다. 과정을 나열하면 아래와 같다. 루트부터 방문하고, 루트의 왼쪽과 오른쪽을 방문한다. 루트 왼쪽 노드의 왼쪽과 오른쪽을 방문한다. 루트 오른쪽 노드의 왼쪽과 오른쪽을 방문한다. 즉, 현재 노드를 방문할 때 현재 노드의 왼쪽과 오른쪽 노드를 차례로 큐에 넣어 둔다. 그리고, 큐에서 순서대로 꺼내서 같은 방식으로 처리한다. 여기서는 파이썬의 리스트를 Queue로 사용한다. from collections import deque tree = ["A", "B", "C", "D", "E", "F", None, "G"] def levelorder(tree): if not tree: return queue = deque([0]) while queue: parent = queue.po.. 2023. 9. 7.

티스토리툴바