본문 바로가기
728x90
반응형

알고리즘109

[백준] 13913번: 숨바꼭질 4 - python https://www.acmicpc.net/problem/13913 시험과 플젝 끝난 후 간만에 알고리즘 풀이 BFS이므로 ch 리스트를 체크하는 용도 말고 dis를 넣어서 체크해도 문제가 되지 않는다.그 후 여기선 최단으로 바뀌는 경로의 값을 전부 다 넣어서 출력해줘야되기에 dis안에 전에 now를 넣어서 저장시켜준다.그 후 만약 n == k 가 되면 dis를 돌아서 answer안에 투입 후 출력해준다. from collections import dequen, k = map(int, input().split())ch = [0] * (100001)dis = [0] * (100001)ch[n] = 0dis[n] = 0dq = deque([n])while dq: now = dq.popleft() .. 2024. 5. 6.
[백준] 14501번: 퇴사 - python https://www.acmicpc.net/problem/14501 14501번: 퇴사첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.www.acmicpc.net 배울게 참 많은 문제 첫번째 아이디어DFS를 이용하여 상태트리를 생성하여 계산하는 방식과N = int(input())def DFS(L, sum): global res if L == N+1: if res   두번째는 DP를 이용하여 최대값을 계속 저장해나가는 방식이다. n = int(input())schedule = []dp = [0] * (n+1)for i in range(1,n+1): a, b = map(int, input().split()) schedule.append([a,b])for i in ra.. 2024. 5. 6.
[백준] 5639번: 이진 검색 트리 - python https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 아이디어 순회와 같은 문제는 DFS로 풀어야겠다고 생각. 입력을 받은 다음 만약 루트, 루트보다 클 경우, 그 중간 이 3개로 분리해서 나누어 재귀함수로 돌리면 해결이 된다. 만약 전위, 중위로 하고 싶으면 print의 위치를 위, 중간 으로 변경하면 가능한 것을 확인 할 수 있다. import sys sys.setrecursionlimit(10**9) arr = [] while Tr.. 2024. 4. 12.
[백준] 12851번: 숨바꼭질2 - python https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 아이디어 체크할 필요가 없으니 체크리스트를 제거한 뒤에 거리가 같을 경우 cnt 값을 증가시키며 답을 출력 from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) ch = [0] * 100001 dis = [0] * 100001 cnt .. 2024. 4. 12.
728x90
반응형

티스토리툴바