[정렬] 난이도1, 국제 알고리즘 대회 '두 배열의 원소 교체' (Python)
동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K 번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 한다. N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하라. 예를 들어 N = 5, K = 3이고, 배열 A와 B가 다음과 같다고 해보자 배열 A = [1, 2, 5, 4, 3] 배열..
[BFS, Dijkstra] 백준 18352번 '특정 거리의 도시 찾기' (Python)
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 이 문제는 BFS 또는 다익스트라 알고리즘으로 풀 수 있다. BFS로 푸는 법은 다음에 기록할 예정이다. 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하므로 다익스트라 알고리즘 사용 M 개수가 1,000,000 이하이므로 input() 보다 빠른 sys.stdin.readline 라이브러리 사용 비용을 구하는 것이 ..