cardbt   1년 전

안녕하세요.

어제 로그인을 하니 대회에 빨간 1이 딱 떠있길래 들어가봤습니다.

아직 알고리즘 공부한지가 얼마 안됐지만 해보고 싶은 마음에 문제를 봤는데요.


처음에는 이분매칭인가? 하고 생각해봤는데, 이분매칭은 아닌거 같더군요.


이렇게 저렇게 짱구를 굴려봤지만, 도무지 해결책이 나오지 않아, 최소비용 관련 알고리즘을 찾아봤습니다.


가장 적합해 보이는 알고리즘이 헝가리안 알고리즘인것 같더라구요.

그래서 보기 시작했는데, 생각보다 어렵네요.


http://www.hungarianalgorithm....

위 싸이트에 헝가리안 알고리즘에 대한 설명이 나와있는데, 너무 러프하게 설명이 되어 있어서 어떻게 코드로 적용시켜야 할지 막막하네요.


좀더 코드 친화적인(?) 설명 사이트가 없을까요?

jwg8679   1년 전

헝가리안 맞는 거 같아요.

https://www.topcoder.com/commu...

탑코더에 잘 나와있네요

근데 오리지널 알고리즘은 N^4 라 500개를 통과 못할 같고요

N^3 짜리가 있다고는 하는데 500의 3승은 0.5초를 절대 통과 못합니다...

그런 걸로 봐서는 헝가리안이 아닌가 싶기도 하고 인풋이 루즈하게 들어오는건지 모르겟네요 ㄷㄷ

cardbt   1년 전

네 저도 찾아보니 헝가리안이 N^3으로 된다는데, 아무리 짱구를 굴려도 N^3짜릴 못 짜겠더라고요.

알려주신 링크 보고 참고하도록 하겠습니다.


그나저나 헝가리안이 안된다니... 더 막막해졌군요.



chan4928   1년 전

N^3 헝가리안을 목적으로 낸 문제인 것 같습니다.

아마 통과 될 겁니다.

baekjoon   1년 전

N^3은 0.5초를 통과할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.