1. 문제 새로 건설할 당위성이 있다: 고속도로를 통해 오갈 수 없던 두 도시가 새로 연결됨. 두 도시를 오가는 데 걸리는 시간이 단축 되어야함 N년간 하나씩 고속도로를 건설할때 이들 중 몇 개가 의미가 없는지 계산하여라 2. 플로이드 n번 역시 간단한 풀이는 그냥 건설할때마다 플로이드를 수행하는 것이다, 하지만 이는 시간초과로 문제를 시간안에 해결할 수 없다. 또다른 방법은 플로이드를 계산할때 a, b 정점을 경유하는지 기록하는 것 만약 고속도로가 추가되면 이 기록을따라 a->b, b->a거리를 업데이트 시키고, b와 a에 대해서만 플로이드를 다시 수행하는 것이다. 하지만 이것은 구현도 까다롭고 복잡하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..

1. 문제 이 문제는 경유점이 중요하다. 한 정점마다 경유하는지를 조사하고 그 경유점으로 인해 최소거리가 되는지 조사하는 플로이드 알고리즘을 이용하여 이 문제를 해결할 수 있다. 2. 경유점 정렬 플로이드 알고리즘에서 정점들의 추가 순서는 알고리즘의 정당성에는 영향을 미치지 않는다. 따라서 delay에 대해 정렬하고, delay가 작은것 부터 조사하게 되면 경로에서 어떤점이 최대의 delay를 가지는지 별도의 연산이 필요없게된다. (항상 추가하는 정점이 현재 최대 delay이므로) 3. 플로이드 알고리즘: 잘못된 풀이 플로이드 알고리즘을 적용시킨 처음 풀이는 다음과 같았다. 정점 w를 추가 하였을 때 adj[i][w] + adj[w][j] + delay[w] 에서 i->w 에서 생기는 딜레이와 w->j ..

1. 문제 이 문제는 주어진 그래프에서 '사이클'을 찾는 문제이다. 특히 1번 정점을 지나는 '사이클' 만 찾으면된다는 것이다. 다른 곳에서 생기는 사이클은 전부 무시해도 된다는 것이다. 하지만 이 문제는 한번 꼬아서 최대와 최소 즉 양의 무한대와 음의 무한대일 경우도 찾아야하는 것이다. 2. 벨만-포드 알고리즘 벨만-포드 알고리즘은 relax를 |V|번하게되면 그래프에 음수사이클의 여부를 알 수 있다. 이 알고리즘을 조금 변형하여 V번째 완화에서 만약 성공하면 시작점부터 완화가 발생한 지점까지 갈 수 있는지 확인하고 완화가 발생한 지점에서 목적지까지 갈 수 있는지 또 확인해야한다. 이는 0번에서 1번까지 도달하는것을 제외한 모든 사이클을 무시하게 해준다. 코드는 다음과 같다 이 코드는 최대 최소를 한번..

1. 문제 이 문제는 여러 소방서에서 불난집까지 가는 최단 거리들을 찾는 것이다. 이것은 불난집을 여러번 다익스트라를 돌려서 가장짧은 소방서를 찾으면 해결되지만 이 문제의 의도는 아니다. (소방서를 기준으로 돌리거나 플로이드의 모든 쌍 최단 경로 알고리즘(O(V^3))을 이용하여 풀 수 도 있지만 느리다) 2. 모든 소방서를 하나로 이 문제는 모든 소방서를 한 소방서에 합치면 다익스트라 한번에 해결 할 수 있다. 다음은 모든 입력이 주어지고나서 첫번째 소방서에다가 하나로 합친 그래프를 만들고 문제를 해결하는 코드이다. 책에서는 인덱스 0 인 임의의 정점을 만들어서 이를 가중치가 0 으로 소방서를 전부 이었다. 이렇게하면 모든 소방서에서 동시에 다익스트라를 수행하는것과 같다. 1 2 3 4 5 6 7 8 ..

1. 다익스트라 문제 이 문제는 간단한 다익스트라 문제이다. 이 문제의 핵심은 정수의 거리가 아닌 실수인 노이즈의 증폭도라는 것이다. 따라서 간선을 지나가면서 가중치를 더하는게 아니라 곱을 하는 것이다. 2. 책의 풀이 책에서는 곱을 로그의 합으로 변환해서 문제를 해결하였다. 로그의 합의 최소를 구하고 exp()만 해주면 답을 구할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include #include #inc..

1. 문제 기둥이 4개가 있다. 네 개의 기둥에 원반들이 자유롭게 배치되어있을 때 (작은것이 위로 와야함) 모든 원반을 맨 오른쪽 기둥으로 옮겨 놓기 위해 필요한 최소한의 움직임 수를 계산하는 프로그램을 작성하여라 2. 최소거리 탐색 기둥이 4개, 원반이 최대 12개 이므로 기둥은 2비트로 표현가능하므로 각 원반마다 해당하는 기둥을 나타내는 상태공간은 최대 24비트만 있으면 표현가능하다. 상태공간에서 최단거리를 구하기위해 너비우선 탐색을 사용하면 시간이 초과 될 수 있다. 분기점은 최대 6개에 최소 3개이니 대략 5라고하자 그러면 최단거리가 d일때 O(5^d) 의 시간이 걸린다. 하지만 목표상태에서 역방향으로 움직이기 쉬우므로 양방향 탐색을 통해 시간을 줄일 수 있다. 그러면 O(5^(d/2))로 어느정..