📝 배운 것들
🏷️ 위상 정렬
- 진입하는 간선이 없는 노드를 큐에 담는다.
- 큐에서 노드를 꺼내고 노드에 연결된 간선을 없앤다.
- 1번과 2번을 반복한다.
여기서 큐에서 꺼내진 순서가 위상정렬을 수행한 결과가 된다.
🏷️ while문 깔끔하게 만들기
while len(nodeQueue) != 0:이것보단
while queue:이게 더 깔끔한듯
🏷️ 딕셔너리 선언법
test = dict() 이거 대신 test = {} 써야 하는 이유
test = dict()와 test = {}는 모두 파이썬에서 딕셔너리를 초기화하는 방법입니다. 하지만 test = {}를 사용하는 것이 일반적으로 더 선호됩니다. 그 이유는 다음과 같습니다:
- 간결함:
test = {}는 더 간단하고 읽기 쉽습니다. - 일관성: 다른 기본 자료형의 초기화 방법과 일관성을 유지합니다. 예를 들어, 빈 리스트는
[], 빈 집합은set(), 빈 튜플은()로 초기화합니다. - 성능:
{}가dict()보다 약간 더 빠릅니다. 이는 파이썬 내부 구현에서 중간 함수 호출을 피하기 때문입니다.
🏷️ float('inf')의 의미
distances = [float('inf')] * (N+1)
이거 어케 최댓값이 되는거임 float('inf')가 뭔데
float('inf')는 파이썬에서 무한대를 나타내는 값입니다. 이는 수학적으로 정의된 양의 무한대를 의미하며, 매우 큰 값을 나타낼 때 사용됩니다.
용도
- 최단 경로 알고리즘: 다익스트라 알고리즘이나 벨만-포드 알고리즘과 같은 최단 경로 알고리즘에서 초기 거리 값을 매우 큰 값으로 설정하여 초기값이 최소값으로 대체되도록 합니다.
- 비교: 어떤 값이 다른 모든 값보다 크다고 가정할 때 사용됩니다.
예제
distances = [float('inf')] * (N + 1)
# N은 도시의 수를 나타내며, 각 도시까지의 초기 거리를 무한대로 설정합니다.
# 이는 다익스트라 알고리즘에서 출발 도시에서 다른 모든 도시까지의 최소 거리를 찾을 때 유용합니다.🏷️ comprehension 쓰면 안될 때
왜
distances1 = [float('inf') for _ in range(N)]
이것보다
distances2 = [float('inf')] * (N)
이게 더 좋은건데?
다익스트라 알고리즘에서 다음과 같은 두 가지 방법으로 리스트를 초기화할 수 있습니다:
distances1 = [float('inf') for _ in range(N)]
distances2 = [float('inf')] * (N)차이점 및 이유
-
성능 및 효율성:
distances2 = [float('inf')] * (N):- 성능 면에서 더 효율적입니다.
float('inf')객체를 한 번 생성하고 이를N번 복제하여 리스트를 초기화합니다.- 이는 단순한 반복 복제 작업이므로 빠르게 실행됩니다.
distances1 = [float('inf') for _ in range(N)]:- 리스트 컴프리헨션을 사용하여 각 요소를 개별적으로 초기화합니다.
- 각 반복마다
float('inf')를 새로 생성하므로, 상대적으로 더 많은 연산을 수행하게 됩니다. - 초기화 속도가
distances2보다 느릴 수 있습니다.
-
가독성 및 코드 일관성:
- 성능 외에도
distances2방식은 간결하고 직관적입니다. 이는 코드의 가독성을 높이고, 다른 기본 자료형을 초기화할 때 사용하는 방식과 일관성을 유지합니다.
- 성능 외에도
⚔️ 백준
📌 2252 줄 세우기
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
# 진입차수 관리하는 리스트
indegree = [0 for _ in range(N+1)]
# 딕셔너리로 인접 리스트 구현
order = dict()
for i in range(N+1):
order[i] = set()
for j in range(M):
A, B = map(int, input().split())
order[A].add(B)
indegree[B] += 1
# 위상 정렬 실행
# 진입하는 간선이 없는 노드를 큐에 담는다.
# 큐에서 노드를 꺼내고 노드에 연결된 간선을 없앤다.
# 1번과 2번을 반복한다.
# 진입 차수에 대한 정보가 필요
# 노드 큐 길이도 따로 관리하면 성능 약간 빨라질듯
from collections import deque
# 진입차수가 0이 된 노드들을 관리하는 큐
nodeQueue = deque()
for i in range(len(indegree)):
if indegree[i] == 0:
nodeQueue.append(i)
# 최종 순서를 담는 리스트
final_order = []
# 큐에서 노드를 꺼내고 연결된 간선을 없앤다
while nodeQueue:
node = nodeQueue.pop()
final_order.append(node)
for next in order[node]:
indegree[next] -= 1
if indegree[next] == 0:
nodeQueue.append(next)
del final_order[-1]
for order in final_order:
print(order, end=' ')↑ 정답 코드
진입하는 간선이 없는 조건을 만족하는 간선을 찾기 위해서
1. 맨 처음 순회를 하며 진입차수가 0인 간선을 모두 큐에 넣는다
2. 큐에서 하나씩 꺼내며 다음 노드로 가는 간선을 지운다
3. 다음 노드의 진입 차수도 1 줄인다
4. 만약 줄였는데 0이 됐으면 큐에 넣는다
인덱스 관리 직관적으로 편하게 하려고 range(N+1)까지 만들어서
안쓰는 노드인 0도 마지막에 프린트되는 현상이 발생했었음.
del final_order[-1] 이렇게 임시로 해결했는데
# 진입차수가 0이 된 노드들을 관리하는 큐
nodeQueue = deque()
for i in range(len(indegree)):잘 살펴보니 이 부분이 이상했다.
indegree 초기화할 때 분명 range(N+1)로 했는데
굳이 길이를 또 구할 필요가 없었고,
처음에 indegree 순회하며 0인 노드들을 큐에 넣는 거니까
순회 시작을 1로 잡아주면 애초에 들어가질 않는다.
# 진입차수가 0이 된 노드들을 관리하는 큐
nodeQueue = deque()
for i in range(1,N+1):
if indegree[i] == 0:
nodeQueue.append(i)이렇게 바꿔주고 del도 없애고 다시 제출했더니
조금 더 빨라졌다.
📌 2637 장난감 조립
# 알고 싶은 것 : 내가 알아야 하는 물품이 중간 부품인지 완제품인지
# 완제품의 재료를 알아야 한다면) 진입 차수가 0인 것들을 훑고 set를 순회하며 기본 부품들의 개수를 더해주기
# 중간 부품이면) ingridient 한 번만 돌리기문제를 제대로 안 읽고 스스로 이상한 조건을 추가하고 있었다.
문제에서 요구하는 건 완제품에 필요한 기본 부품 갯수인데
중간 제품에 드는 기본 부품 갯수가 필요할 때도 있다는 착각을 해버렸다.
제발 문제를 잘 읽자.
import sys
input = sys.stdin.readline
N = int(input()) # 기본 부품, 중간 부품 가지수
M = int(input()) # 설계도 개수
# 설계도 초기화
indegree = [0 for _ in range(N+1)]
blueprint = dict()
for i in range(N+1):
blueprint[i] = set()
# 설계도 받아오기
for _ in range(M):
# X : 만들 제품, Y : 재료 부품 번호, K : 필요한 개수
X, Y, K = map(int,input().split())
blueprint[X].add((Y,K))
indegree[Y] += 1
# 기본 부품 더해주기
def ingridient(p, amount):
if not blueprint[p]:
result[p] += amount
return
for need in blueprint[p]:
ingridient(need[0], need[1]*amount)
result = [0 for _ in range(N+1)]
from collections import deque
# 진입 차수가 0인 것들을 훑고
# set를 순회하며 기본 부품들의 개수를 더해주기
middleQueue = deque()
for i in range(1,N+1):
if indegree[i] == 0:
middleQueue.append(i)
for middle in middleQueue:
ingridient(middle, 1)
for i in range(1,N+1):
if result[i] != 0:
print(i, result[i])테스트 케이스는 맞는데 자꾸 시간초과가 난다.
로직이 간단해서 고칠만한 부분이 안 보인다.
문제가 될 만한 부분은 이미 답을 알고 있는 부품을 또 검색한다는 것.
이걸 구현해봐야겠다.
import sys
input = sys.stdin.readline
N = int(input()) # 기본 부품, 중간 부품 가지수
M = int(input()) # 설계도 개수
# 설계도 초기화
indegree = [0 for _ in range(N+1)]
blueprint = dict()
blueprint_done = dict()
for i in range(N+1):
blueprint[i] = set()
blueprint_done[i] = set()
# 설계도 받아오기
for _ in range(M):
# X : 만들 제품, Y : 재료 부품 번호, K : 필요한 개수
X, Y, K = map(int,input().split())
blueprint[X].add((Y,K))
indegree[Y] += 1
# 기본 부품 더해주기
def ingridient(p, amount):
# 완성된 설계도가 있다면
if blueprint_done[p]:
for need in blueprint_done[p]:
result[need[0]] += need[1]
print(need[0],need[1])
return
# 기본 부품이라면 amount를 추가한다
if not blueprint[p]:
result[p] += amount
blueprint_done[p].add((p,amount))
return
# 중간 부품이라면 재료 부품을 순회하며 기본 부품 개수 알아내기
for need in blueprint[p]:
ingridient(need[0], need[1]*amount)
result = [0 for _ in range(N+1)]
from collections import deque
# 진입 차수가 0인 것들을 훑고
# set를 순회하며 기본 부품들의 개수를 더해주기
middleQueue = deque()
for i in range(1,N+1):
if indegree[i] == 0:
middleQueue.append(i)
for middle in middleQueue:
ingridient(middle, 1)
# for i in range(1,N+1):
# if result[i] != 0:
# print(i, result[i])해보려고 했는데 안됨.
동기한테 물어봤더니 애초에 위상 정렬을 쓰지 않은 것이 잘못이었음.
import sys
from collections import deque
sys.stdin = open("input.txt", "r")
N = int(sys.stdin.readline().rstrip())
M = int(sys.stdin.readline().rstrip())
need_parts = [[] for row in range(N+1)]
parts_needed = [0]*(N+1)
EA_list = [0]*(N+1)
visited = [0]*(N+1)
basic = []
for m in range(M):
x, y, EA = map(int,sys.stdin.readline().split())
need_parts[x].append([y,EA])
parts_needed[y] += 1
while sum(parts_needed) > 0:
for i in range(1,N+1):
if not need_parts[i] and visited[i] == 0:
basic.append(i)
visited[i] = 1
if parts_needed[i] == 0 and visited[i] == 0:
if EA_list[i] == 0:
EA_list[i] = 1
visited[i] = 1
for j in need_parts[i]:
EA_list[j[0]] += j[1]*EA_list[i]
parts_needed[j[0]] -= 1
for i in basic:
print(i, EA_list[i], sep=" ")모르겠어서 그냥 답 봄.
- rstrip()의 의미:
- rstrip()은 문자열의 오른쪽 끝에서 공백이나 특정 문자를 제거하는 함수입니다. 이 코드는 줄 끝에 있는 개행 문자('\n')를 제거하기 위해 사용됩니다.
- sys.stdin = open("input.txt", "r")의 목적:
- 이 코드는 표준 입력을 "input.txt" 파일로 바꾸는 역할을 합니다. 로컬 환경에서 파일로부터 입력을 받기 위해 사용되며, 백준에서는 일반적으로 사용하지 않습니다. 백준에서는 기본적으로 표준 입력을 통해 문제를 풀이합니다.
- sep=" "의 의미:
- print() 함수에서 sep=" "는 출력 시 각 항목 사이에 공백을 넣겠다는 의미입니다. 기본값이 공백이지만, 명시적으로 설정할 수도 있습니다.
📌 18352 특정 거리의 도시 찾기
import sys
input = sys.stdin.readline
# bfs 한 뒤에 depth가 k인 도시들을 출력한다
# visited 필요 없을듯?
# 최솟값을 담는 배열을 하나 만들면 될듯
N, M, K, X = map(int, input().split())
graph = {i: [] for i in range(1,N+1)}
graph_min = [N+1 for _ in range(N+1)]
for _ in range(M):
A, B = map(int, input().split())
graph[A].append(B)
from collections import deque
def bfs(node, visited, waiting):
visited.add(node)
waiting.append(node)
courses = []
depth = 0
graph_min[node] = depth
while len(waiting) != 0:
qSize = len(waiting)
depth += 1
for _ in range(qSize):
node = waiting.pop()
for near in graph[node]:
waiting.append(near)
visited.add(near)
# 최단거리 갱신 및 조건 파악
if graph_min[near] > depth:
graph_min[near] = depth
if depth == K and graph_min[near] == K:
courses.append(near)
return courses
visited = set()
waiting = deque()
courses = bfs(X, visited, waiting)
if len(courses) == 0:
print(-1)
else:
for course in courses:
print(course)
# '최단 거리'가 정확히 K인 모든 도시들의 번호 출력
# 다익스트라로도, bfs로도 된다고 함그제 풀던 코드가 있어 살짝 고쳐서 냈는데 메모리 초과.
pypy문제인가 싶어서 python3로 바꿔봤는데 시간 초과.
안 쓰던 visited가 있어서 삭제했는데 또 메모리 초과.
graph_min을 굳이 배열로 관리할 필요가 없을 것 같다.
graph_min을 set로 바꾼 후 처음 만났을 때 graph_min에 넣는,
최단 거리가 된 그 순간에만 depth가 K인지 확인하면 될듯.
import sys
input = sys.stdin.readline
N, M, K, X = map(int, input().split())
# graph = {i: [] for i in range(1,N+1)}
graph = [[] for i in range(N+1)]
graph_min = set()
for _ in range(M):
A, B = map(int, input().split())
graph[A].append(B)
from collections import deque
def bfs(node, waiting):
waiting.append(node)
courses = []
depth = 0
graph_min.add(node)
while len(waiting) != 0:
qSize = len(waiting)
depth += 1
for _ in range(qSize):
node = waiting.pop()
for near in graph[node]:
waiting.append(near)
# 최단거리 갱신 및 조건 파악
if near not in graph_min:
graph_min.add(near)
if depth == K:
courses.append(near)
return courses
waiting = deque()
courses = bfs(X, waiting)
if len(courses) == 0:
print(-1)
else:
for course in courses:
print(course)graph_min을 set로 바꾸고 필요할 때만 가져오려고 했는데 또 메모리 초과.
import sys
input = sys.stdin.readline
# bfs 한 뒤에 depth가 k인 도시들을 출력한다
# visited 필요 없을듯?
# 최솟값을 담는 배열을 하나 만들면 될듯
N, M, K, X = map(int, input().split())
# graph = {i: [] for i in range(1,N+1)}
graph = [[] for i in range(N+1)]
for _ in range(M):
A, B = map(int, input().split())
graph[A].append(B)
from collections import deque
def bfs(node, waiting):
visited = [-1]*(N+1)
waiting.append(node)
visited[node] = 0
depth = 0
while len(waiting) != 0:
qSize = len(waiting)
depth += 1
for _ in range(qSize):
node = waiting.popleft()
for near in graph[node]:
# 최단거리 갱신 및 조건 파악
if visited[near] == -1:
waiting.append(near)
visited[near] = 0
if depth == K:
return waiting
return waiting
waiting = deque()
courses = list(bfs(X, waiting))
if len(courses) == 0:
print(-1)
else:
courses.sort()
for course in courses:
print(course)↑ 정답 코드
여러 가지 바꾸면서 최적화했는데 아무리 해도 안됨.
알고보니 return을 depth == K일때만 반환하는 걸로 해놔서 그랬음.
무조건 depth == K인 상황이 발생할거라고 생각했는데 아니었나봄.
그래프가 쪼개져 있거나 하면 안될 것으로 생각됨.
return을 생략하는 것에 확신을 가지면 안되겠다는 교훈을 얻음.
기본은 지키라고 있는거구나.
옆자리 동기가 안 도와줬으면 절대 못 풀었음.
정글에 와서 다행이다.
📌 1916 최소비용 구하기
import sys
import heapq
input = sys.stdin.readline
def dijkstra(start):
distances = [float('inf')] * (N+1)
distances[start] = 0
pq = [(0,start)]
while pq:
# 현재 거리, 현재 노드를 우선순위 큐에서 꺼낸다
current_distance, current_node = heapq.heappop(pq)
# 현재 경로 비용이 현재 노드에서의 최소 비용보다 작으면 넘기기
if distances[current_node] < current_distance:
continue
# 인접 노드와 가중치를 graph에서 꺼낸다
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
N, M, K, X = 4, 4, 2, 1 # Example test case
graph = [[] for _ in range(N+1)]
# Example edges
edges = [
(1, 2),
(1, 3),
(2, 3),
(2, 4)
]
for A, B in edges:
graph[A].append((B, 1))
distances = dijkstra(X)
result = [i for i in range(1, N+1) if distances[i] == K]
if result:
result.sort()
for city in result:
print(city)
else:
print(-1)다익스트라로 풀어야 되는 것 같아서 다익스트라 구현을 먼저 연습해봤다.
import sys
input = sys.stdin.readline
# 입력 받기
N = int(input())
M = int(input())
distance = {i : [] for i in range(1,N+1)}
for _ in range(M):
start, end, weight = map(int, input().split())
distance[start].append((end,weight))
start, end = map(int, input().split())
import heapq
def dijkstra(start, end):
costs = [float('inf')] * N
distance[start] = 0
pq = [(start,0)]
while pq:
cur_city, cur_cost = heapq.heappop(pq)
if costs[cur_city] > cur_cost:
return
dijkstra(start, end)풀어보려고 다익스트라 답지 슬쩍슬쩍 보면서 적어내려갔는데 막상 쓴거 아무것도 없음 뼈대도 제대로 못 만듬. 어차피 내일 끝이니까 정글 과정 다 끝나면 해야할듯.
