풀이29 [C/C++] 백준 11404: 플로이드 (플로이드-워셜 알고리즘) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘? 알고리즘 제목에서도 알 수 있다싶이 이 문제는 한 도시에서 다른 도시까지 필요한 비용의 최솟값을 구하는 알고리즘 문제이기 때문에 그래프에서 한 지점에서 다른 지점까지의 최솟값을 구하는 알고리즘인 플로이드-워셜 알고리즘을 사용하면 된다. 특징으로는 다익스트라 알고리즘에 비해 구현이 쉽고 삼중 반복문을 사용하기 때문에 O(V^3)의 시간 복잡도를 갖는다. 삼중 반복문을 돌때 .. 2023. 9. 11. [C++] Map 기본 사용법! (BOJ 17219: 비밀번호 찾기) https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 이 문제는 C++의 map을 사용하면 쉽게 풀 수 있다! 그 전에 map에 대해 간단히 짚고 넘어가겠다! Map이란? map은 각 노드가 key와 value가 쌍을 이루고 있는 트리로 pair 객체로 저장되기 때문에 first-key로 second-value를 저장한다. 중복을 허락하지 않으며 기본 형태는 map m; 으로 key를 통해 value를 찾기 용이하게 되.. 2023. 9. 6. [C/C++] 백준 11286: 절댓값 힙 (구조체와 연산자 오버로딩) https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 절댓값 힙 문제는 최소 힙 문제를 조금 변형시켜면 쉽게 풀 수 있다. 최소 힙 문제에서 priority_queue를 정의할 때 priority_queue queue;를 사용해야 했다면 이 문제에서는 절댓값이 작은 순으로 heap을 정렬시켜야하므로 세번째 자리에 greater 가 아닌 priority_queue queue;와 같은 새로 정의한 구조체를 넣어줘야한다. 참고로 pr.. 2023. 9. 5. [C/C++] 백준 1931: 회의실 배정 (풀이) https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이 문제는 Greedy 알고리즘 중에서 제일 유명한 문제라고 할 수 있다. 한개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의 중에 회의실을 사용할 수 있는 회의의 최대 개수를 구하면 된다. 결론부터 말하자면 끝나는 시간이 제일 빠른 회의부터 차례대로 진행할 때 회의의 개수가 최대가 된다. 각 경우마다 가장 이득이 되는 선택을 하면 되는데 그 각각의 선택이 전체적으로도 가장 이득이 되는 대표적인 예이다. 구현은 끝나는 시간 순서대로 오름차순으로 정렬을 한다. 이때 한가지 주의해야할 점은 회의의 시작시간과 끝.. 2023. 9. 5. 이전 1 ··· 4 5 6 7 8 다음
