ps(알고리즘) (44) 썸네일형 리스트형 그래프 최단경로 알고리즘 - 플로이드워셜, 다익스트라, 벨만포드, SPFA 정리 그래프에서 최단경로를 구하는 대표적인 알고리즘 4개를 소개할 것이다.정점의 개수는 V(vertex), 간선의 개수는 E(edge)로 표기한다. 1. Floyd - Warshall 알고리즘모든 정점 간의 최단거리를 구하는 알고리즘이다.개념과 구현 모두 아주 간단한데, 그냥 중간 정점 k를 거치면서 i에서 j로 가는 최단경로를 갱신해나가면 된다.k를 1부터 N까지 돌면서 중간 정점으로 1~k를 사용하며 i->j로 가는 최단 경로를 저장한다.adjMat[i][k]와 adjMat[k][j]에 저장된 값은 중간 정점으로 1~k-1을 사용하는 최단 경로일 것이다.여기서 중간 정점 k를 사용할 때 거리가 더 짧아진다면 adjMat[i][j]가 갱신될 것이다. 매우 간단한 알고리즘이지만, 시간복잡도가 O(V^3)이고,.. 책 구매하기2 - 최대유량(에드몬드-카프 알고리즘) 최대 유량은 용량이 정해진 간선들이 있는 그래프에서 출발점->도착점으로 보낼 수 있는 최대 유량을 구하는 문제이다.최대 유량 문제를 해결하는 아이디어는 포드-풀커슨 방법이다.포드-풀커슨 알고리즘이라고 부르기도 하는데, 아이디어의 핵심은 음의 유량을 설정하는 것이다.우선 사이에 간선이 있는 두 정점에 간선이 한 방향으로만 있다면, 반대 방향 간선도 만들어주고, 용량을 0으로 설정한다.출발점에서 도착점까지의 경로를 dfs로 하나 찾으면, 그 경로에 흘려보낼 유량은 지나치는 모든 간선의 (용량-현재유량)의 min값이될 것이다.그렇게 계산한 유량을 흘려보내주고, 지나치는 모든 간선의 반대 방향 간선에 음의 유량을 흘려준다.처음에는 음의 유량을 설정하는 것이 어떤 의미인지 이해하기 어렵긴 한데, 여러 그래프의 예.. K번째 최단경로 찾기 k번째 최단경로를 찾는 문제이다.1번 도시에서 i번 도시로 가는 k번째 최단경로 거리를 모두 출력해야 되기 때문에 다익스트라 알고리즘을 써야 한다.k번째 최단경로를 찾아야 하기 때문에 기존의 다익스트라처럼 visit 배열을 체크해서 다시 오지 않는 방식이 아니라어디에 방문을 하면, 그 노드의 우선순위큐에 거리를 넣는 방식을 쓴다. 우선순위큐를 노드의 개수 N개만큼 만들고, i번 도시에 방문을 하면, i번째 우선순위큐에 방문까지 걸린 거리를 push한다.이때 큐의 크기가 K를 넘어가면 안되기 때문에 큐의 크기가 K보다 작을때는 그냥 push를 하고,큐의 크기가 K일때는 top의 값과 비교를 해서 top보다 작으면 push를 한다.top보다 크면 모든 경로를 정렬했다고 쳤을 때 어차피 K+1번째 이상에 위치.. 구간 합 구하기2 구간 합 문제는 세그먼트 트리로 풀 수 있었는데 이 문제는 update를 하나의 값만 하는게 아니라 구간을 정해서 구간 안의 모든 수를 갱신한다.그래서 원래 구현했던 대로 update를 처리하면 구간의 길이만큼 K번 해야되서 시간이 안된다. 이 문제는 lazy propogation 알고리즘만 알면 구현으로 끝나는 간단한 문제이다.세그트리에 lazy라는 새로운 값을 부여하는데, 구간 업데이트를 할 때 현재 탐색하는 구간이 업데이트하려는 구간에 포함된다면,아래의 노드들을 탐색하는 것이 아니라 그냥 lazy 배열에 값을 추가해준다.그리고 나중에 업데이트를 하거나 쿼리를 탐색할 때 lazy 배열에 값이 존재한다면, 해당 노드의 seg 값을 구간의 길이*lazy값 만큼업데이트를 해주고, 아래 노드 2개로 가서 각.. 경찰차 간단하게 경찰차 두대에 사건을 맡겨서 이동거리 합이 최소가 되게 하면 된다.N,W는 1000이하이다. dp로 풀면 되는데, dp[i][j]를 경찰차 1이 마지막으로 해결한 사건 번호가 i, 경찰차 2가 마지막으로 해결한 사건 번호가 j일 때 이동거리의 합의 최소로 정의한다.이렇게 하고 dp[i][j]에서 i,j중 큰 사건 번호가 마지막으로 해결한 것이기 때문에 max(i,j)+1을 경찰차1한테 배정했을 때와경찰차2한테 배정했을 때의 이동거리를 dp값과 비교해서 더 작은 것으로 채워나가는 식으로 하면 된다.void solve(){ dp[1][2]=0; police.push({1,2,0}); while(!police.empty()) { Data t = police.top().. 박성원 단순한 문제인데 꽤 어려웠다.N개를 배열하면 N!가지가 있어서 일일히 모든 경우를 따져보는 것은 불가능하다.그런데 정확한 경우의 수를 세려면 모든 경우를 따져야 한다.모든 경우를 나눠보지 않고 어떻게 나눠지는 경우의 수를 셀 수 있을지 생각해 내기가 어려운 문제였다. 결론적으로 방법은 dp를 쓰면 된다.N만 놓고 본다면 15! 이어서 모든 경우를 셀 수 없는 것이 맞는데이 문제는 K가 100이하여서 풀리는 문제이다.N개의 숫자들 중에 어떤 숫자를 사용했는지를 비트마스킹으로 표현을 하면dp[i][j]는 비트가 i이고, K로 나눈 나머지가 j인 경우의 수이다.이렇게 하면 2^15 * 100 크기의 dp 배열을 채우면 되는 문제가 돼서 시간 안에 풀 수 있게 된다. void solv(){ dp[0][0].. 발전소 비트마스킹으로 상태를 정의하면서 bfs를 돌면 된다.도는 중간에 켜져있는 발전소 개수가 P이상일 때만 저장된 정답과 비교하면서 돌면 끝이다.struct Data{ int bit, cost, cnt; bool operatorr.cost; } return cnt>r.cnt; }};구조체를 이렇게 정의해서 어떤 발전소들이 켜져 있는지 저장하면 bit, 현재까지의 비용 cost, 켜져 있는 발전소의 개수 cnt이렇게 3가지 정보를 이용한다.priority_queuepw;void solve(int start,int stcnt){ pw.push({start,0,stcnt}); while(!pw.empty()) { Data t = pw.top();.. 큰 수 만들기 그냥 그리디로 풀면 되는 문제이다.정렬을 하는데 정렬 기준만 정해주면 되는데, a, b가 있을 때 ab와 ba를 비교하면 된다.처음에는 자릿수로 따지면서 맨앞이 큰 순서대로 하고, 겹치는 경우에 대한 예외 처리를 하려다 보니 너무 복잡해졌는데 생각보다 간단하게 해결할 수 있었다.#include#include#include#includeusing namespace std;int N;string arr[1004];bool compare(string a, string b){ string ab = a+b; string ba = b+a; if(ab>ba) return true; else return false;}int main(){ scanf("%d",&N); for(int i=1.. 이전 1 2 3 4 ··· 6 다음 목록 더보기
