Algorithm/Graph188 [파이썬] 백준 프로그래머스 : 합승 택시 요금 (Lv3) [파이썬] 백준 프로그래머스 : 합승 택시 요금 (Lv3) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 0. 방향성 생각 다익스트라, 플로이드 워셜 둘 다 가능한데 플로이드 워셜 구현 안해봐서 다익스트라로 풀이 시간복잡도도 다익스트라가 나아서 효율성 점수도 있겠다 다익스트라로 풀이. 1. 입력 import heapq as hq def solution(n,s,a,b,info): graph = {i: {} for i in range(1,n+1)} for n1,n2,cost in info: graph[n1][n2] = cost graph[n2][n1] .. 2023. 8. 16. [파이썬] 백준 1504 : 특정한 최단 경로(골드4) [파이썬] 백준 1504 : 특정한 최단 경로(골드4) 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 풀이 0. 방향성 생각 간선 정보가 주어진 그래프가 주어지고 최소비용으로 목적지에 도달해야한다. 다익스트라 활용해서 풀이 1. 입력 import heapq as hq import sys input = lambda : sys.stdin.readline().rstrip() n,e = map(int,input().split()) graph = {i: {} for .. 2023. 8. 16. [파이썬] 백준 2481 : 해밍 경로 (골드2) [파이썬] 백준 2481 : 해밍 경로 (골드2) 2481번: 해밍 경로 길이가 같은 두 개의 이진수 코드 w1과 w2가 있다고 하자. 이 두 코드 사이의 해밍 거리(Hamming distance)는 w1과 w2의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 www.acmicpc.net 문제 풀이 0. 방향성 생각 입력 개수가 최대 10^6, 해밍거리가 1인 노드끼리만 연결해주면 된다. 노드가 최대 10^6인거부터 2개씩 짝지어서 하는 방법은 불가능. 최대 5 * 10^11이므로 불가능하다. 코드인덱스 매칭을 통해서 딕셔너리를 사용한다는 점까지는 생각할 수 있다. 그 이후에는 1. 입력 from collections import deque import sys input .. 2023. 8. 12. [파이썬] 백준 17244 : 아맞다우산 (골드2) [파이썬] 백준 17244 : 아맞다우산 (골드2) 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 문제 풀이 0. 방향성 생각 기본적으로 DP에서 하던거처럼 상태를 나눈다. 물건의 개수가 늘어갈수록 상대가 2배로 늘어나니 bitmask를 통해서 간편하게 처리한다는게 아이디어 1. 입력 from collections import deque import sys input = lambda : sys.stdin.readline().rstrip() w,h = map(int,input().split()) arr .. 2023. 8. 9. 이전 1 ··· 36 37 38 39 40 41 42 ··· 47 다음
