지식을 나누는 공간

문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 코드 import java.util.*; import java.io.*; public class b1753 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Str..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 import java.util.*; class Solution { public int solution(int n, int s, int a, int b, int[][] fares) { // INF+INF의 합이 Integer 범위 안넘게 조심 int INF=1000000000; int[][] map=new int[n+1][n+1]; for(int i=1; i

문제 https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1. intensity가 최소가 되도록 A->B 경로를 찾았다면, B->A로 돌아올 때도 똑같은 길을 그대로 되돌아오면 intensity가 최소가 된다. 따라서 출입구->산봉우리 까지의 최소 intensity만 찾아도 문제를 해결할 수 있다. 2. 등산코스에서 출입구와 산봉우리는 한번씩만 포함되어야 하므로 출입구에 연결된 양방향 등산로 -> 출입구에서 다른 지점으로만 이동 가능한 단방..

문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 코드 import heapq import sys INF=sys.maxsize def dijk(start): dis = [INF] * (n+1) q=[] heapq.heappush(q,(0,start)) dis[start]=0 while q: cost,node=heapq.heappop(q) if cost>dis[node]: continue for i in graph[node]: new_c..

문제 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 코드 import sys input=sys.stdin.readline INF=sys.maxsize n,m,r=map(int, input().split()) item=list(map(int, input().split())) graph=[[INF]*(n+1) for _ in range(n+1)] for i in range(n+1): for j in range(n+1): if i==j: graph[i]..

문제 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 코드 import heapq import sys INF=sys.maxsize input=sys.stdin.readline def dijk(start): dis = [INF] * (v + 1) q=[] heapq.heappush(q,(0,start)) while q: cost,node=heapq.heappop(q) if cost>dis[node]: contin..

문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 코드 import heapq import sys input=sys.stdin.readline INF=sys.maxsize def dijk(start): dis = [INF] * (n + 1) q=[] heapq.heappush(q,(0,start)) dis[start]=0 while q: cost,node=heapq.heappop(q) if dis..

문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 코드 import sys input=sys.stdin.readline INF=sys.maxsize def bf(start): distance[start]=0 for i in range(1,n+1): for j in range(m): node=array[j][0] next=array[j][1] cost=array[j][2] if di..

벨먼-포드 최단경로 알고리즘 : 음수 간선이 포함된 경우에서 한 노드에서 다른 노드로 가는 각각의 최단경로 구하기 특징 가중치가 음수여도 계산 가능 다익스트라의 가중치는 양수여야함 음수 간선의 순환 또한 감지 가능 시간복잡도 : O(VE) → V는 노드의 개수, E는 간선의 개수 음수 간선의 최단 경로 모든 간선이 양수인 경우 음수 간선이 있는 경우 2.1 음수 간선의 순환이 없는 경우 2.2 음수 간선의 순환이 있는 경우 2->3, 2->5 등의 경우 -> 최단 거리가 음의 무한이 될 수 있음 동작 원리 출발 노드 설정, 최단 거리 테이블 무한으로 초기화 N-1번 아래 과정 반복 2.1 전체 간선 E개 확인 2.2 각 간선을 거쳐 다른 노드로 가는 비용 계산 -> 최단 거리 테이블 갱신 N번째 반복했을..

문제 종강을 맞은 민준이는 고향인 마산으로 내려갈 계획을 짜고 있었다. 늘 그랬듯, 마산으로 갈 버스를 예약하려던 순간 민준이는 집으로 가는 다른 방법이 떠올랐다. 그것은 직접 지도를 보고 고향으로 가는 가장 짧은 길을 찾는 것이다. 그때, 먼저 고향으로 내려갔던 친구인 건우에게 연락이 왔다. 건우는 고향으로 내려가던 중 알 수 없는 일에 휘말려 외딴곳에 혼자 남겨지게 되었다. 건우는 유일한 구세주인 민준이에게 도움을 청한 것이었다. 그러나 마산의 남자인 민준이에게는 마산이 먼저였다. 민준이는 처량한 건우를 무시한 채 고향으로 떠나려고 했지만, 만약 고향으로 가는 길에 건우가 있다면 겸사겸사 도움을 줄 수 있을 것 같았다. 지도는 양방향 그래프 형태로 되어있다. 출발지는 1번 정점 마산은 V번 정점이다...