디시인사이드 갤러리

갤러리 이슈박스, 최근방문 갤러리

갤러리 본문 영역

헝가리안 알고리즘 소개

[성대아싸]갤로그로 이동합니다. 2011.02.19 22:52:21
조회 8268 추천 0 댓글 1


n by n 행렬이 있고 거기에는 값들이 막 들어가 있는데요

행과, 열을 중복되지 않게 선택하면서

선택한 값들의 합이 최대값 (혹은 최소값)을 지니도록 선택해야 하는 문제를

정합문제 라고 해연


이걸 brute force로 풀면

처음 row 에서 n개 중에 하나 고르고, 
두번째 row에서 n-1개 중에 하나 고르고,
세번째 row에서 n-2개 중에 하나 고르고,
..
..
..
마지막 row에서 1개를 선택

계속 계산해서 모든 경우중에 최적해를 찾죠

시간복잡도는 O(n!) 이라는 어마어마한 크기임



하지만 헝가리안 알고리즘을 사용하면 

이거슬 O(n^3)으로 줄여줌

굉장히 유용한거 같은데요


비록 대학교 알고리즘 시간에 안나오겠지만;;

introduction to algorithms 에도 안나옴 ㅋㅋ


알아두면 써먹을 데가 많을거 같아 소개함


그냥 있다는거만 알고, 구현하기 귀찬은 분들한테는

이 알고리즘 라이브러리에도 들어가 있대요 (이름을 까먹었음 ㅠ)

Lap 으로 검색하시믄 라이브러리 있을거에연 

최근 연구에서는 O(log(n)*n^2) 까지 줄여놨데요 ㅇㅇ




아래는 굉장히 개념에 충실하여 제가 구현한 코드임

<meta http-equiv="content-type" content="text/html; charset=utf-8">http://codepad.org/k4MhfHJg



원래 주석 잘 안쓰는데 제출용이라 ㅋㅋ 남발했음









추천 비추천

0

고정닉 0

0

댓글 영역

전체 댓글 0
등록순정렬 기준선택
본문 보기

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

갤러리 리스트
번호 제목 글쓴이 작성일 조회 추천
설문 가족과 완벽하게 손절해야 할 것 같은 스타는? 운영자 24/06/24 - -
236487 아이유 다이어리를 샀다. [4] 유리한갤로그로 이동합니다. 11.03.01 279 0
236485 대학생 갤러많아여?? + 질문 [5] ㅠㅠㅁㅇ(211.212) 11.03.01 123 0
236484 정보통신공학과에 입학하게됬는데영ㅠ_ㅠ [5] d(220.78) 11.03.01 135 0
236483 프로그래밍 관련 업종 일을 하고싶은데 [2] 프그밍(180.230) 11.03.01 92 0
236482 야 정보보안전문가 이거 정보컴퓨터공학부에 속해 있는거냐? 힙합청각장애(175.210) 11.03.01 115 0
236481 왜 개발자들은 다 이클립스 글자를 작게 해놓고 함 ??? [4] 미츠도모에갤로그로 이동합니다. 11.03.01 184 0
236480 이거 언젠가는 터질려나?? [3] SODmaster갤로그로 이동합니다. 11.03.01 133 0
236477 혹시 개정판 열혈 TCP/IP책 읽는분 계신가요? 콩가루군(180.68) 11.03.01 93 0
236474 IT대학 하면(정보보안) [3] 힙합청각장애(175.210) 11.03.01 243 0
236473 즐겁지 않으면 프로그래밍이 아니다. [3] 천재플머(61.77) 11.03.01 190 0
236472 열혈C 플그래밍 드뎌 챕터10 도전 문제 풀고있는데요 [4] 늦깍이(123.199) 11.03.01 116 0
236471 형들 질문 하나만 더할게 ... [2] 아망했다..(121.185) 11.03.01 114 0
236470 이런개같은오라클 ocm 보유하고있는 형들있어? [2] 후플(61.100) 11.03.01 149 0
236468 php 언어를 공부하면 소셜네트워크 사이트 만들수있나요??? [5] (211.243) 11.03.01 161 0
236467 형들은 코드 쓸 때 머 쓰심? [5] 트럼프조커갤로그로 이동합니다. 11.03.01 214 0
236466 1년전에 만들었던거 . . [3] 온순한감자갤로그로 이동합니다. 11.03.01 128 0
236465 프갤 횽들 안녕!! [3] 프로햄갤로그로 이동합니다. 11.03.01 85 0
236463 수학.... 이거어떻게 계산하지... [6] 주방아가씨갤로그로 이동합니다. 11.03.01 223 0
236462 프갤러들을 위한 천재플머 강의 - 천재플머 명언 - [5] 천재플머(61.77) 11.03.01 238 0
236461 솔루션에서 여러개의 프로젝트가 있는게 궁금해서 질문드립니다 [8] 배틀멧돼지갤로그로 이동합니다. 11.03.01 123 0
236460 컴퓨터계의 여신 [5] 풋사과1갤로그로 이동합니다. 11.03.01 328 0
236458 엌... 멕시카나 [4] SODmaster갤로그로 이동합니다. 11.03.01 151 0
236457 중고딩용 테크트리 [1] 시불라미갤로그로 이동합니다. 11.03.01 275 0
236456 우리나라 한글 2벌식 문제가 많다. [8] ㅇㅇ(119.71) 11.03.01 179 0
236455 횽들 나 이제 고1인데 프로그래밍 하려면 c부터 책사서 해야하남? [6] 개념없는초보(61.85) 11.03.01 130 0
236454 정보보안전문가랑 정보보호전문가 [2] 힙합청각장애(175.210) 11.03.01 142 0
236453 임베디드 S/W에 관해 질문 [13] 드로제닉갤로그로 이동합니다. 11.03.01 220 0
236452 혹시 1000000! 계산결과 아는사람있나여?? [2] 10000팩(122.202) 11.03.01 120 0
236451 늅늅이 프갤러들을 위한 천재플머의 절규 - 천재플머 명언 - [4] 천재플머(61.77) 11.03.01 137 0
236450 도와주세요 횽들 ㅠㅠ [1] 횽들 헬미!!(121.64) 11.03.01 71 0
236448 질문 하나만 해도 되남여 형들 [8] 좆병신(121.181) 11.03.01 107 0
236447 횽들 새내기 데탑살건데 어때? [5] 기숙사들어감(121.185) 11.03.01 139 0
236445 SQL 공부할려구 하는데 [3] 한강구조견(118.37) 11.03.01 129 0
236444 너의 인생을 종결시켜주마 [6] 꿀레(14.33) 11.03.01 239 0
236443 그동안 인터넷이 안됬어 [2] elwlwlwk갤로그로 이동합니다. 11.03.01 103 0
236442 C는 내 마음의 안식처 [6] elwlwlwk갤로그로 이동합니다. 11.03.01 247 0
236441 디버깅은 재밌어 [1] elwlwlwk갤로그로 이동합니다. 11.03.01 105 0
236439 내일이면 복학이구나... 꿀레(14.33) 11.03.01 54 0
236438 스맛폰 앱은 과도기적인거야 [3] 계백(61.255) 11.03.01 157 0
236437 분당살람 형 봅니다. [3] 천재플머(61.77) 11.03.01 121 0
236436 형들 나 진짜 고민이 있어 [7] 유동(180.69) 11.03.01 127 0
236434 퇴사하고 싶다니까 오만소리 다한다 [3] ㅁㅁㄴㅇ(112.153) 11.03.01 152 0
236432 프로그래밍 입문?? [4] 코코낫뜨(121.141) 11.03.01 177 0
236431 [공지] 천재플머의 격한 감정에 의한 헛소리를 정정합니다. [2] 천재플머(61.77) 11.03.01 249 0
236430 프로그램에서 트위터에 글 쓰게 하려고 하는데 [3] 준치◕‿◕갤로그로 이동합니다. 11.03.01 95 0
236429 mysql 정렬후에 where 쓰고싶은데 어떻게해야해? [1] 으앙(175.115) 11.03.01 89 0
236428 이직하는 거 어려움? [2] 하앍하앍(123.199) 11.03.01 111 0
236427 이 짤빵을 보고 갑자기 민류횽이 생각 났음.. [1] seta(27.117) 11.03.01 147 0
236426 제로보드XE로 계식판등등 설정좀해주실분 [1] 박구갤로그로 이동합니다. 11.03.01 107 0
236424 IT맨의 사직서이후 이바닥 사정좀 좋아졌음?? [1] ㅁㄴㅇ(175.198) 11.03.01 159 0
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

뉴스

디시미디어

디시이슈

1/2