[일반] 알고리즘 문제푸는데..

[야야야(115.22)]

플로이드 알고리즘을 구현하고 P값과 D값 

즉 어느 노드에서 다른노드로가는 비용이 가장적게드는 경로를 구한다음에

만야 랜덤으로 두개의 서로 다른 노드에서 사람이 출발하여 어느 중간지점에서 만난다면

그렇게 만날수있는 경로가 여러가지가있잖아?? 그걸 일일이 하나하나 비교해가면서 원하는값 찾을려니간 그경로의 나눠진만큼 다스캔해야해서

오버타임 뜨더라고.. 이런경우는 어케하지..?? 60점에서 안올라가네

[하루룽(ailedear)]

해석이 안댐

[하루룽(ailedear)]

P값과 D값(??) 랜덤으로(??) 원하는값(??)

[야야야(115.22)]

P는 플로이드 알고리즘으로 a->b 갈때 최저비용으로 가는 경로를 저장한 배열이고 D는 플로이드 알고리즘으로 a->b 갈때 최저비용을 저장한 배열이야

[야야야(115.22)]

이두개가지고 임의의 a와 b에서 중간지점을 찾을려고해 그때 선로상에서도 만날수있고 어느 노드 c d e 중에서도 만날수 있어 선로상에 만나면 c-d 사이에 만나면 c d 값을 출력하고 c위에서 만나면 c c 출력하고 이럴때 제일 작은 값을 찾고싶은데 문제 제출은 햇는데 답은 다나오는데 40점이 속도 문제 ㅜㅜ 아마 저기 경로가 여러개로 갈리면서 스택오버플로우 또는 경로가 너무많아서 탐색시간이 오래걸리는거같오 ㅎㅎㅎ.. 그래서 잘모르겟당

[하루룽(ailedear)]

제일 작은 값을 찾고싶다고 했는데 중간지점을 m이라고 했을 때 a->m으로 가는 경로의 길이와 b->m으로 가는 경로의 길이 중에 큰 값을 최소화하고 싶다는거임? 선로에서 만나면 비용 처리는 어떻게 되는거야 간선을 반반씩 자르나 그리고 저말대로면 다익스트라만 돌려도 될텐데 플로이드를 쓰는 이유는 뭐지 그냥 빠진조건이 너무 만은데 문제자체를 올릴수는업ㄹ는건가

[야야야(115.22)]

a-b 중간지점으로 가는 경우가 얼마나 노드가 갈라지냐에 따라서 a-b 길이의 중간인점이 여러가지가 나오는데 답은 정확한데 속도에걸려서 이게 경우의수가 너무많아서 탐색하는데 오래 걸리는거 같아..

[야야야(115.22)]

플로이드를 쓴이유는 처음에 경로만주어주고 임의의 두 노드에서 중간지점을 찾아라하는거거든 그게 최대 3회 나와 그래서 플로이드썻어 근데 이거는 플로이드 나 다익스트라 문제보다 a->b 가는 경우가 a-1-b a-2-3-4-b a-5-7-1-b 이런식으로 잇으면 저 세가지 경우 중간지점은 다다르잖아 그때 양끝노드가 최소가 되게하는 값을 찾고싶은데 내가 알고리즘 배운지 이제 한달넘어가는데 이걸 dp로 구현이 가능한지와 다른 소거법이 잇는지 모르겟네 ㄷㄷ

[하루룽(ailedear)]

ㅇㅎ 거의 알아들은듯 근데 "양끝노드가 최소가 되게 한다는게 뭔소리임 노드의 번호의 합?

[야야야(115.22)]

만약 중간지점에 만나는 후보가 9-1 5-6 2-2 가 있으면 제일작은값을 왼쪽에 보내고 그중에서 제일작은에 즉 1-9가 답이되거든

[야야야(115.22)]

플로이드가 시간복잡도가 N^3이긴한데 이거때문인가 ;

[하루룽(ailedear)]

아닌가 졸려서 헷가릴네

[하루룽(ailedear)]

다시 정리좀 하고옴

[야야야(115.22)]

흐음 근데 다익 돌릴때 비용이 같은경우 경로가 나뉘는 거잖아 이럴때는 데이터구조가 어떻게될려나 ㅋㅋ 감도안오네

[하루룽(ailedear)]

우선 a와 b 각각에서 다익스트라를 돌리고 a에서 b로 가는 최단경로의 절반을 mid라 하자

[하루룽(ailedear)]

2중 반복문으로 (i,j)를 번호가 작은 순으로 순회하면서, i==j라면 a->i로 가는 최단경로가 정확히 mid이면서 i->b로 가는 최단경로도 정확히 mid일 때 후보에 속함

[하루룽(ailedear)]

i != j라면 (단, j는 i와 간선으로 연결되어 있음) a->i 거리 + (i->j)간선 비용 + j->b 거리 == a->b거리일 때 (a->i->j->b) 경로가 최단경로에 포함되어 있음. 이 때 a->i거리가 mid보다 작으면서 a->j거리가 mid보다 크거나, 그 반대가 성립하면 (i,j)쌍은 후보에 속함

[하루룽(ailedear)]

후보에 속하는 (i, j) 쌍이 나오는 순간 탐색을 종료하면 됨 그게 항상 사전순으로 최소이므로 다익 돌리는 데 O(ElogV), (i, j) 정점 쌍 찾는 데 O(E)

[야야야(115.22)]

다익스트라로 경로를 뽑아낼려면 값이 바뀔때마다 스트링같은걸로 게속 붙여가면서 선언해야 할거같은데 근데 문제는 다익스트라 채우는 과정에서 같은경우에 경로가 갈리는 경운데 그거를 어떻게 처리하지??

[하루룽(ailedear)]

이거랑 비슷하게 하면 맞겠지?? ㅁㄹ 자러간다

[야야야(115.22)]

다익으로 정점의 미드는 쉽게구하는데 ㅜㅜ 그 미드값을 가지는 경로가 많이잇자너... 그게문제 지금 문제 제출한거 60점인데 40점이 플로이드로 푼사람은 못맞추거나 아니면 그갈라지는 경로를 최소화 해라는거 같은데 어렵네

[하루룽(ailedear)]

경로를 왜뽑아냄 각 정점에다 최소비용만 저장하면 되지

[야야야(115.22)]

어쨋든 고마워용~

[하루룽(ailedear)]

그러니까 그 mid값을 가지는 모든 경로들 중에서 정점 번호가 사전순으로 맨 앞에 오는 경로를 찾아내는 방법을 저기다 써놨잔아 다익스트라는 걍 전처리

[야야야(115.22)]

흐음 내가그림 올려볼까

[야야야(115.22)]

일단 이해해볼께 고마워

[익명(218.54)]

문제를 올려줘 ㅅㅂ ㅋㅋㅋㅋ

[익명(218.54)]

설명 진짜 뭔 소린지 못 알아듣겠네

[익명(121.175)]

얘는 espa 알고리즘 과제 나올때마다 글 올리네

[야야야(115.22)]

ㄷㄷ 이것도 안돼 ???? ㅜㅜ 지울게