deque6 [python]11725_트리의 부모 찾기 사용한 자료구조 및 개념 : 재귀, bfs 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ 부모가 누구인지 기록할 리스트 parent를 만든다. 2️⃣ parent의 초기 설정을 0으로 하여 이 값을 활용해 방문한 노드인지 아닌지도 같이 판단한다. 재귀와 deque를 사용한 bfs 버전으로 풀었는데 bfs가 시간과 메모리 측면에서 더 효율적이었다! 👻 어려웠던 점 🚨 런타임 에러(재귀ver) ❓이유 : 재귀 버전으로 풀었을 때 재귀 호출 깊이 제한을 초과하였다. 파이썬에서는 기본적으로 재귀 호출 깊이가 제한되어 있고, 대부분 시스템에서 1000으로 설정해놓았기 때문에 트리의 최대 크기가 100.000일 수 있는 이 문제에서는 깊이 제한을 늘려줘야 했다. ❗해결 : sys.setrecursionl.. 2023. 9. 7. [python]1260_DFS와 BFS 사용한 자료구조 및 개념 : DFS, BFS, deque 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ dfs를 재귀로 구현한다. 2️⃣ bfs를 deque을 사용하여 구현한다. 👻 어려웠던 점 🚨 문제 틀림 ❓이유 : 문제의 요구사항에서 낮은 번호를 우선으로 방문해야 한다는 것을 놓쳤다..! ❗해결 : graph = [sorted(g) for g in graph] 를 추가하였다! Solution Code & 주석 import sys from collections import deque input = sys.stdin.readline def dfs(graph, start, visited): visited[start] = True result = [start] for next_node in gr.. 2023. 9. 7. [python]2060_바이러스 사용한 자료구조 및 개념 : bfs, deque 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ bfs와 deque을 사용한다. 2️⃣ 노드를 queue에 추가하여 노드와 연결된 노드들을 순회한다. 3️⃣ next_v 노드가 감염되지 않았다면 감염시키고 next_v 노드의 연결된 노드들을 확인할 수 있게 queue에 추가한다. 4️⃣ queue가 빌 때까지 반복하여 감염된 컴퓨터 수를 확인한다. Solution Code & 주석 import sys from collections import deque def bfs(v): result = 0 infected[v] = True queue = deque([v]) while queue: v = queue.popleft() for next_v in gr.. 2023. 9. 6. [python]22942_데이터 체커 1 걸린 시간 : 1h 2 사용한 자료구조 및 개념 : deque, sort 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ 각 원의 중심 좌표와 반지름을 활용하여 시작점과 끝점을 구한다. 2️⃣ 하나의 원이므로 튜플 형태( 시작점, 끝 점 )로 리스트에 담는다. 3️⃣ sort를 활용하여 시작점을 기준으로 정렬한다. → 가장 왼쪽에 위치한 원부터 차례로 검사할 수 있어 확인 과정이 수월해진다. 4️⃣ stack 최상단 원의 끝점이 현재 원의 시작점(start)보다 작다면, 이는 겹치지 않음을 뜻하므로 스택의 원 끝점을 pop한다. 예를 들어 스택에 [9, 4]가 있고 현재 비교하는 원이 (5, 7) 이라면 스택의 최상단 원의 끝점 4는 현재 비교하는 원의 시작점 5보다 작으므로 겹치지 않음을 .. 2023. 7. 14. [python]1966_프린터 큐 1 걸린 시간 : 45m 2 사용한 자료구조 및 개념 : deque 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ enumerate와deque를 사용하여 기존 순서와 값을 가진 튜플 리스트를 만든다 2️⃣ 최댓값과 현재 프린트될 순서의 값을 popleft()하여 비교 3️⃣ 같으면 출력 횟수 +1을 해주고 출력 후 break 4️⃣ 다르다면 append하여 리스트의 끝으로 낸다 👻 어려웠던 점 🚨 최적화된 방법인가? 중요도가 높은 문서를 찾기 위해 매번 max로 전체 리스트를 스캔하는것이 비효율적이라고 생각되어 다른 방법을 찾아보았다. ⇒ heapq 모듈을 사용하여 우선 순위 큐 구현! (아래에 또 구현코드 있음) Solution Code & 주석 import sys from collectio.. 2023. 7. 4. [python] 데크(deque)란? 데크(deque)의 개념 큐(queue) 선입선출(FIFO) 방식 데크(deque) 양방향 큐 앞, 뒤 양쪽 방향에서 element 추가 제거 가능 append와 pop이 압도적으로 빠름 컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거의 경우, 일반적인 리스트(list)는 O(n) 소요, 데크(deque)는 O(1) 소요 사용법 from collections import deque deq = deque() # Add element to the start deq.appendleft(10) # Add element to the end deq.append(0) # Pop element from the start deq.popleft() # Pop element from .. 2023. 6. 29. 이전 1 다음
