쾌락없는 책임 (공부)
-
길찾기 알고리즘(3) - 벨만-포드 알고리즘쾌락없는 책임 (공부)/알고리즘 공부 2021. 6. 23. 22:30
벨만-포드 알고리즘 벨만 포드 알고리즘은 이전에 작성한 다익스트라 알고리즘, 플로이드-와샬 알고리즘과 더불어 자주 소개되는 길찾기 알고리즘입니다. 저 두개의 알고리즘보다 아주 뛰어난 성능을 가지는 알고리즘은 아니지만 아래 표와 같이 특징에 따라 분류된 알고리즘이라고 볼 수 있습니다. 다익스트라 플로이드-와샬 벨만-포드 빠르다 한 노드에서 다른 노드들 까지 거리를 구함 음의 가중치가 있으면 도달 불가 느리다 모든 노드 to 모든 노드의 거리를 구함 사건의 전후관계 파악에도 사용 다익스트라보다 느리다 음의 가중치가 있을때 사이클을 판단 벨만-포드 알고리즘을 배우는 큰 이유는 '음의 가중치'를 판별해내기 위함입니다. 만약 A->B->C->A의 경로를 지나면 음수의 가중치가 얻어진다고 하면, 기존 알고리즘은 이..
-
백준 2206 벽 부수고 이동하기 - C++, BFS쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 6. 23. 21:22
2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net #include #include #include using namespace std; int n, m; int goX[4] = { 0, 0, 1, -1 }; int goY[4] = { 1, -1, 0, 0 }; int map[1001][1001]; int arr[1001][1001][2]; int BFS(){ queue q; q.push(make_pair(make_pair(0, 0), 1)); arr[0][0][1] = 1; while(..
-
백준 1865 웜홀 - C++, 벨만-포드 알고리즘쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 6. 18. 16:27
1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net #include #include using namespace std; int t, n, m, w; // 지점의 수, 도로의 수, 웜홀의 수 int node[501]; bool possible; vector edge; bool Bellman(){ node[0] = 1; for(int i = 0; i node[from] + cost) node[to] = node[from] + cost; } } for(int j = 0; j < edge.size(); j..
-
백준 2467 용액, 2470 두 용액 - C++쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 6. 17. 21:17
2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net #include #include #include using namespace std; int n, resL, resR; int main(){ scanf("%d", &n); vect..
-
백준 17404 RGB 거리 2 - DP쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 6. 17. 21:03
17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net #include #include using namespace std; int main(){ int n; int res = 1000010; int house[1005][3]; int arr[1005][3]; scanf("%d", &n); for(int i = 0; i < n; i++){ for(int j = 0; j < 3; j++){ scanf("%d", &house[i][j]); } } for(int j = 0; j < 3; j++)..
-
길찾기 알고리즘(2) - 다익스트라 알고리즘쾌락없는 책임 (공부)/알고리즘 공부 2021. 6. 17. 20:59
다익스트라 알고리즘 다익스트라 알고리즘은 최단거리를 구하는 알고리즘중 가장 대표적인 알고리즘으로 아래와 같은 조건에서 사용하면 좋습니다. - 간선간 음의 가중치가 없을때 - 시작지점이 한개의 정점으로 정해졌을 때 (시작점이 여러개라면 다익스트라를 여러번 돌려 해결이 가능합니다) 다익스트라 알고리즘은 '가장 빠른 길'을 찾는 알고리즘으로 간선간 음의 값을 가지는 길은 없다고 생각합니다. 또한 플로이드-와샬보다 속도는 빠르지만 시작지점 1개에 대해서만 빠른 길을 찾는 알고리즘입니다. 조금 풀어쓴 다익스트라 알고리즘 1. 시작점 start, 도착점 finish, 각 경로와 가중치가 주어지게 됩니다. - 입력을 전부 받아오면 다익스트라를 위한 배열을 아래 표처럼 INF로 초기화해줍니다. 1 2 3 4 5 INF..
-
백준 11657 타임머신 - C++, 벨만포드 알고리즘쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 6. 15. 10:50
11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net #include #include using namespace std; int n, m; long long node[501]; vector edge; void Bellman(){ // 벨만 포드 알고리즘 node[1] = 0; for(int i = 1; i node[from] + cost) node[to] = node[from] + cost; } } //사이클이 있는지 확인하기 for(int i = 0; ..
-
백준 7579 앱 - C++, 배낭 문제쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 6. 15. 10:35
7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net #include #include using namespace std; int n, m, sum = 0; int mem[10001]; int abyte[101]; int cost[101]; int main(){ scanf("%d %d", &n ,&m); for(int i = 0; i < n; i++) scanf("%d", &abyte[i]); for(int i = 0; i < n; i++){ scanf("%d", &cost[i]); sum += cost[i]; } for..