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. 최단 경로 문제 (shortest path problem) : 가중치 있는 그래프 최단 경로 문제란 주어진 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제로, 그래프의 응용 문제 가운데 가장 유용하고 널리 사용된다. 가중치가 없는 그래프에 대한 최단 경로는 BFS를 사용하면 되므로 여기서는 가중치 있는 그래프에 대한 알고리즘을 다룬다. 이 알고리즘들은 '최단 경로'를 구성하는 정점들의 목록을 구해주는 것이 아니라 '최단 경로의 길이'를 찾아 주는 것들이다. 실제 경로를 얻어내려면 탐색 과정에서 별도의 정보를 저장하고, 이것으로부터 실제 경로를 찾아내는 코드를 작성해야한다. 다양한 그래프의 종류와 특성에 따라 알고리즘의 효율성이 달라지기 때문에 많은 경로 알고리즘이 존재한다...

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

1. 최단 경로 전략 너비 우선 탐색은 최단 경로 문제를 푸는 가장 직관적이고 유명한 방법이지만, 모든 최단 경로 문제를 너비 우선 탐색만으로 풀 수 있는 것은 아니다. 문제에 따라서는 너비 우선 탐색보다 다른 탐색 알고리즘이 더 강력한 경우가 있다. 2. 15- 퍼즐 7 8 4 1 2 3 5 6 9 10 11 12 13 14 15 => 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4 X 4 격자에 끼워진 열다섯 개의 숫자 타일을 순서에 맞게 맞추는 퍼즐이다. 빈 칸에 상하좌우로 인접한 타일 하나를 빈 칸으로 밀어넣는 것을 한번의 움직임이라 할 때, 이 퍼즐을 해결하기 위해 필요한 최소 움직임을 구하는게 오늘의 목적이다. 이 문제를 풀기 위한 첫번째 단계는 게임판의 상태를 정점으로 표..

1. 문제 C개의 선물들을 n명의 아이들에게 나누어주는데 m명의 아이들에게는 1+ g 개 n-m 명의 아이들에게는 g개 씩 나누어준다고한다. 이때 C는 D 목록에 있는 수로만 이루어져있는 자연수여야한다. 2. C의 성질 이 문제는 D목록을 정점으로하는 무향 그래프를 생성하여 0에서부터(impossible) bfs로 차근차근 하나씩 자리수를 늘려가며 맞아 떨어지는지 검사하는 문제인것같다 문제에서 주어지는 변수들로 수학식을 정리해보면 다음과 같다 C = m(1+g) + (n-m)g C = ng + m C%n = m%n (C>=n) C%n = m ,,, m>n 즉 목록 D로 구성되어있는 C를 n으로 나눈 나머지는 m을 n으로 나눈 나머지와 같아야한다 이때 m과 n은 고정점이므로 이점을 이용하면 목록이 주어졌을..