본문 바로가기

Algorithm475

[파이썬] 백준 1916 : 최소비용 구하기 (골드5) [파이썬] 백준 1916 : 최소비용 구하기 (골드5)https://www.acmicpc.net/problem/1916풀이방향성 생각전형적인 다익 기본A -> B로가는 최소 거리전체코드import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()N = int(input())M = int(input())G = [[] for _ in range(N+1)]for _ in range(M): a,b,cost = map(int,input().split()) G[a].append((b,cost))start,end = map(int,input().split())V = [float('inf')]*(N+1)V[start] = 0heap = .. 2024. 11. 21.
[파이썬] 백준 10251 : 운전 면허 시험 (플레5) [파이썬] 백준 10251 : 운전 면허 시험 (플레5)https://www.acmicpc.net/problem/10251풀이방향성 생각상태 공간 나누기x좌표, y좌표, x,y에 들어오는 진입 방향, 누적 회전 수상태공간 나누는 기준이 G가 아닌건, G 범위가 너무 크다.G 공간을 리스트로 나누거나 딕셔너리로 나눠도 메모제이션이 되지 않을 가능성이 매우 높아서 BFS랑 다를바가 없다.전체코드import sysinput = lambda : sys.stdin.readline().rstrip()T = int(input())for _ in range(T): H,W,L,G = map(int, input().split()) # 가로이동 : hor[i][j] (j,i)에서 (j+1,i)로 이동 hor.. 2024. 11. 19.
[파이썬] 백준 1753 : 최단경로 (골드4) [파이썬] 백준 1753 : 최단경로 (골드4)https://www.acmicpc.net/problem/1753풀이방향성 생각방향 그래프의 node A에서 다른 노드까지의 거리를 구하는 문제입력 크기를 보면 node = 20000에 edges = 300000이라 다익스트라로 풀이.주의할점은 node간 중복 간선이 주어져서 처리를 해야한다.defaultdict로 이중 딕셔너리 만들어서 최솟값으로 갱신하는 방식으로 풀이전체코드from collections import defaultdict as ddimport heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()N,K = map(int,input().split())start = int(in.. 2024. 11. 18.
[파이썬] 백준 1644 : 소수의 연속합 (골드3) [파이썬] 백준 1644 : 소수의 연속합 (골드3)https://www.acmicpc.net/problem/1644풀이방향성 생각N=4백만이라, 에라스토테네스로 소수 리스트 한 번 빠르게 만든 다음 투포인터 사용연속된 소수의 합으로 다른 자연수를 만드는거라 투포인터임을 바로 알 수 있다.전체코드def prime(n): is_prime = [True]*(n+1) is_prime[:2] = [False]*2 for i in range(2,int(n**0.5)+1): if is_prime[i]: for j in range(i**2,n+1,i): is_prime[j] = False primes = [i for i, prime in.. 2024. 11. 16.

티스토리툴바