컴공생의 다이어리

백준 1005번 : ACM Craft (문제 바로가기) 내 코드 import sys from collections import defaultdict, deque input = sys.stdin.readline for _ in range(int(input())): n, k = map(int, input().split()) times = list(map(int, input().split())) result = times[::] indegree = [0] * n arr = defaultdict(list) for _ in range(k): a, b = map(int, input().split()) arr[a - 1].append(b - 1) indegree[b - 1] += 1 w = int(input()) -..

백준 1715번 : 카드 정렬하기 (문제 바로가기) 내 코드 import heapq import sys input = sys.stdin.readline n = int(input()) card = [int(input()) for _ in range(n)] heapq.heapify(card) result = 0 while len(card) > 1: a, b = heapq.heappop(card), heapq.heappop(card) result += a + b heapq.heappush(card, a + b) print(result)

백준 1717번 : 집합의 표현 (문제 바로가기) 내 코드 import sys sys.setrecursionlimit(10**8) def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b input = sys.stdin.readline n, m = map(int, input().split()) parent = [i for i in range(n + 1)] ..

백준 11725번 : 트리의 부모 찾기 (문제 바로가기) 내 코드 DFS 활용 import sys from collections import defaultdict sys.setrecursionlimit(10 ** 8) def dfs(graph, visited, v, result): visited[v] = True for i in graph[v]: if not visited[i]: result[i] = v dfs(graph, visited, i, result) input = sys.stdin.readline n = int(input()) arr = [[] for _ in range(n + 1)] for _ in range(n - 1): a, b = map(int, input().split()) arr[a]..

백준 7662번 : 이중 우선순위 큐 (문제 바로가기) 내 코드 import sys, heapq from collections import defaultdict input = sys.stdin.readline for _ in range(int(input())): max_heap, min_heap = list(), list() visited = defaultdict(bool) for j in range(int(input())): command = list(input().split()) if command[0] == 'I': # 데이터 삽입 heapq.heappush(min_heap, (int(command[1]), j)) heapq.heappush(max_heap, (-int(command[1]), j))..

백준 11286번 : 절댓값 힙 (문제 바로가기) 내 코드 import heapq, sys n = int(input()) heap = [] for _ in range(n): num = int(sys.stdin.readline()) if num == 0: if heap: print(heapq.heappop(heap)[1]) else: print(0) else: heapq.heappush(heap, (abs(num), num))

백준 2178번 : 미로 탐색 (문제 바로가기) 내 코드 import sys from collections import deque, defaultdict input = sys.stdin.readline def bfs(graph, start, n, m): # graph : 미로 정보 # start : 시작 좌표 d = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 상하좌우 방향 visited = defaultdict(int) # 좌표별 최소 이동 거리 저장 용 queue = deque([start]) visited[start] = 1 while queue: x, y = queue.popleft() # 현재 좌표 if graph[x][y] == 1: # 이동할 수 있는 칸인가? for x..

너비 우선 탐색(BFS, Breadth First Search) BFS는 가까운 노드부터 우선적으로 탐색하는 방식이며 레벨(level) 순서대로 접근한다. BFS는 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용된다. 큐를 활용해서 구현한다. 장점 노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있음 단순 검색 속도가 DFS보다 빠름 단점 재귀호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색 할 노드들을 저장하기 때문에 노드의 수가 많을 수록 필요없는 노드들까지 저장해야 하기 때문에 더 큰 저장공..

깊이 우선 탐색(DFS, Depth First Search) DFS는 그래프에서 깊은 부분(자식들)을 우선적으로 탐색하는 방식이다. DFS는 스택이나 재귀 함수를 사용해서 구현할 수 있다. 탐색 과정이 한없이 진행되는 것을 막고 싶다면 깊이 제한(depth bound)를 사용해서 한업이 진행되는 탐색을 막을 수 있다. 장점 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적음 최선의 경우, 가장 빠른 알고리즘. 운 좋게 항상 해에 도달하는 올바른 경로를 선택한다면, 깊이 우선 탐색이 최소 실행시간에 해를 찾음 찾으려는 노드가 깊은 단계에 있다면 BFS보다 빠르게 찾을 수 있음 단점 찾은 해가 최단 경로가 된다는 보장이 없음 최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해..

[프로그래머스] 주식가격 - 파이썬(Python) from collections import deque def solution(prices): queue = deque(prices) answer = [] while queue: price = queue.popleft() sec = 0 for q in queue: sec += 1 if price > q: break answer.append(sec) return answer https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수..