개발왕 양선규

# 도치가 사방으로 가는 것과, 물이 도치의 방문목록에 영향을 받는 것(도치가 지나간 길 안가는것)은 결과에 영향을 미치지 않는다. import sys from collections import deque input = sys.stdin.readline R, C = map(int, input().split()) # 행, 열 forest = [list(input().strip()) for _ in range(R)] visited = [[-1] * C for _ in range(R)] # -1로 설정해두고 도치의 이동 과정을 입력할것이다 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] queue = deque() for x in range(R): for y in range(C): if f..

import sys sys.setrecursionlimit(10 ** 9) input = sys.stdin.readline # 이분 그래프 판별 DFS 함수 def DFS(graph, start, visited, group): visited[start] = group for i in graph[start]: if visited[i] == 0: # 방문 안 한 곳이라면 result = DFS(graph, i, visited, -group) if not result: return False # 하위에서 이분 그래프 아니라고 판단했다면 함수 종료 elif visited[i] == group: # 인접노드인데 그룹이 같을경우 이분그래프 아님 return False return True # 입력받은 갯수만큼 그래..

import heapq import sys input = sys.stdin.readline N, E = map(int, input().split()) # 노드, 간선 graph = [[] for _ in range(N + 1)] # 그래프 입력받기 for _ in range(E): a, b, c = map(int, input().split()) graph[a].append((c, b)) graph[b].append((c, a)) visited = [False] * (N + 1) # 방문체크 리스트 def prim(graph, start): # 그래프, 시작노드 입력받는다, 프림 알고리즘 사용 visited[start] = True # 시작노드 방문체크 distance = 0 # 거리(가중치)를 계산할 변..

캐시 메모리를 사용하면 컴퓨터의 성능이 향상되는 이유 지역성(Locality) - 프로그램이 메모리에 접근할 때, "특정 부분을 집중적으로 사용"하는 경향 시간적 지역성(Temporal Locality) - 한 번 접근된 데이터는 가까운 미래에 다시 접근될 가능성이 높다. - ex) 루프 내에서 반복적으로 사용되는 변수 공간적 지역성(Spatial Locality) - 메모리의 특정 주소에 접근한 후, 그 주변 주소에 있는 데이터에 접근될 가능성이 높다 - ex) 배열, 연속적인 메모리 블록 등 캐시 메모리는 지역성 원리를 활용하여, 자주 사용되거나 연속적으로 사용될 가능성이 높은 데이터를 미리 캐시에 저장한다. 이로 인해 CPU는 필요한 데이터를 캐시에서 빠르게 찾을 수 있다. 메모리 계층구조 L0 :..

import heapq import sys INF = int(1e9) input = sys.stdin.readline N = int(input()) board = [] for _ in range(N): # 미로 입력받기 board.append(list(map(int, input().strip()))) distroy = [[INF for _ in range(N)] for _ in range(N)] # 부순갯수 visited = [[False for _ in range(N)] for _ in range(N)] # 방문목록 def goingNogoing(x, y): # 갈지말지 정하는함수 if 0

from collections import deque import sys input = sys.stdin.readline M, N, H = map(int, input().split()) # 가로, 세로, 높이 5, 3, 2 box = [] for i in range(N * H): # 토마토 입력받기 box.append(list(map(int, input().split()))) visited = [[False] * M for _ in range(N * H)] # 방문목록 box와 똑같이 만들기 def goingNogoing(box, x, y, visited): # 익힐수있는지 고민하는함수 if 0

import heapq import sys INF = int(1e9) input = sys.stdin.readline N = int(input()) # 도시 개수 ( 노드 개수 ) E = int(input()) # 버스 개수 ( 간선 개수 ) graph = [[] for _ in range(N + 1)] for _ in range(E): a, b, c = map(int, input().split()) # 출발노드, 도착노드, 거리 입력받기 graph[a].append([c, b]) # (거리, 도착노드) start, end = map(int, input().split()) # 계산해야 할 출발지, 도착지 distance = [INF] * (N + 1) # 최단 경로 리스트 def dijkstra(star..

import heapq import sys INF = int(1e9) input = sys.stdin.readline N, E, K, start = map(int, input().split()) # 노드, 간선, 찾을거리, 출발노드 graph = [[] for _ in range(N + 1)] for _ in range(E): a, b = map(int, input().split()) # 출발노드, 도착노드 graph[a].append([1, b]) # 거리(1), 도착노드 distance = [INF] * (N + 1) def dijkstra(start): queue = [] heapq.heappush(queue, (0, start)) # 시작노드거리, 시작노드 큐에 삽입 distance[start] ..

다익스트라(dijkstra) 알고리즘(최단 경로 알고리즘) - 그래프에서 한 정점까지의 최단 경로를 구하는 알고리즘 - 이 과정에서 도착 정점 뿐만 아니라, 모든 다른 정점까지 최단 경로로 방문한다. - 최단 경로를 구하는 과정에서, “각 노드에 대한 현재까지의 최단 거리” 정보를 항상 저장하고 갱신한다. - 매번 가장 비용이 적은 노드를 선택하는 것을 반복하기 때문에 그리디 알고리즘으로 분류되기도 한다. - 방향/무방향 그래프인지는 상관없다. 다익스트라 알고리즘 동작과정 - 우선순위 큐 사용을 위해 파이썬 heapq를 사용한다. 최소 힙으로 동작하기 때문에 항상 최단 거리를 pop하게 된다. 1. 최단 거리 테이블을 전부 INF(무한)으로 초기화한다. ( 일반적으로는 INF = int(1e9) 이다.)..

from collections import deque import sys input = sys.stdin.readline N = int(input()) # 노드(부품) 개수 E = int(input()) # 간선 개수 indegree = [0 for _ in range(N + 1)] # 진입차수 담을 리스트 needs = [[0] * (N + 1) for _ in range(N + 1)] # 부품별 요구부품량 담을 리스트 graph = [[] for _ in range(N + 1)] # 연결정보 담을 리스트 for _ in range(E): leaf, root, money = map(int, input().split()) graph[root].append([leaf, money]) indegree[lea..