문제풀이/백준 썸네일형 리스트형 백준 10888번 두 섬간의 이동 https://www.acmicpc.net/problem/10888 10888번: 두 섬간의 이동 1에서 N까지 번호가 붙은 N개의 섬이 일렬로 쭉 늘어서 있다. 이 섬들 간에는 아직 다리가 없어서 배로만 이동을 해야 했기에 매우 불편했다. 그렇기에 정부에서는 이 섬들에 다리를 연결하고자 � www.acmicpc.net 무려 열두 번 틀린 문제입니다. 그렇다고 어려운 문제는 아닙니다.. 풀이 방법 임의의 A개의 섬이 A-1개의 다리를 통해 모두 연결되어 있다면, 이 A개의 섬에 대해 연결된 쌍의 개수와 최소 다리 개수의 합을 구할 수 있습니다. 1. 쌍의 개수 A×(A-1) / 2 = 쌍의 개수입니다. 2. 최소 다리 개수의 합 섬 A개가 모두 연결되어 있을 때, 다리 1개를 거쳐 연결되어 있는 쌍의 개.. 더보기 백준 2660번 회장 뽑기 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 각 회원을 정점으로, 친구사이를 가중치가 1인 간선으로 생각하면 회원의 점수는 그 회원과 가장 멀리 떨어진 정점과의 거리가 됩니다. 이를 구하려면 모든 회원 간의 관계 (모든 정점 사이의 거리) 를 알아야 하므로 플로이드-와샬 알고리즘을 적용하였습니다. 정점의 수가 N일 때 O(N^3)인 알고리즘이지만 회원의 수 (정점의 수) 가 최대 50이므로 사용할 수 있습니다. 코드 1234567891.. 더보기 백준 1655번 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 N개의 정수를 입력받아 1번째, 2번째, ... N번째 정수까지만 보았을 때 각각의 중앙값들을 출력하는 문제입니다. 풀이 단순히 배열을 사용하여 입력받을 때마다 배열을 정렬한다면 O(N^2)이므로 시간초과일 것입니다. 힙을 이용하여 O(NlogN)으로 해결할 수 있습니다. 지금까지 입력받은 수 중 절반의 작은 수들은 최대 힙에, 나머지 절반의 큰 수들은 최소 힙에 저장합니다... 더보기 이전 1 2 3 다음
