| 제목 | (n-1)! 짜리 알고리즘.. ㅠㅠ | ||
|---|---|---|---|
| 글쓴이 | 세콩 | 작성시각 | 2012/01/19 15:48:40 |
|
|
|||
|
아.... 너무 힘들어서 조언을 구할까 해서 글을 남깁니닷.. 초보개발자의 삽질의 방향을 제시해주십사... ㅠㅠㅠㅠㅠㅠㅠ ** 상황개요..** 사람들이 묶여있는 쌍으로된 배열에서 유니크한 쌍을 뽑으려고합니다. 예를들면 (철수, 영희) , (철수, 갑돌) , (영희, 말자), (말자, 희수), (길동, 지현) , ....................................... 이런식의 배열들이 있습니닷.. ( 각자리 모두 중복가능) 이중 2쌍을 뽑길원한다고 할때!! ( 실제로 n 개의 쌍을 뽑습니닷..) 올바른 예 : (철수, 영희) , (말자, 희수) // 모든 사람들이 중복되지않으면서 기존의 쌍을 유지하는경우 잘못된 예 : (철수, 영희), (영희, 말자) 등...... 올바른 예의 여집합... ** 문제점... ** 억지로 뽑아낼수는 있습니다.. 단... 알고리즘 복잡도가 (n-1)! 꼴이 되버려서....... 반복연산을 최소한으로 줄이고싶은데... 조언을 구해봅니닷... ps. 삽질 2일째 불쌍한 중생에게 따듯한 손길을........ㅠㅠㅠㅠㅠㅠㅠ 게시판 내용과 어울리지않으면 삭제하도록 하겠습니닷... |
|||
| 다음글 | 아래 글 보면서 갑자기 궁금해진건데요~ (4) | ||
| 이전글 | 외국에서의 접속속도 테스트 (8) | ||
|
변종원(웅파)
/
2012/01/19 17:10:21 /
추천
0
|
|
milosz
/
2012/01/19 18:24:17 /
추천
0
1. 전체를 shuffle 한다.
2. 최종배열, 확인배열 = array(), i=0; while( i < 추출갯수 ){ 3. 임시배열 = array_shift(전체배열) 4. err = false; foreach(임시배열){ 5. 확인배열에 임시배열에 값이 있는지 확인 6. 있으면 err = true; 7. 없으면 확인배열에 array_push } if( err == false ){ 8. 최종배열에 array_push 9. i++ } } 이러면 원하는 만큼만 뽑고 끝낼 수 있을거 같아요... 복잡하긴 한데; |
|
양승현
/
2012/01/19 18:29:22 /
추천
0
1. 각 배열을 루프돌면서 하는방법..
2. 웅파님 말씀대로 한번에 왕창 합쳐서 하는방법.. in_array로 체크하면서 배열을 생성해 나가면 될듯.. 뭐 이런건 이미 아실듯.. ㅋㅋ 전 자바스크립트속을 헤엄치고 있어서 ㅜ.ㅜ |
|
배불뚝이
/
2012/01/19 20:45:59 /
추천
0
$names= array( array('aa','bb'), array('cc','bb'), array('dd','ee'), array('aa','dd'), array('ff','gg'), array('hh','bb') ); $selected= array(); $result= array(); foreach($names as $name){ if( isset( $selected[$name[0]]) || isset( $selected[$name[1]]) ){ continue; } $selected[$name[0]]=1; $selected[$name[1]]=1; $result[]= $name; } 아이디어 적어볼까 하다가 이런저런거 다 빼버리고 간단히 코딩해보았습니다. 조건이나 상황에 적합한지 모르겠네요 ^^; |
|
한대승(불의회상)
/
2012/01/19 21:12:16 /
추천
0
앗.. 갑자기 포럼에서 study 분위기!!!!!
|
|
타로
/
2012/01/19 23:32:16 /
추천
0
왠지 무섭기까지.. ㅋㅋ
|
|
세콩
/
2012/01/20 10:37:50 /
추천
0
우왕굳~ 감사합니다
덕분에 문제를 해결하였습니닷~!! 로직을 만들어서 실행해보았는데 5만개의 배열에서 5천개 뽑으니까 5초 걸리네요 하앜 1만개뽑으면 20초 걸리고.. 하앜 ㅋㅋㅋ (사실 표본 5만개에서 뽑는 개수 맥시멈을 천개잡고 1초걸리니 만족합니닷!!) ps) 시간날때 위 예제들만들어서 다양하게 만들어보고 비교해봐야겠어요~ |
|
변종원(웅파)
/
2012/01/20 13:08:30 /
추천
0
바람직한 방향입니다. ㅎㅎ
|
|
들국화
/
2012/01/26 11:55:21 /
추천
0
음... 유니크한 값을 랜덤하게 뽑는 로직 같은데요..
같은 사람 배열을 두개 변수에 담습니다. a 배열에 랜덤한 위치를 뽑아내 담고 a배열에서 버립니다. b위치에 같은 위치의 값을 버립니다. 그리고 랜덤한 위치나 a의 위치에서 일정값을 더한 위치의 b의 배열에서 추출해 담습니다. 이 과정을 필요한 갯수만큼 반복하는게 빠를듯 하네요. |
1. 기본배열을 합치고 유니크한 이름만 뽑아낸다.
새배열 = array(철수, 영희, 말자, 희수)
2. 새배열로 for문 돌리면서 첫번째 값인 철수에 대해 다시 for문 돌린다.
안쪽의 for문에서는 철수를 제외한 영희, 말자, 희수를 가지고 돌리는데
철수를 제외한 첫번째 값이 영희이므로
(철수, 영희) 또는 (영희, 철수) 로 기본배열에서 검색하여 카운트를 잡는데
첫번째 그런 경우가 나오면 +1 하고 그 카운트가 1 이후인 것은 기본배열에서 삭제한다.
이정도면 될거 같은데요?
오류나 더 좋은 아이디어 있으시면 올려주세요. ^^