통계가 좋아 ^ㅅ^

그래프에 대한 기초적인 지식은 생략 최소비용흐름과 최단경로문제는 같은 문제이고 최대 흐름 문제는 조금 다르다 (책에서는 같다고 설명 되어 있는데 이건 좀 어거지임 내가 봤을 때) 최소비용 흐름 = 최단경로 문제 경로의 비용을 경로의 거리와 동일하게 생각하면 됨 . 이때 우리는 최단경로문제를 푸는 알고리즘을 배웠음 다익스트라 알고리즘임 다익스트라 알고리즘을 사용하기 위해선 조건이 있음. 모든 마디 (edge) 의 값 (최단경로 문제에서는 거리, 최소비용 흐름 문제에서는 비용) 이 0보다 커야한다는 것임 (0이 되는지는 좀 더 생각해봐야함) 다익스트라 알고리즘이 어떻게 진행되는지는 잘 알거니까 넘어가고 다익스트라가 최단경로문제를 해결하기 위한 알고리즘이란걸 상기하고 넘어가자. 만약에 edge의 값이 음수가 ..

비선형계획법.. 우선 알고가야할 것들은 1. 기울기 벡터 - 함수값을 최대화 하는 방향이다 = 목적함수 값을 개선하는 방향이다. 2. 라그랑주 승수법 3. feasiblility 자 시작하자 목적함수와 제약식가 linear 하지 않고 non - linear 일 때를 뜻하죠 . 난 공학미적분학2를 안 들어서 최대최소 하면 미분해서 0하거나 산술기하 정도밖에 몰랐는데 내가 고등학교 1학년때 오픈채팅 수학방에서 이런저런 문제풀이하는 걸 구경한 적이 있음 . 그때 어떤 초딩새끼가 어디 KMO 같은데 나갈 법한 새끼가 하나 있었는데 뭔 라그랑주 승수법이니 ㅈㄹ해서 찾아봤다가 람다 기호 보고 도망갔던 기억이 있음 여튼 최대최소 >> 최대화 하거나 최소화 한다 >> 최적화 문제라고 해석 가능함 non -linear ..

선형계획법 기억나지? 선형이 뭐야. 일차함수잖아. 제약식도 일차함수고, 목적함수도 일자함수여서 계산하기가 쉽다고 했잖아. 우리 수능 수학 공부 좀 했으면 "특수한 케이스가 답이다" 라는 건 익숙할거고 그래서 제약식의 교점에서 답이 나올거라곤 알고 있고 . 근데 이제 모든 교점에서 최적해라면 그건 말이 안 되잖아 값이 다 다를텐데 사실 그건 로컬최적해였던거지. 국지최적해라고 하는게 낫겠다 여튼 그것들이 사실 전역최적해의 후보들이란거지 이러한 개념을 가지고 한번 들어가보자 정수계획법이 뭐야? 제약식에 "정수조건" 이 들어간 거 뿐이지 이거 제약식은 함수인데 그럼 연속적이란 소리고. 정수조건이 포함되어 버리면 결국 제약식을 만족하는 범위 안에 존재하는 정수들을 전부 조사해보는 수 밖엔 답이 없다. 이걸 푸는 ..

최소비용 "흐름" 문제이다. 최소 비용으로 물건을 운반해야하는데, 제약조건에 흐름의 양 이란 것이 추가된 거라고 이해하면 된다. s 에서 t 까지 물을 5만리터 보내고 싶은데, 경로가 다양하고, 그 경로는 배수관의 사이즈가 제각각인 상황이다. 이때 물 1리터를 그 배수관을 통해 보낼려면 비용이 x만큼 든다는 것임. 근데 마을에서 쓰는 물이 3이라고 치면 들어오는 물이 7일때 나가는 물이 5면 쓸 수 있는 물은 2니까 말이 안 되잖아 그러니까 쓰는 들어오는 물 7 이면 나가는 물은 3만 가능하다. 라는 조건도 추가되는거임 이게 vertex 의 균형을 유지한다 라고 표현함 . 정리하자면 1. vertex의 균형을 유지하면서 2. 흐름의 양을 조절하는데 3. 최소비용을 만들어야한다. 1과 2는 무조건 만족해야..