알고리즘!76 [C/C++] 백준 11660 구간 합 구하기 5 (이차원 구간 합) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 방법? 가장 먼저 드는 생각은 합을 구해야하는 횟수마다 저장되어 있는 2차원 배열에서 이중 for문을 통해 구간 합을 각각 구하는 방법인데 이 방법으로 할 경우 최악의 경우에는 100,000*1024*1024 의 경우를 모두 확인해야하므로 시간 초과가 발생한다. 그렇기 때문에 여기서 제목에 있는 힌트를 빌려 풀이 방법을 생각해보자면 현재 있는 위치까.. 2023. 9. 15. [C/C++] 백준 1916: 최소비용 구하기 (다익스트라 구현하기!) https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 이번에 드디어 다익스트라 알고리즘을 배워서 실제 문제 풀이에 적용하였다. 알고리즘 문제해결 전략에 나와있는 것을 응용하여 해결했다. 1. 준비작업 1-1. vector adj_list[100001] 먼저 각 노드들의 인접리스트를 만들 이차원 백터 vector adj_list[100001]을 선언해주었다. 이 백터의 역할은 a번째 노드와 연결되어 있는 b번째 노드까.. 2023. 9. 13. [C/C++] 13549: 숨바꼭질 3 (BFS,Queue) https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 결론부터 말하자면 이 문제는 queue를 이용해 bfs로 풀 수 있는데 이때 2의 배수일 때는 0초만에 도달 가능하다는 것만 유의하면 된다. 구현?? 이를 구현하기 위해서 내가 사용했던 방법은 함수 after_onesec와 after_zero이다. after_onesec는 1초뒤에 갈 수 있는 곳을 queue에 넣는 방식으로 동작되는데 이때 queue.fron.. 2023. 9. 12. [C/C++] 백준 11404: 플로이드 (플로이드-워셜 알고리즘) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘? 알고리즘 제목에서도 알 수 있다싶이 이 문제는 한 도시에서 다른 도시까지 필요한 비용의 최솟값을 구하는 알고리즘 문제이기 때문에 그래프에서 한 지점에서 다른 지점까지의 최솟값을 구하는 알고리즘인 플로이드-워셜 알고리즘을 사용하면 된다. 특징으로는 다익스트라 알고리즘에 비해 구현이 쉽고 삼중 반복문을 사용하기 때문에 O(V^3)의 시간 복잡도를 갖는다. 삼중 반복문을 돌때 .. 2023. 9. 11. 이전 1 ··· 3 4 5 6 7 8 9 ··· 19 다음
