7:55 입실
밤에 어제 모기 한테 4~5방 물리고 시끄러워서 새벽에 깨서 잠을 설쳤다.
그래서 오늘 아침 7시 30분에 울리던 알람을 5분 늦추는 사치를 부려봄.
(너무 피곤해서 점심시간에 기숙사 가서 1시간 잠ㅠ)
손이 매우 가렵지만, 가려움을 느낄 수 있음에 감사하기로 함.
오늘은 무한 문제 풀이 + csapp 2장 읽어보기
2665 미로만들기
혼자 못 풀었음. 대략적인 흐름만 구현했는데 정확히 구현은 실패
import sys
from collections import deque
N = int(sys.stdin.readline().strip())
maze = []
for _ in range(N):
maze.append(list(map(int, sys.stdin.readline().strip())))
def bfs(N, maze):
# 상, 하, 좌, 우
xd = (-1, 1, 0, 0)
yd = (0, 0, -1, 1)
distance = [[float("inf")] * N for _ in range(N)]
distance[0][0] = 0 # 시작방의 거리는 0
queue = deque()
queue.append((0, 0))
while queue:
current_x, current_y = queue.popleft()
for i in range(4):
next_x = current_x + xd[i]
next_y = current_y + yd[i]
if 0 <= next_x < N and 0 <= next_y < N:
if maze[next_x][next_y] == 1:
weight = 0
else:
weight = 1
if distance[next_x][next_y] > distance[current_x][current_y] + weight:
distance[next_x][next_y] = distance[current_x][current_y] + weight
queue.append((next_x, next_y))
return distance[N - 1][N - 1]
print(bfs(N, maze))
백준 2637 장난감 조립
??? 이것도 전혀 감도 못 잡고 인터넷 찾아봐도 풀이가 다 마음에 안 들어서
오후 내내 고민함.
근데 갑자기 머리가 번쩍하더니 코드가 술술술 써졌다!!!!!
예제 테스트는 통과했으나 시간 초과..
시간 초과
import sys
from collections import defaultdict, deque
N = int(sys.stdin.readline().strip())
M = int(sys.stdin.readline().strip())
edges = []
for _ in range(M):
x, y, k = map(int, sys.stdin.readline().strip().split())
edges.append((x, y, k))
edges.sort(reverse=True)
def topology_sort(N, edges):
queue = deque()
result = defaultdict(int)
indegree = [0] * (N + 1)
tree = defaultdict(list)
for edge in edges:
x, y, k = edge
for _ in range(k):
tree[x].append(y)
indegree[x] += 1
middle_parts = []
for i, d in enumerate(indegree):
if d != 0:
middle_parts.append(i)
queue.append(N)
while queue:
current_node = queue.pop()
if current_node not in middle_parts:
result[current_node] += 1
else:
for adj_node in tree[current_node]:
queue.append(adj_node)
return result
result = topology_sort(N, edges)
for k, v in result.items():
print(k, v)
개선 코드(GPT)
import sys
from collections import defaultdict, deque
N = int(sys.stdin.readline().strip())
M = int(sys.stdin.readline().strip())
edges = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
tree = defaultdict(list)
indegree = [0] * (N + 1)
result = [0] * (N + 1)
for x, y, k in edges:
tree[x].append((y, k))
indegree[y] += 1
queue = deque()
queue.append(N)
result[N] = 1
while queue:
current = queue.popleft()
for next_node, k in tree[current]:
result[next_node] += result[current] * k
indegree[next_node] -= 1
if indegree[next_node] == 0:
queue.append(next_node)
for i in range(1, N + 1):
if not tree[i] and result[i]:
print(i, result[i])
시간 초과 원인은 트리 만드는데 반복이 너무 많이 들어감.
그냥(3번 노드, 5개)하면 되는데[3, 3, 3, 3, 3]이렇게 짬
그래서 시간 복잡도가 급격하게 증가함.
불필요하게 반복문 돌려서 자료 구조 짜는 게 아니라
배열로 할 수 있는지 생각해보자.
요소를 삭제하는 것이 아니라면 배열은 조회, 수정 시간복잡도가 O(1)
백준 21606 아침 산책
인터넷에 떠도는 답지 베끼고 싶지 않아서 5시간 정도 구현함!
5시간이나 소모했지만 절대 헛수고는 아님!
GPT 도움 받기는 했지만 기본적인 흐름은 스스로 생각함!
DFS를 정석대로 적용해서 잘 해결한 풀이법 같음!
풀이 과정 정확히 이해했음!
200점 만점은 아니지만.. DFS로 풀었다는데 의의
108점으로 마무리! 짜릿하다..
import sys
from collections import defaultdict
N = int(sys.stdin.readline().strip())
node_info = [0] + [int(char) for char in sys.stdin.readline().strip()]
edges = []
for _ in range(N - 1):
u, v = map(int, sys.stdin.readline().strip().split())
edges.append((u, v))
tree = defaultdict(list)
for edge in edges:
u, v = edge
tree[u].append(v)
tree[v].append(u)
def dfs(tree, start_node, node_info):
visited = set()
if node_info[start_node] == 0:
return 0
paths = 0
stack = []
visited.add(start_node)
for adj_node in tree[start_node]:
stack.append(adj_node)
while stack:
current_node = stack.pop()
if current_node not in visited:
visited.add(current_node)
if node_info[current_node] == 1:
paths += 1
continue
for adj_node in tree[current_node]:
stack.append(adj_node)
return paths
result = 0
for key in tree.keys():
result += dfs(tree, key, node_info)
print(result)오류 복기
print() 리턴값을result += print()하려고 해서 틀림.
print()는None을 반환함.!
백준 1446 지름길
다익스트라 실버 1이길래 도전해봤는데 감도 못 잡음.
주어진 노드 만을 간선으로 생각해서 감을 못 잡았음.
이 문제는 1km 단위가 하나의 노드라고 생각하고 풀면 됨.
이건 DP 문제라고 보는 게 더 적절?
이 문제는 절대 못 풀었을 듯..
N, D = map(int, input().split())
shortcuts = [tuple(map(int, input().split())) for _ in range(N)]
# 현재 노드까지 거리 정보 초기화
distances = [i for i in range(D + 1)]
# 1km마다 고속도로 갈 때를 기본으로 잡고, 1km씩 증가하며 도착점까지 진행
for i in range(1, D + 1):
# 직전 노드(1km 전)에서 1 더한 것과 초기값을 비교해서 더 작은 값으로 업데이트
distances[i] = min(distances[i], distances[i - 1] + 1)
for start, end, distance in shortcuts:
# 만약 현재 도착점에 해당하는 지름길이 있다면
if i == end:
# 현재 위치 i에 도달할 수 있는 최소 주행 거리
distances[i] = min(distances[i], distances[start] + distance)
print(distances[D])
공부한 게 많지 않아 보이는 하루
그래도 치열했다..
알고리즘 고민하는데 시간을 많이 씀
