해킹왕 양선규

다익스트라(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..

파이썬 코드에서 a = -7 b = 2 일 때, 1. int(a / b) -> -3 2. a // b -> -4 가 된다. 1번은 a를b로 나눈 후 정수 형태로 바꾸기 위해 소수점 부분을 미련없이 버린다. 반면 2번의 // 연산은 “내림”을 수행한다. -3.5에서 “내림”을 하면 -4가 된다. 만약 양수인 3.5였다면 3이 되었겠지만, 음수에서는 더 작은 수가 -4기 때문에 그렇다. 이것을 신경쓰며 코드를 짤 필요가 있어 보인다. DAG(Direct Acyclic Graph) - 사이클이 없는(비순환적) 방향 그래프 위상 정렬(topological sort) - 사이클이 없는 방향 그래프(DAG)에서 정점들을 순서대로 나열하는 알고리즘. “선후관계를 만족하는 정점의 순서”를 찾는다. - 순서가 정해져 있..

from collections import deque import sys input = sys.stdin.readline N, E = map(int, input().split()) # 노드, 간선 입력받기 indegree = [0 for _ in range(N + 1)] # 진입차수 저장할 리스트 graph = [[] for _ in range(N + 1)] # 연결정보 저장할 리스트 for _ in range(E): # 연결정보 입력받기 root, edge = map(int, input().split()) graph[root].append(edge) indegree[edge] += 1 # 진입차수 추가하기 def solve(): queue = deque() # 덱 사용 result = [] for i ..

import sys input = sys.stdin.readline n = int(input()) numList = list(map(int, input().split())) add, sub, mul, div = map(int, input().split()) maxValue = -1e9 minValue = 1e9 def DFS(i, calc): global add, sub, mul, div, maxValue, minValue if i == n: # 수열의 끝에 오면 최대/최솟값 구하기, 수열번호와 인덱스번호 헷갈리지 말자. # 수열번호가 1이면 인덱스번호는 0 maxValue = max(maxValue, calc) minValue = min(minValue, calc) else: if add > 0: ad..

import sys sys.setrecursionlimit(10 ** 9) # 재귀함수 최대깊이 늘려놓기 N, M = map(int, sys.stdin.readline().split()) # 노드개수, 간선개수 graph = [[] for _ in range(N + 1)] # 노드번호와 인덱스를 맞추기 위해 + 1 for _ in range(M): # 연결정보 입력받기 root, edge = map(int, sys.stdin.readline().split()) graph[root].append(edge) graph[edge].append(root) visited = [False] * (N + 1) # 노드번호와 인덱스를 맞추기 위해 + 1 visited[0] = True # 마지막에 False 존재 여부..

import sys sys.setrecursionlimit(10 ** 9) N = int(sys.stdin.readline()) # 노드의 개수 graph = [[] for _ in range(N + 1)] # 노드번호와 인덱스번호 동기화를 위해 N + 1 for _ in range(N - 1): # 연결정보 입력받기 root, edge = map(int, sys.stdin.readline().split()) graph[root].append(edge) graph[edge].append(root) visited = [False] * (N + 1) parent = [[] for _ in range(N + 1)] # 노드번호와 인덱스번호 동기화를 위해 N + 1 def dfs(graph, v, visited..

from collections import deque import sys N, M = map(int, sys.stdin.readline().split()) board = [] for _ in range(N): string = sys.stdin.readline().strip() board.append(list(map(int, string))) def isValidPos(x, y, N, M, visited): if 0

# DFS/BFS로 모든 노드 탐색 # visited 목록 만들어서 True 갯수 세면 될듯 !! import sys N = int(sys.stdin.readline()) # 노드의 개수 E = int(sys.stdin.readline()) # 간선의 개수 graph = [[] for _ in range(N + 1)] # 노드번호와 동기화 하기 위해 N + 1 for _ in range(E): root, edge = map(int, sys.stdin.readline().split()) # [1,2] 형태로 입력된다. 1번과 2번에 연결되어 있다는 뜻 graph[root].append(edge) # 무방향(양방향) 그래프이기 때문에 대칭되게 입력해 준다 graph[edge].append(root) for ..

from collections import deque import sys def DFS(graph, v, visited): # 인접노드리스트, 시작 노드, 방문목록 visited[v] = True print(v, end=' ') for i in graph[v]: # 현재 노드의 인접 노드로 재귀 if visited[i] == False: # 아직 안 갔으면 가기 DFS(graph, i, visited) def BFS(graph, start, visited): # 인접노드리스트, 시작 노드, 방문목록 queue = deque([start]) # 큐에 시작 노드 넣기 visited[start] = True while queue: v = queue.popleft() # 큐에서 노드 빼고 출력 print(v, ..