728x90

목sssssss록플로이드와샬 (3)

개발조아

[BOJ/백준] 1719 택배 파이썬

문제 링크 : https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 문제에 모든 노드가 다 연결되어 있는지 만약 아니라면 그때의 출력은 어찌하는지가 없었다. 그래서 그냥 모든 노드가 연결되어 있다는 가정하에 문제를 풀었다. 나는 플로이드 와샬로 풀었다. 노드가 최대 200개 이므로 충분히 해결할 수 있다. 우선 인접 행렬로 구성했다. 배열[a][b] = [b,c] a->b로 가는 최단 경로중 b를 가장 먼저 들러야하고 비용은 c이다 는 의미이다. 처음 입력은..
알고리즘/백준 2021. 9. 17. 15:19
[프로그래머스] 합승 택시 요금 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr n이 200으로 작아서 플로이드 와샬로 풀었다. 풀이는 생각보다 너무..
알고리즘/프로그래머스 2021. 8. 24. 20:03
[프로그래머스] 순위 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 고민고민하다가 접근법을 모르겠어서 검색해본 문제이다. 접근방법은 플로이드와샬로 하면 됐었다. a가 b를 이겼다면 b는 항상 a 아래이고, b가 c를 이겼다면 c도 항상 b 아래이다 결국 c는 항상 a아래 이므로 a->b, b->c이면 a->c 인 것이므로 플로이드와샬로 접근이 가능하다. a와 b 관계에서 a가 c를 이기고 c가 b를 이기는 관계가 있으면 a가 b를 이긴것으로 체크하고 (b,a), (c,a), (b,c)는 모두 진것으로 체크하면 된다. 마지..
알고리즘/프로그래머스 2021. 8. 13. 16:29
Prev 1 Next
728x90