전체 글 썸네일형 리스트형 1916번 1916번 - 최소 비용 구하기 문제를 그래프 모델로 바꾸고, 주어진 시작점과 끝점에서의 최단 거리를 구하면 된다. 가중치가 있고, 최단거리를 구하기 때문에 bfs 가 아닌 다익스트라 알고리즘을 사용하면 된다. 다익스트라 알고리즘은 두가지 방식으로 풀 수 있는데, 첫번째는 우선 순위 큐를 이용하는 방법으로 O(ElogV) 의 시간복잡도, 두번째는 우선 순위 큐를 이용하지 않는 방법으로 O(VE)의 시간복잡도( 연결리스트로 풀 경우). 나는 우선 순위 큐를 이용해서 문제를 풀었다. 다익스트라로 풀어보는 첫 문제라서, 우선 순위 큐를 쓸때랑, 쓰지 않을 때 방법이 자꾸 섞여서 생각났다. 더 풀어보면서 확실히 다익스트라를 두가지 방식으로 푸는걸 잡아야겠다. 우선 순위 큐로 풀 때는, 방문을 확인하는 배열이 따.. 더보기 1865번 1865번 - 웜홀 11657 타임머신과 같이, 음수 간선이 있는 그래프에서 최단 거리를 구하는 벨만 포드 알고리즘을 쓰면 된다. 근데 웜홀 문제는 음수 싸이클이 존재하는지 여부만 확인하면 된다. 음수 싸이클이 존재하면, 충분히 음수 싸이클을 돈 뒤에 양수 간선을 이동해서 시작점으로 이동하면, 항상 시작점에서 출발할 때보다 더 이른 시간에 도착하기 때문이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include#includeusing namespace std; co.. 더보기 11657번 11657번 - 타임 머신 그래프 상에서 최단 거리를 구하는 알고리즘으로 풀면 된다. 단, 가중치에서 음의 가중치가 존재 하기 때문에, bfs 나 다익스트라를 쓰면 안되고 벨만 포드 알고리즘을 사용하였다. 음의 싸이클이 존재하는 경우는 ( iter == n && update == true) 일 때 이므로 체크해주면 된다. 그리고 도달할 수 없는 경우는 INF 로 남아있기 때문에, 이를 if문으로 걸러서 출력하면 된다. ##SPFA 풀이 추가 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879.. 더보기 2018-01-02 최단경로 문제(4가지) 1 . BFS - 가중치가 없거나 동일한 그래프. 단일 시작점과 모든 쌍 알고리즘. - Queue 를 이용해서 구현.- 방문 체크 배열 (visited) => 거리 배열로 대체 가능(초기값 -1)- 거리 배열은 distance[next] = distance[now] + 1 2. 다익스트라 알고리즘 - 가중치가 있는 그래프. 단일 시작점과 모든 쌍 알고리즘 . 음의 가중치가 있는 경우 계산 불가. (엄밀히 말하면 음수 싸이클이 있는 경우 계산 불가) 구현방법 - Priority Queue 사용, Priority Queue 사용X ##Priority Queue 를 사용할 때 , 시간 복잡도 = O(E * logV) - 시작점의 distance 만 0을 하고 나머지는 INF 로 초기화... 더보기 반복적 깊이증가 탐색 1.최단경로 - bfs 2.메모리 or 시간부족 - 양방향 탐색 3. 반복적 깊이증가 탐색 http://www.aistudy.com/heuristic/iterative_deepening_dfs.htm 더보기 1516번 1516번 - 게임 개발 위상 정렬을 이용한 문제. 2056번 (작업) 이랑 완전 똑같은 문제다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#include#include using namespace std; int indegree[501];int dist[501];int t[501];int main(){ int n; vector v[501]; scanf("%d", &n); for (int i = 1; i 더보기 2056번 2056번 - 작업 위상정렬을 이용한 문제풀이다. 위상정렬은 2가지 풀이방식이 있는데, 그 중에서 BFS로 풀었다. indegree 값을 구하고, dist[i] 배열에는 i번 작업이 끝나는 시간으로 정의했다. (처음에 dist[i]=i번 작업이 시작하는 시간으로 정의했는데, 그럴 경우 맨 마지막에 호출되는, out-degree 가 0인 작업들은 다시 한번 계산해줘야 하는 번거로움이 있었다.) 또 처음에 while 문 안에서 queue 가 empty 가 될 때, dist 값을 구했는데, 그러면 안됐다. 마찬가지로 out-degree 가 0인 작업들 중에서 시간이 최대로 많이 걸리는 애가 선택이 되는게 아니기 때문이다. 1234567891011121314151617181920212223242526272829.. 더보기 2018-01-01 ##위상정렬은 DAG(방향있는, 싸이클 없는, 그래프) 에서 방법 2가지 - BFS : indegree 0인 지점부터 방문하면서, 방문할때 indegree 감소하고 0이면 queue 에 넣기. - DFS : 방문하지 않은 모든 정점 DFS 하면서, DFS 종료시 배열에 저장하고, 나중에 역순으로 출력. ##오일러 서킷/ 오일러 트레일 (서킷은 시작점=끝점, 트레일은 시작점 != 끝점) - 정점의 차수(degree의 개수가 중요) - 무향 그래프에서 오일러 서킷 - 모든 정점의 차수가 짝수, 하나의 컴포넌트로 이루어져 있어야함. 오일러 트레일 - 시작점 ,끝점의 차수가 홀수, 나머지 정점 짝수 하나의 컴포넌트로 이루어져 있어야함. - 유향 그래프에서 오일러 서킷 - 모든 정점의 in-degree 와 out.. 더보기 이전 1 ··· 39 40 41 42 43 44 45 ··· 61 다음