반응형 백준58 [백준 1414] 크루스칼 알고리즘(Kruskal , 최소신장트리) - 파이썬(Python) 불우이웃돕기 문제 다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다. 다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나, 또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다. 다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다. N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.. 2023. 1. 4. 파이썬(Python) 크루스칼 알고리즘(Kruskal) 개념과 예제 - 최소신장트리(MST) (백준 1197) 최소 신장 트리 : 최소 신장 트리는 모든 노드가 연결되도록 간선을 그은 트리의 가중치의 합이 가장 작은 것을 말합니다. 가중치의 값이 최소가 돼야되기 때문에 사이클은 없어야 합니다. 크루스칼 알고리즘 크루스칼 알고리즘은 최소 신장 부분 트리를 찾는 알고리즘으로 가중치가 가장 낮은 엣지를 순서대로 고르지만, 사이클이 안생기도록 고르는 알고리즘입니다.변의 개수를 E, 꼭짓점의 개수 V라고 하면 이 알고리즘은O(E\log V)의 시간복잡도를 가집니다. 1. 엣지리스트 초기화 하기엣지들을 가중치가 낮은것 순서대로 뽑을 것이므로 리스트에다가 넣고, 나중에 정렬해줍니다.2. 유니온 파인드 알고리즘 적용시키기유니온 파인드는 쉽게 말해서 집합을 구현하는 알고리즘입니다. 아래 코드를 보시면 겉핥기로 이해되실 것입니다 .. 2023. 1. 4. [백준 11780] 플로이드-워셜 알고리즘 - 파이썬(Python) 플로이드 2 문제 n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 .. 2022. 12. 31. 파이썬(Python) 플로이드-워셜(Floyd-Warshall) 개념과 예제 (백준 11404) 플로이드-워셜 알고리즘 ● 다익스트라( O(ElogV) ) vs 벨만-포드 ( O(EV) ) vs 플로이드-워셜 ( O(V^3) ) 다익스트라는 양수엣지에서 가장 빠르게 최단거리를 구하는 알고리즘이고, 벨만-포드는 음수엣지에서 최단거리를 구하는 알고리즘이라면, 플로이드는 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다. (플로이드-워셜 알고리즘은 음의 간선도 사용할 수 있습니다) 그러므로 한노드에서 출발하는 최단거리를 구하라고 하면 오래 걸리지만, 출발노드가 계속 달라지면서, 최단거리의 질의가 많아지면 빛을 발하는 알고리즘이라고 볼 수 있습니다. 동적계획법(DP)의 원리를 이용한 알고리즘으로 점화식은 아래와 같습니다. s에서 시작해서 e로 간다고 하겠습니다. s->k->e 방식으로 k를 경유.. 2022. 12. 31. [백준 1219] 벨만-포드 알고리즘 - 파이썬 Python 오민식의 고민 문제 오민식은 세일즈맨이다. 오민식의 회사 사장님은 오민식에게 물건을 최대한 많이 팔아서 최대 이윤을 남기라고 했다. 오민식은 고민에 빠졌다. 어떻게 하면 최대 이윤을 낼 수 있을까? 이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다. 오민식의 여행은 A도시에서 시작해서 B도시에서 끝난다. 오민식이 이용할 수 있는 교통수단은 여러 가지가 있다. 오민식은 모든 교통수단의 출발 도시와 도착 도시를 알고 있고, 비용도 알고 있다. 게다가, 오민식은 각각의 도시를 방문할 때마다 벌 수 있는 돈을 알고있다. 이 값은 도시마다 다르며, 액수는 고정되어있다. 또, 도시를 방문할 때마다 그 돈을 벌게 된다. 오민식은 도착 도시에 도착할 때, 가지고 있는 돈의 액수를 최대로 .. 2022. 12. 31. 파이썬 (Python) - 벨만-포드(Bellman-Ford) 개념과 예제 (백준 11657) 벨만 포드 알고리즘 많이 알려져있는 다익스트라가 (시간 복잡도 O(ElogV)) 최단거리 구하는 알고리즘이라면, 벨만-포드 알고리즘(시간 복잡도 O(VE))은 다익스트라 보단 조금 느리지만, 음수엣지가 있어도 수행할수 있는 알고리즘입니다. 음수 엣지가 있는 그래프 탐색에선 '음수 사이클'이 생기는데, 그 음수 사이클을 판별하는 용도로도 쓸수 있습니다. 음수 사이클 같은 경우는 위 그래프의 2,4,5 노드의 사이클이라고 보시면 됩니다. 한 바퀴 돌때마다 -1씩 감소하므로, 최단거리가 음의 무한대로 발산할 수 있기 때문에 이 경우는 최단거리가 없는 경우입니다. 음의 엣지가 있는 그래프에서는 최단 거리를 구할 땐 음수 사이클이 없는지 확인하고 출력해야합니다 1. 등록된 모든 엣지를 가지고 엣지리스트와 각 노드.. 2022. 12. 31. [백준 9084] 냅색 알고리즘(DP) - 파이썬 Python 동전 성공 문제 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. 입력 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 .. 2022. 12. 30. 이전 1 2 3 4 5 6 ··· 9 다음
