헝가리안 알고리즘 소개

[성대아싸]

2011.02.19 22:52:21

조회 8267 추천 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) 까지 줄여놨데요 ㅇㅇ

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

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

고정닉 0

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	가족과 완벽하게 손절해야 할 것 같은 스타는?	운영자	24/06/24	-	-
236860	!!!!!!!!! ★형들 급함 급질문 [5]	유닉스입뉴비(211.232)	11.03.04	72	0
236859	니들 덕분에 흘겨보고 지나간 Java메모리 구조와.. 가비지컬렉터를 조사 [13]	음...(115.178)	11.03.04	415	0
236858	뒤도수 [2]	SODmaster	11.03.04	83	0
236857	제 47차 보안,해킹 세미나(실제 은행해킹용 웜 분석과 웹해킹)	gumpkim(125.129)	11.03.04	73	0
236856	별찍기 물결모양으로 하려하는데요 [2]	asdf(203.234)	11.03.04	133	0
236855	영어 드립 [3]	개드립(121.182)	11.03.04	137	0
236854	근데 영어 못읽는건 아님... [3]	꿀레(14.33)	11.03.04	90	0
236852	영어공부 하면서 느끼는 건데, [11]	Minryu	11.03.04	285	0
236850	졸작하는데 좀 고민되네. [3]	===(115.145)	11.03.04	238	0
236849	쌍용교육센터라고 알아?? [11]	쌍용(218.153)	11.03.04	268	0
236848	[내일배움카드제] 3월 국비지원 내일배움카드제(계좌제) 개설과목 안내 [3]	gumpkim(125.129)	11.03.04	76	0
236847	오오오오... 테트리스 블락이 막 떨어지는군 [6]	LibeRa	11.03.04	176	0
236846	프갤 눈팅하면서 느낀건데... [7]	개드립(121.182)	11.03.04	260	0
236845	프갤 눈팅하면서 느끼는 건데 [2]	ㅍㅌ	11.03.04	119	0
236843	횽들 facematch 같은건 어떻게 만드나요? [2]	Paradise	11.03.04	75	0
236842	디도스 공격왔엇네 [1]	ㅂㅈㄷㄱ(175.193)	11.03.04	146	0
236840	형들 형들은 졸작으로 어떤걸 했엉?? 리플로 뽐점 내줘 [4]	안숭(61.100)	11.03.04	194	0
236839	난 여태까지 영어공부 제대로 한 기억이 없는데 시험보면 잘침 [7]	ㅋ(211.222)	11.03.04	97	0
236838	이번에 복학하면서 진짜 프로그래밍 개 ㅈ도 모르고 시작했는데 [3]	우호앙(210.115)	11.03.04	154	0
236837	밤샜는데 잘수가 없다.. [6]	꿀레(14.33)	11.03.04	136	0
236836	영어징징이들 [8]	cyluss	11.03.04	165	0
236835	페북에 서식하는 프갤횽들 소환!!! [8]	은행강도	11.03.04	127	0
236833	컴파일러라는 과목에선 뭐 배움? [6]	하앍하앍(123.199)	11.03.04	149	0
236832	으아아아아아아아악 ! 영어 ! [5]	LibeRa	11.03.04	98	0
236830	입갤! 횽들 잘 지냈냐능! [14]	해일리	11.03.04	131	0
236829	하앍 컴파일러란 과목이 컴공4년제 나오면 중요한거임요? [3]	빡곰	11.03.04	181	0
236828	고정닉?	hideto.	11.03.04	33	0
236827	먹튀들은 검색이란것도 모르냐? [1]	일광면	11.03.04	162	0
236826	공부는 말야 어영부영 하는거야 [1]	별가사리(122.40)	11.03.04	123	0
236825	나처럼 새벽형 인간이 되라! [1]	계백(61.255)	11.03.04	87	0
236822	피방에서 파일구리 리버싱 하ㅇ는사람 봤다 [1]	3(116.34)	11.03.04	821	0
236821	자바 첨 공부하려고 하는데 책추천점! [1]	말코형	11.03.04	177	0
236820	글삭튀하는 마음 [1]	blackskirts	11.03.04	85	0
236819	어느새 시간이 벌써...	SODmaster	11.03.04	29	0
236815	ㅋㅋ 역시 글삭튀 [7]	clique	11.03.04	182	0
236813	에듀펜이라는 동영상강의 싸이트 괜찮어?? [1]	ㅇㅇ(175.195)	11.03.04	1085	0
236811	to 허허벌판 [22]	SODmaster	11.03.04	208	0
236809	컴공과 장래좀요 [7]	척척밥샙	11.03.04	221	0
236804	디비쪽은 신입 안 뽑나여 으헝?'ㅅ' [5]	풀개미'ㅅ'	11.03.03	173	0
236802	횽들 C#에서 인터페이스를 써볼려고 하는데 [11]	허허벌판	11.03.03	109	0
236801	횽들 질문하나만 봐줘요 [7]	qwerty(124.49)	11.03.03	86	0
236800	디씨 아파요? [5]	해일리	11.03.03	82	0
236799	프갤은 굉장히 현실적인것 같아여.ㅅ.	풀개미'ㅅ'	11.03.03	108	0
236798	[질문]tv도 공유기처럼 사용가능한가요 [7]	123(221.155)	11.03.03	61	0
236794	fps오류 [1]	ㅇㅇ(210.218)	11.03.03	65	0
236792	c#책 추천 부탁드립니당	후우(175.114)	11.03.03	126	0
236791	..아무래도 탈겔해야겠다 [1]	DMW(125.138)	11.03.03	69	0
236790	횽들 질문좀....	내바다	11.03.03	23	0
236789	SCJD 같은거 생각하고 계신 분 빨리 따세요 [1]	후시기바나(220.67)	11.03.03	75	0
236788	나같은 초보를 위한 winapi 안들어가져요 [1]	듣보킹	11.03.03	89	0