아어제 글 쓰고 링크 첨부를 안했나벼..ㅎㅎ 아까버라
백준 24479번: 알고리즘 수업 - 깊이 우선 탐색 1
- DFS, 무방향 그래프
- 시행착오
- 이차원 배열 - 메모리 초과
- 조건이 있길래
g[u]=[v]만 담고 반대의 경우v in g[u]를 검사하였으나 시간 초과 - 런타임에러 (recursion error): 백준에서 파이썬 recursion limit이 1000이라 일어난다고 한다.
sys.setrecursionlimit()을 조절해서 해결할 수 있지만 굳이 sys 변수 건들고 싶지 않아서 스택 사용 - 시간초과 나서 결국
input = sys.stdin.readline으로 대체했는데, 시간복잡도를 줄여야 했던 것은 아닐까? 그게 아니라면 백준은 언어 별로 시간 제한을 다르게 줘야 하는 거 아닌가?
- 풀이 방법
- stack에 방문해야할 노드를 push하고 마지막 방문 노드를 pop한다
- 인접 정점을 오름차순으로 방문해야 하기 때문에 push를 내림차순으로 한다 (LIFO)
import sys
input = sys.stdin.readline # ㅠㅠ 맘에안듬
n, m, r = list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
for i in range(m):
u, v = list(map(int, input().split()))
g[u].append(v)
g[v].append(u)
visited = [0] * (n + 1)
order = 1
stack = [r]
while stack:
r = stack.pop()
if visited[r]:
continue
visited[r] = order
order += 1
stack.extend([i for i in sorted(g[r], reverse=True)])
for i in visited[1:]:
print(i)목요일이라 보너스 문제도 있다
백준 2512번: 예산
사흘 동안 이분탐색 문제를 풀었더니 범위를 구한다 -> 이분탐색으로 풀어야 한다는 감이 옴
while start ? end:
if money ? m:
start = mid + 1
else:
end = mid - 1? mid?
print(?)이 부분들을 자꾸 헷갈려하던 참이었는데
곰곰히 생각하니까 최댓값을 구해야하니까 end가 답이고
예산이 딱 맞을 때는 그 mid가 답인 것을 바탕으로 이렇게 짰다
n = int(input())
region = list(map(int, input().split()))
m = int(input())
if sum(region) <= m:
print(max(region))
else:
start = 0
end = max(region)
while start <= end:
money = 0
mid = (start + end) // 2
for i in region:
money += i if i <= mid else mid
if money < m:
start = mid + 1
elif money == m:
end = mid # 함수가 아니라 return 대신 end에 mid 대입
break
else:
end = mid - 1
print(end)같은 유형을 여러 번 풀면 확실히 손에 붙는 게 느껴진다!
그런데 정확히 개념을 찾아본 게 아니라 대애충 감으로 풀다 보니 헷갈리는 부분은 담에도 또 헷갈리는 것 같다
음음