[02:25] 국내도 아이패드3 정발하네요 [06:55] Seony, 계십니까? [06:55] ㅇㅇ [06:56] 보내주신 메일 확인해봤는데요~ [06:56] 순서는 크게 중요하지 않아요 ㅎㅎ [06:56] 아 그래? 근데 걔네들은 BFS로 길을 찾아가는 알고리즘이잔하.. [06:57] 결국 다 돌다보면 최대플로우 양이 계산되어가게 되어있는데 ;; [06:57] 아... 최대플로우의 양은 결국 같은 값이 나오게 되어있는거구나.. [06:57] imsu, 굳모닝 [06:57] 어쩐지 숙제하다보니 계속 답이 같은 걸로 나오긴 하더라... [06:57] 그럼 총용량이랑 단절은? [06:58] bluedusk, 안녕하세요~ [06:58] 아니, 일단은 3번째 페이지부터 봐줘. [06:58] 왜 답이 e인건지.. [06:59] 답이 e 라니용? [06:59] 3번째 페이지 봤어? [06:59] sp [06:59] 네 [06:59] 잠시만. [07:01] 교과서에서는, e가 맥시멈이라고 하거든. [07:01] Maximum flow라고 하는데, 왜 그게 e인건지 이해가 잘 안가. [07:01] 아... 내가 설명을 잘못했구나... 보기가 a,b,c,d,e가 아니라, a->b->c->d->e의 순서대로 진행되는 건데, [07:02] f에서 더 이상 갈데가 없으니 e가 맥시멈이다. 그렇게 설명하고 있어. [07:05] 네 저도 이책 가지고 있어요~ ㅋㅋ [07:05] 한글번역판? [07:06] ㅇ [07:06] 넹 [07:06] 울 교수가 학기 첫날 뭐라 그랬냐면, [07:06] "이 책 존내 어렵다. 그러니까 만약에 이해가 안가면 그냥 넘어가라" [07:06] ㅋㅋ [07:07] 설명이 잘 되어 있는거 같던데~ [07:07] ㅎㅎ [07:07] 근데 책에 수학적인게 좀 많이 들어가서 ㅎㅎ [07:07] ㅇㅇ 좀 많이 들어갔지 ㅎㅎ [07:07] 그러니까 암튼, 내가 궁금한 건 왜 e가 맥시멈이냐... [07:07] 바이블 같은 느낌~ ㅋㅋ [07:08] 더이상 보낼데가 없으니깐요~ [07:08] 그럼 길 따라 쭉 다니다가, 더 이상 보낼데가 없으면 그게 최대가 되는 거야? [07:08] 너무 간단하게 대답햇나~ ㅋㅋ [07:08] 네 [07:09] 숫자로만 봐서는 d가 더 많아보이잖아.. [07:09] 음 이건요 [07:09] 왼쪽 그림이 중요한게 아니라 [07:09] 오른쪽 그림이 중요해요 [07:09] ㅇㅇ [07:09] 아... 그렇게 말하니까 이해가 되네 [07:10] 오른쪽 그림을 보시면 더이상 못보네요 ㅋㅋ [07:10] ㅇㅇ 그리고 당연히 e가 맥시멈이네 [07:10] 최대용량이 꽉 찾거든요;; [07:10] 넹 [07:10] ㅇㅋ. 그러면, [07:10] 첫번째 질문으로 되돌아가서, [07:10] 총 용량이 31이라는 건 어떻게 나오는 거야? [07:11] 총용량이 30 ? [07:12] 총 capacity가 31이라는데, 대체 어떻게 계산하는 건지 이해가 안가서.. [07:12] 간만에 봤더니 또 까묵었네 ㅋㅋ [07:12] 잠시만요 [07:12] 최대 플로우 19는 그림갖구 머리 싸매니까 대충 어떻게 계산해내는 건지 알겠는데, capacity는 이해가 안가네.. [07:13] 30 맞아요? [07:14] 확실하지는 않은데, 어디서 저 계산대로 풀어논걸 봤어. [07:14] 아닐텐데 ;; [07:15] 아 41인가 [07:15] 아니구나.. [07:16] 내가 이해를 못하고 있는 상태에서 풀어논걸 봤으니, 내가 잘못 적용해서 푼걸수도 있어 [07:18] 아닐걸요 ㅋㅋㅋ [07:18] c(S,T) 계산에 의해 달라지는데 ;; [07:19] 근데 최대플로우라는 게, 결국은 t 양 옆의 숫자만 더해주면 나오는거 맞지? [07:19] 네 플로우 보존 법칙에 의해서 [07:20] ㅋㅋ [07:20] 음... 그럼 Capacity를 어떻게 계산하는지 알면 될 거 같은데 ㅎㅎ [07:21] 그냥 용량이에요 얼마나 많이 보낼수 있는가;; 물리적으로 ㅎㅎ [07:21] 그 때 그 때 달라지죵 ㅋㅋ [07:21] 너가 계산한 건 어떻게 하는지 좀 알려줘. 아마 내가 틀린 거 같아 ㅎㅎ [07:22] S 와 T 를 어는 vertex 에서 정의하느냐에 따라 달라질걸요~ [07:23] 일단 저 예제를 기준으로.. [07:23] 책에 나와 있는건데 ㅋㅋ [07:23] d 를 보세요 [07:24] 잉? 진짜? 내가 책 수십번도 더 봤는데.. [07:24] S = { s, v1, v2} , T = { v3, v4, t} 일 때 c(S,T) = 26 [07:25] 네트워크과 관련해서 Tx , Rx 로 나뉘어 지는거랑 똑같다고 보시면 되욤 [07:25] S 에서 T 로 얼마나 보낼 수 있느냐 ~ ;; [07:25] 머 이런거라고 생각하면 될거 같은데 ;;; [07:26] 그럼 경로가 어떻게 되는 거야? [07:26] s->v1->v2->v3->v4->t인거야? [07:26] 경로라기 보다는 집합이죠 [07:26] 노노 [07:26] s , v1, v2 가 하나의 집합이에요 [07:26] 음;; 예를 들면 각 가정의 하수 배출량을 계산할 때 [07:26] ㅇㅇ [07:27] 각각의 v1 v2, ~~~~~ 기타 등등 각 가정을 모두 출발지로 보는거죵 [07:27] 그럼, 내가 궁금한 건 26이라는 숫자가, 뭐뭐를 더해서 나온 거야? [07:27] 12 + 14 [07:28] 왜냐면 S 에서 T 로가는건 12 하고 14 밖에 없잖아요 [07:28] 그래서 두개 더하면 14 [07:28] 26 [07:28] v1-v3이랑 v2-v4, 그러니까 서로 집합간 연결점인거네 [07:28] 최대 용량 ㅋㅋ [07:28] 네 [07:28] 거기서 v2 -> v2 는 계산 안된게 다시 안보내면 되니까 ㅋㅋ [07:28] 뭐 이렇게 보면 되나? [07:28] 근데 저 첫번째 예제에서는, [07:28] v3 -> v2 [07:28] 집합을 {s, v2, v4}, {v1, v3, t}로 보는 거야. [07:29] 그러면 결국 저 경우는 모든 이동경로를 다 더해야하는거네 [07:29] 그럼 31 맞네요 ㅋㅋ [07:29] v2-v3은 반대방향이라서 포함 안하는 거고? [07:29] 16 + 4 + 7 + 4 [07:29] 네 그건 역플로우 [07:30] 오케. 이해했어. 그러면, [07:30] 시작점과 종점으로 보시면 되요 [07:30] 최소단절을 긋는 기준은 뭐야? [07:30] 긋는 기준이라;; [07:30] 그냥 아무거나 긋는건데 [07:30] ㅋㅋㅋ [07:30] 헐... [07:31] 자기가 계산하고 싶은거데로 [07:31] 한마디로 스타팅 포인트를 어디로 둘거냐는건데 [07:31] 음... 내가 다른 예제를 보여줄께 ㅋㅋ [07:31] http://seowonjung.com/screenshots/ScreenShot2012-04-16at9.31.22PM.png [07:31] 이 그림을 보면 최소단절이 그어져있는데, 원래 그어져있는 건 아니고, [07:32] 최소단절이 뭐냐는 게 질문이거든. 그래서 내가 저렇게 그은 건데, [07:32] 내가 준 pdf파일의 첫번째 문제의 경우는, [07:32] 제가 이해한건 그래요 최소단절은 내부적으로 복잡한 네트워크를 s,t 로 간단하게 구분한다. [07:32] 집합을 {s, v2, v4}, {v1, v3, t} 이렇게 미리 문제로 주어주니까 쉽게 그었는데, 이건 아예 주어진 게 없거든.. [07:34] 음... 그러면, v2-v3은 역방향이라 상쇄가 되는 건 맞는거지? [07:34] 아 최소단절;; [07:34] 아까 저렇게 그은게 단절이잖아요 [07:34] 그 단절중 최소인거 ㅋㅋ [07:35] 그러면 4가 되는 거야? ㅎㅎ [07:35] 아니요 [07:35] 용량 계산하였잖아요 [07:35] ㅇㅇ [07:35] 그 용량 계산한것 중에 최소가 되게 자르는거 ㅋㅋ [07:35] 맞나;; [07:36] 이건 좀 헷갈리네 ㅋㅋ [07:36] 최소가 되게 자른다... [07:37] 이건 저도 잘;; ㅋㅋ [07:37] 이해해볼게요 ㅋㅋ [07:37] ㅎㅎ ㅇㅋ. [07:37] 그러면, v2-v3은 역방향이라 상쇄가 되는 건 맞는거지? [07:38] 아... 말이 더 어렵네. 상쇄.. [07:38] 내가 상쇄라는 말을 자주 쓰는데, 여기서 쓰니까 더 모르겠네 [07:38] 상쇄라기 보댜는 [07:38] v3 에서 v2 로 보낼 수 있는 방향이잖아요 [07:38] ㅇㅇ [07:38] 그니까 해당사항 없죠 [07:38] 네트워크는 S->T 로 보내는게 순방향이잖아요 [07:38] 순방향의 용량을 계산하는건데 [07:38] 그 알고리즘 책에서 "상쇄"라는 말이 나오는데, 저 보기에서 상쇄가 뭔지 물어보는 문제가 나오거든.. [07:38] 저건 역방향이라 [07:39] 아 그래요? [07:39] ㅇㅇ [07:39] 혹시 메일 보내주신거 내용에 나오나요? [07:39] 니가 갖고있는 책에서 문제 26.2-3 봐바 [07:39] 내가 보는 거랑 똑같은 문제일거야 [07:41] 이제 동적프로그래밍 수업만 마치면, 이번학기 알고리듬 클래스는 끝이다... [07:41] 시험이 더 걱정돼.. [07:41] 그렇네요 상쇄가 나오네 ㅋㅋ [07:41] 그치? ㅎㅎ [07:41] 그러면 일단, 상쇄는 너도 모르는 부분인거 같으니까 지금 건너뛰고 마지막으로 하나만 더 물어볼께 [07:41] 에드몬드-카프 알고리즘이랑 포드-풀커슨이랑 다른 점은 뭐야? [07:42] 내가 보니까 그냥 길따라 찾아댕기는 건 똑같은 거 같은데.. [07:42] 에드몬드 카프는 아직 안봤는데요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ [07:42] 헛... [07:42] 포드-풀커슨을 개량시킨 알고리즘이라거든... ㅎㅎ [07:42] 포드 풀커슨만 ;;; 수업 때 필요해서 ;; [07:42] 그래봐야 소스 두세줄 더 들어간건데.. [07:42] 음... 그럼 일단 궁금한 건 다 배웠네. ㅎㅎ [07:42] 시간 내줘서 땡큐. [07:43] 상쇄라는게 [07:43] 그 뭣이냐 그걸 뜻하는 거 같아요 [07:43] 방향에 따라서 [07:43] 저기 d 보시면 [07:43] v3 -> v2 가는게 원래 5 였나 그랬는데 [07:43] ㅇㅇ [07:44] 다시 방향 제대로 가면서 아예 없어져 버린;; [07:44] 그걸 뜻하는 용어인거 같은데요~ [07:44] ㅇㅋ. 내가 책을 좀 더 볼께. [07:44] 아 마지막 하나 더 [07:44] 내가 보내준 PDF에 2번째 페이지 [07:44] 내가 그린거 맞게 그린 거야? [07:45] ? [07:45] 예제랑 똑같은거 아닝요? [07:46] 아... 저 문제는 에드몬드-카프 알고리즘을 적용시켜야하는 문제니까 패스해야겠네 [07:46] 오케. 일단 그럼 궁금한 건 다 됐네... [07:46] 내가 저번에 그 C언어 답 주면서 프로젝트 해야한다는거 있잖아... [07:46] 시간이 나면 보겠으나;;; ㅋㅋㅋ [07:46] 네 [07:46] 학교 가서 애들한테 얘기해보니까, 열라 어려워서 못하겠대 ㅋㅋ [07:47] 일단 좌표를 프로그래밍으로 어떻게 구현을 해야할지 답이 안나온대... [07:47] 그러고보면 난 성공한듯. ㅋㅋ [07:47] 그냥 x,y 나누면 되지머;;ㅡ.ㅡ; [07:47] 나누는거야 쉬운데, 그 나눈걸 갖구 길 따라댕기면서 [07:47] 지름길을 연결해야하거든.. [07:48] ㅋㅋㅋ [07:48] 각 정점들간의 거리 배열로 집어 놓고 하면 편할텐데;; [07:48] 아닌가요? ㅎㅎ [07:48] 일단 각 정점들간의 거리 먼저 계산했는데 저같은 경우는 ;; [07:48] 한 정점이, 두개 세개 연결될 수 있거든.. [07:48] 최소신장트리 구현하는 거라서.. [07:48] 아~ 그거였나요? ㅋㅋ [07:48] 그걸 프림이랑 크루스칼 알고리즘 둘다 구현해야돼. [07:49] 크루스칼은 나도 하루만에 구현햇는데, 프림은 아직도 답이 안나와 [07:49] 근데 일단 거리만 계산해 놓으면 n^2 이니까 나중에 더 편할텐데 ;; [07:49] ㅋㅋㅋ [07:49] ㅇㅇ 거리 계산이야, 그냥 펑션 만들어서 돌리면 되는데, [07:49] 나머지 정점을 탐색하고, 그 정점이랑 순환이 되는지 안되는지 여부도 파악해야해서... ㅎㅎ [07:50] 그러니까, [07:50] http://seowonjung.com/screenshots/ScreenShot2012-04-16at9.50.14PM.png [07:50] 이런 식이 아니라, [07:50] 프림 알고리즘 드려요? ㅋㅋ [07:51] 모든 vertex 가 연결되어 있다고 생각하고 계산하면 되는거 아닌가요? [07:51] http://seowonjung.com/screenshots/ScreenShot2012-04-16at9.51.05PM.png [07:51] 이런 식으로.. [07:51] ㅇㅇ [07:51] ㅋㅋ [07:51] 1이랑 10은 3개의 정점이 연결되어있잖아... [07:52] 근데, 단순히 그냥 연결이 되어있지 않은 정점만 따라다니다보면, [07:52] 최종적으로는 5와 6이 연결이 안돼 [07:52] 어쨌든 중요한 점은, 일단 나는 해결을 했어 ㅋㅋ [07:52] 다만 한 가지 문제는, 정점 100개짜리가 제대로 된 답이 안나와서 그렇지만.. ㅎㅎ [07:53] 원래는 프림 알고리즘이 연결된 정점을 찾아서 하는 건데 저건 모든 점이 연결 되 어 있다고 생각해서 그냥 최소거리 구하면 되는거 아닌가요? [07:53] 문제가 기억이 안나;; ㅋㅋ [07:54] 암튼 그건 다음기회에 ~ ㅋㅋ [07:54] ㅋㅋㅋ [07:54] 오케. [07:54] 암튼 오늘 고마워. [07:54] 뭐 필요한 거 있어? ㅋㅋ [07:54] ?? [07:55] 나 아는 동생이 하와이로 신혼여행 와있거든. [07:55] 그 편에 뭐 좀 보내줄까 ㅋㅋ [07:55] 아이맥은 너무 커서 안되겠지? ㅋㅋ [07:59] ㅋㅋㅋㅋㅋㅋㅋㅋㅋ [07:59] 아이맥~!~!~!~!~!~~! [07:59] ㅋㅋㅋ [07:59] 설겆이 하고 왔어요 ㅋㅋ [08:00] 아이맥을 쓰고 싶긴한데 ㅋㅋㅋ [08:00] 아옹;;; [08:00] 딴거 뭐 필요한 거 있어? ㅎㅎ [08:00] ㅇㅅㅇ [08:00] 아 나 잠시 와이프 픽업하러... 한 15분 후에 올거야 [08:00] 저도 [08:00] 아가씨가 필요해요 [08:00] ㅠ_ㅠ [08:00] 글세요~ ㅋㅋㅋ [08:00] imsu, 님 [08:00] 네~ ㅎㅎㅎ [08:00] 굽신굽신 [08:00] bluedusk, ?? [08:00] 저도 아가씨좀..; [08:00] 나도 없는;;;; ㅋㅋㅋ [08:11] hi [08:11] 어 아가씨 브로커 임수옹이시다ㅣ [08:11] 오 [08:11] 아가씨 븛로커! [08:16] ㅋㅋㅋㅋ [08:16] 노노 브로커 [08:16] breaker [08:16] zz [08:16] grr, 안녕하세요~ [08:16] imsu: 뭐 암튼 필요한 거 있어? ㅎㅎ [08:17] 오셨나보네 ㅋㅋ [08:17] Seony, 필요한게 너무 많아요 ㅋㅋ [08:17] 그래서 뭘 얘기해야할지 모르겠어요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ [08:17] ㅋㅋ [08:18] 내일 모레 중으로 얘기해 ㅎㅎ [08:18] 근데 필요한 게 뭐가 그리 많은데? [08:18] 일단 지갑을 얼마전에 잃어버렸고 ㅡ.ㅡ; [08:18] 흑흑 [08:19] 내가 봐서 지갑 하나 보내줄께 [08:19] 옹~!~! [08:19] 안쓰시는걸로~!~!~! ㅎㅎ [08:19] 사놓고 안쓰시는걸로~!~!~!~!!~!~ [08:19] 아니면 쓰시다 질리는걸로~!~!!~! [08:19] ㅋㅋ [08:20] 지금 쓰고있는 건 너무 바래서 안돼 ㅋㅋ [08:20] 에이~ 그럼 새로 사실 필요까지는 없는데요;; [08:20] 가죽크림으로 닦으면 된다던데, 그래도 너무 헌거야. [08:20] 이번에 봐서 ㅎㅎ [08:20] ㅋㅋㅋ [08:21] 안쓰시는 물건 있으면 환영입니다만;; 구입을 하신다면야;; 제가 뭐 이쁜 구석도 없는데;;;; ㅋㅋ [08:21] 아는 동생 낼모레 쇼핑몰 구경시켜줄껀데, [08:21] 그때 가서 보고 사줄께 [08:21] 헐;; [08:21] 노노노노~!~! [08:21] 지갑없어도되요~ ㅋㅋㅋ [08:22] ㅎㅎ 그러니까 암튼 가서 보고 결정할께 [08:22] ㅋㅋㅋㅋ [08:22] 네 안사시는 쪽으로 ㅋㅋㅋ [08:22] 걱정마. 사게되더라도 비싼 건 못사니까 ㅋㅋ [08:23] 전 누가 선물해준거 죄다 잃어버렸어요 그래서 안받을래요 ㅠ [08:23] 시계도? [08:23] 네 ㅡ.ㅡ; [08:23] 헐 [08:24] 그럼 먹는걸로 해다줄까 [08:24] ㅋㅋㅋㅋ [08:24] 시계는 어디서 잃어버렸는지 기억도 안나요 ㅠ [08:24] 죄송합니다 ㅠㅠ [08:24] ㅎㅎ 할수없지. [08:24] 원래 물건을 잘 잃어버리는갑네 [08:24] 술먹고 이럴 때 벗어놓는데 그 때 잃어버렸나 .ㅡ.ㅡ; [08:24] 휴대폰 빼곤;; ㅋㅋ [08:24] imsu: Hi [08:25] 휴대폰 안잃어버리는건 신기해요... 항상 방치해서 그런가 ㅡ.ㅡ; [08:25] 전파가 우리의 뇌를 이끕니다 [08:25] 지갑도 선물로 4번째 받은건데;; 또 잃어버렸어... ㅡ.ㅡ; [08:25] 나중에 디아블로나 같이하게 디아블로 사줄까 ㅋㅋ [08:26] ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ [08:26] 그건 저를 폐인으로 만들겠다는 말씀? ㅋㅋㅋㅋㅋ [08:26] ㅇㅅㅇ [08:26] imsu, 님 디아블로 3정도는 해주셔야 [08:26] 디아블로 돌아갈 pc 가 없네요 ㅋㅋㅋㅋㅋㅋㅋㅋ [08:26] ...... [08:26] 자 ㄲㄲ [08:26] pc도 기증해줄 기세 [08:26] Seony, 그러고보면 아이맥이 제일 필요하네요~ ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ [08:27] 디아블로를 위한 pc ㅋㅋ [08:27] bluedusk: 벌써 놋북 두대 줬어요 [08:27] ㅋㅋㅋㅋ [08:27] 한대는 안됨 ㅋㅋ [08:27] 놋북하드 하나 줏어야 하는데; ;ㅋㅋ [08:27] 그래? IBM? [08:27] 알아봐야징 ㅋㅋ [08:27] 네 [08:27] 그 때 부팅때 하드 불량이라고 메세지 뜬거같았어요 [08:27] 그거 원래 멀쩡하게 쓰던 건데... [08:27] 음... [08:27] 하드불량... [08:31] 부팅부터 안되더라구요 ㅋㅋ [08:31] 가져오면서 충격먹었나 ㅋㅋ [08:32] 흐... 그럴수도