궤도

문제 풀이 지금까지 풀었던 골드1 문제는 힌트를 조금씩 봐야했는데, 이건 정말 나혼자만의 힘으로 풀었다. 뿌듯히다. 처음에는 '플로이드-워셜'일까 싶었는데 이것도 모든 경로와 비용을 고려하진 못해서 동적 계획법을 써야겠거니 했다. 일단 최소 2차원 배열일 것 같았고, 행과 열을 무엇으로 할지 고민했는데 냅색 문제를 떠올렸다. 그래서 행을 각 정점으로 하고, 열을 비용으로 하는 2차원 dp 배열을 생각했다. 예제 입력 1의 두번째 테스트 케이스에 대해서 dp 배열의 초기값을 만들어보면 이렇게 될 것이다. dp[i(파란색)][j(초록색)]의 의미는 j만큼의 비용이 있을 때 1번 정점에서 i번 정점까지 가는 최단 거리이다. 당연히 출발점인 1에서 1까지 가는 최단거리는 비용에 상관없이 0이다. 한편 예제 입력..

문제 풀이 처음에는 이 문제가 당연히 플로이드-워셜 문제인 줄 알았다... 실제로 그걸로 풀었더니 맞기도 했고... 근데 다익스트라 문제라는 것이다...! 난 이해가 되지 않았다. 다익스트라는 하나의 시작점에서 모든 정점과의 거리를 구하는 SSP 알고리즘인데 이 문제는 모든 사람에 대해 도착지점 하나에 대한 거리를 구해야 하기 때문이다... 굳이 모든 정점에 대해 하나하나 다익스트라를 돌리느니 플로이드-워셜이 낫지 않나 했는데 다익스트라 2번으로 해결할 수 있는 방법이 있었다. jow1025.tistory.com/114 [백준 1238] 파티 문제출처: https://www.acmicpc.net/problem/1238 풀이 출발->거쳐서->도착 의 패턴이 보여서 플로이드와샬 알고리즘이 끌리는데, 정점의 ..

문제 풀이 굳이 안그래도 될걸 억지로 어렵게 만들었다는 느낌이 드는 문제다. myunji.tistory.com/345 [백준] 1504번 : 특정한 최단 경로 문제 풀이 반드시 거쳐야 하는 정점이 B, C라고 하자. 이 둘을 거친 최단 경로는 1->B->C->N 또는 1->C->B->N일 것이다. 이걸 구하기 위해선 다익스트라 알고리즘을 3번 실행해야 한다. 1에 대하여 실행 myunji.tistory.com 논리는 이 문제랑 같다. 일단 s->t 최단 거리를 구한다. 만약 s->g->h->t 또는 s->h->g->t 의 최단거리와 s->t와 같다면 목적지가 될 수 있다. 소스코드 #include #include #include #include #include #include using namespace..

문제 풀이 반드시 거쳐야 하는 정점이 B, C라고 하자. 이 둘을 거친 최단 경로는 1->B->C->N 또는 1->C->B->N일 것이다. 이걸 구하기 위해선 다익스트라 알고리즘을 3번 실행해야 한다. 1에 대하여 실행해 1->B, 1->C의 최단 거리를 알아야 하고 B에 대하여 실행해 B->C, B->N의 최단 거리를 알아야 하고 C에 대하여 실행해 C->B, C->N의 최단 거리를 알아야 한다. N까지 가는 두가지 경로 중 작은 것을 택하면 된다. 다익스트라 알고리즘의 자세한 구현 설명은 myunji.tistory.com/344 [백준] 1753번 : 최단경로 문제 풀이 TMI 난 사실 다익스트라 알고리즘에 트라우마가 있다. 바로 지금보다도 훨씬 아무것도 모르던 2학년 2학기 시절 라이브러리 하나 없..

문제 풀이 TMI 난 사실 다익스트라 알고리즘에 트라우마가 있다. 바로 지금보다도 훨씬 아무것도 모르던 2학년 2학기 시절 라이브러리 하나 없이 다익스트라 알고리즘을 구현해야 했던 것이다. 심지어 최단 거리만 출력하는게 아니라 경로도 출력해야 했다. c로 구현해야 했기 때문에 스택, 우선순위 큐 기타 등등을 스스로 구현해야 했다. 하지만 난 이제 라이브러리를 마음껏 사용할 수 있기 때문에 용기를 내보려 한다. 다익스트라 알고리즘은 특정한 출발 노드에서 모든 노드로 가는 최단거리를 구하는 알고리즘이다. 힙을 사용했을 때의 시간복잡도는 O(|E|log|V|)라고 한다. log의 밑은 2다. ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B..