algorithm8 [BOJ] 백준 11660 - 구간 합 구하기 5 문제 링크 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net (x1,y1)부터 (x2,y2) (x1 n >> m; for (int i = 1; i a[i][j]; } } for (int i = 1; i = 1) { total[i][j] += total[i][j - 1]; } if (i - 1 >= 1 && j - 1 >= 1) { total[i][j] -= total[i - 1][j - 1]; } } } while (m--) { int x1, y1, x2, y2; cin.. 2021. 8. 11. [BOJ] 백준 11404 - 플로이드 2021.08.09 - [Algorithm/Theory] - [Algorithm] Floyd-Warshall Algorithm(플로이드-와샬 알고리즘) 문제 링크 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 도시(정점), 버스(간선), 버스의 비용(가중치)를 갖는 그래프에서, 모든 도시(정점) 의 쌍 (A,B)에 대해 A에서 B로 가는데 필요한 최소 비용을 구하는 문제이다. 문제의 제목과 같이 Floyd-Warshall 알고리즘으로 해결 할 수 있었다. 해당 알고리즘은 아래 링크에서 확인할 수 있다. 202.. 2021. 8. 9. [Algorithm] Floyd-Warshall Algorithm(플로이드-와샬 알고리즘) Floyd-Warshall 알고리즘은 기존에 포스팅했던 Dijkstra 알고리즘이나 Bellman-Ford 알고리즘과 다르게, 모든 정점들 사이의 최단거리를 계산하는 알고리즘이다. 그래프의 초기 상태는 다음과 같다. 두 정점사이의 거리를 나타내는 dist 배열을 나타내보자. dist[i][j]는 정점 i에서 정점 j까지의 거리이다. dist 배열의 초기값은 i==j일때는 0으로, 정점 i와 정점 j가 연결되어있다면 두 정점을 잇는 간선의 가중치로, 두 정점이 연결되어있지 않다면 적당히 큰 수인 INF로 설정했다. 초기 dist배열의 모습은 아래와 같다. Floyd-Warshall 알고리즘의 핵심은 정점 k(14) dist[5][4]=min(dist[5][4],dist[5][2]+dist[2][4])=mi.. 2021. 8. 9. [BOJ] 백준 1865 - 웜홀 문제 링크 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 지점(정점), 도로(무방향 간선), 웜홀(음의 가중치를 갖는 유방향 간선)으로 이루어진 그래프에서 출발을 하였을때보다 시간이 되돌아가 있는 경우(음의 사이클)가 존재하는지 찾는 문제이다. Bellman-Ford 알고리즘으로 해결할 수 있었다. 해당 알고리즘은 아래 링크에서 확인 할 수 있다. 2021.04.06 - [Algorithm/Theory] - [Algorithm] Bellman-Ford Algorithm (벨만-포드 알고리즘) [.. 2021. 4. 6. [Algorithm] Bellman-Ford Algorithm (벨만-포드 알고리즘) Bellman-Ford 알고리즘은 Dijkstra 알고리즘과 마찬가지로 단일 정점에서 각 정점까지의 최단거리를 구하는 알고리즘이다. 시작점은 1번 정점이다. dist배열은 시작점으로부터의 거리를 나타내고 INF로 초기화 되어있다. 초기상태는 아래와 같으며 그래프의 구현은 인접 행렬(Adjacency Matrix) W로 되어있다. 시작점이 1번 정점이기 때문에 dist[1]을 0으로 갱신한다. 한 정점과 인접한 정점을 중심으로 갱신을 이어나간 Dijkstra 알고리즘과는 달리 Bellman-Ford 알고리즘은 매 수행마다 모든 간선(edge)에 대해 갱신을 진행한다. 한 간선이 정점 i에서 정점 j로 이어진다고 할 때, 다음 연산을 통해 갱신이 진행된다. dist[j]=min(dist[j],dist[i]+.. 2021. 4. 6. [BOJ] 백준 1753 - 최단경로 문제 링크 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 방향 그래프의 한 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 문제이다. 해당 문제는 Dijkstra 알고리즘을 사용하여 풀이했다. Dijkstra 알고리즘에 대한 설명은 아래 링크에서 확인할 수 있다. 2021.04.06 - [Algorithm/Theory] - [Algorithm] Dijkstra Algorithm (다익스트라 알고리즘) [Algorithm] Dijkstra Algorithm (다익스트라 알고리즘).. 2021. 4. 6. 이전 1 2 다음
