디시인사이드 갤러리

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

갤러리 본문 영역

횽들 알고리즘 질문 하나만할께

늅늅이(220.68) 2011.03.30 16:18:55
조회 104 추천 0 댓글 13

오늘 연습 문제 풀면서 궁금해서 그런데

책에 있는 문제야

답을 알려달라는건 아니구 ㅋㅋ
횽들의 생각이나 힌트점 듣고 싶음


n개의 서로다른 정수(n은 짝수라고 가정해도 좋음)가 있을때 이 그룹을 반으로 쪼갠다.
나눠서 생긴 두개의 그룹을 A와 B라고 할때 A의 총합과 B의 총합의 차가 최소가 되게 코딩하라.

내가 생각한건 일단 원그룹을 작은수부터 차례대로 정렬시킨후에
2개씩 수를 묶어서
A의 총합이 작으면 하나를 A에넣고   그래도 A의 총합이 작으면 또 하나도 A에 넣고 (B의 총합이 작으면 나머지 하나는 B에)
B의 총합이 작으면 하나를 B에넣고   그래도 B의 총합이 작으면 또 하나도 B에 넣고 (A의 총합이 작으면 나머지 하나는 A에)

이런식으로 하면 일단 서로 n/2개의 원소를 가진 그룹이 되겠지만, 이게 최소차이는 아닌것 같더라구.그래서

A그룹의 첫번째부터 마지막까지를 B그룹의 처음부터 마지막까지 하나씩 비교해가면서 바꿔보고 차를 분석해서 차가 더 좁혀지면 서로 스위칭...

이렇게 짯는데 이거는 너무 비효율적인것 같애서.....

횽들의 생각을 듣고 싶음.


추천 비추천

0

고정닉 0

0

댓글 영역

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

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

갤러리 리스트
번호 제목 글쓴이 작성일 조회 추천
설문 흡연때문에 이미지 타격 입은 것 같은 스타는? 운영자 24/07/15 - -
이슈 [디시人터뷰] '좋아해요'로 마음을 사로잡은 배우 최하슬 운영자 24/07/17 - -
244535 double이 int보다 큰데 i=d가 왜됨? [3] 놀보(175.205) 11.04.13 56 0
244534 xna c샵 고수님들 제발제발제발 프갤뉴비좀 살려주세요 ㅠㅠ [3] 프갤뉴비(14.51) 11.04.13 48 0
244532 형변환은 작은타입에서 큰타입으로는 되고 큰타입에선 작은타입 안되나요? [3] 놀보(175.205) 11.04.13 50 0
244530 이바보 == 여자 : 사랑해 : 꺼져; [2] 잏힝(61.255) 11.04.13 72 0
244529 DirectX질문 - D3DFORMAT의 size얻는 메소드 아시는분? [1] 용책해골책(120.142) 11.04.13 49 0
244528 엄마랑 싸우고 문 쾅닫고 들어갔는대... [2] 천한플머(121.139) 11.04.13 99 0
244527 오픈소스로 한다음 컨설팅/용역/서어비스로 버는거지 [2] 잏힝(61.255) 11.04.13 66 0
244526 pow퇴er근 이다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! [2] McHello갤로그로 이동합니다. 11.04.13 88 0
244525 자료대로 EditPlus 2로 java로 프로그래잉 해주실수 있나요?ㅠ [3] 루팅왕(210.210) 11.04.13 68 0
244524 아 역시 예비창업자 또 떨어짐 [11] 분당살람갤로그로 이동합니다. 11.04.13 110 0
244523 src어셈블리 짜는거 도와주긔 ㅠㅠ.피보나치는 짯음!! [4] ㅇㅇ(122.34) 11.04.13 127 0
244522 명색이 프로그램 갤러리인데 농협사태에 대한 반응이 왜 전혀 없냐. [6] ㅇㅇㅇ(121.144) 11.04.13 298 0
244521 방금 sector변수명 준다는게 [1] McHello갤로그로 이동합니다. 11.04.13 72 0
244520 성공은 노력과 소망하는 마음만으로는 부족하다. 나야나(61.100) 11.04.13 31 0
244519 국내 SW 품질, '심각' 수준 [2] 1(121.182) 11.04.13 126 0
244518 멍청한놈이 컴공과에 지원하였습니다.... 테크트리좀 알려주세요 [9] 놀보(175.205) 11.04.13 231 0
244517 아 귀엽네 [1] SODmaster갤로그로 이동합니다. 11.04.13 84 0
244516 윈8 앱스토어???? 시불라미갤로그로 이동합니다. 11.04.13 69 0
244515 고정닉이 날아갔다는게 김트루? [4] URA!갤로그로 이동합니다. 11.04.13 62 0
244514 지금 디씨 접속 안되는 사람 없음???? ㅁㅁ(220.86) 11.04.13 37 0
244513 char과 int 크기 질문 ㅠ ㅁㄴㅇ(115.140) 11.04.13 168 0
244512 고수님들아 제가 xna로게임을 만들고 있는데 잘안되네요 도와주세요 ㅠㅠ [5] 핫빈(14.51) 11.04.13 74 0
244511 프갤러들 도와주시오 언패킹좀 3(116.34) 11.04.13 54 0
244510 야 나이거 왜 공지에 안넣어주냐 [2] ㅔㅕㅅㄷㄱ갤로그로 이동합니다. 11.04.13 75 0
244509 이번에 대회나가는데 C#에대해 모르는게있음..알려주세요 굇수분들 [11] 은야(14.51) 11.04.13 171 0
244508 면접보러 갈건데 연봉얼마 불르까 [3] 밍밍(61.255) 11.04.13 180 0
244507 파일 언패킹좀 해줄사람 [12] 3(116.34) 11.04.13 141 0
244506 프갤 옛날 짤방 [3] 반헤일런갤로그로 이동합니다. 11.04.13 123 0
244505 IT 취업교육받고 당당하게 취업하자구요.(오라클.자바.닷넷 등등) [2] 솔맨갤로그로 이동합니다. 11.04.13 141 0
244503 마소떡밥 success [3] SODmaster갤로그로 이동합니다. 11.04.13 87 0
244501 이 홈페이지에서 쓴 기술이 AJAX 맞아?? [3] angling(222.107) 11.04.13 179 0
244500 자바에서 JList를 초기화하고 새로 같은 자리에 넣는 방법 없나여? [5] Deanex(210.102) 11.04.13 6604 0
244499 한국에서 학부만 마치고 바로 미국 취업은 불가능에 수렴?? [11] 힘맨(220.126) 11.04.13 239 0
244498 진심으로 게임 컴퓨터 AI만드는거 [1] McHello갤로그로 이동합니다. 11.04.13 162 0
244497 2^0 != 1 이다 [2] 닌텐도DS갤로그로 이동합니다. 11.04.13 99 0
244496 형들아 어느게 더 잘짰어염 [5] 뇌자알갤로그로 이동합니다. 11.04.13 82 0
244493 형들 미디어플레이어 관련 프로그램만들고싶은데 [2] ㅇㅇ(112.159) 11.04.13 67 0
244492 마소가 망한다 굽쇼???? [2] 시불라미갤로그로 이동합니다. 11.04.13 122 0
244491 i=i+k 와 같은 표현은? [4] 우왕(220.149) 11.04.13 60 0
244490 어셈블리 짜는건데 하다가 어떻게 써야할지모르겠음.ㅠㅠ 도와주긔.. [7] 어셈블리(122.34) 11.04.13 80 0
244489 마소 윈도우는 쉽게 없어지진 않겠지만 분당살람갤로그로 이동합니다. 11.04.13 52 0
244488 SMS 건당 13원이나 드네 ㅅㅂ..무료서비스인데 밍밍(61.255) 11.04.13 58 0
244487 매틀랩 고수님?? [2] 새오갤로그로 이동합니다. 11.04.13 136 0
244486 엠씨헬로횽 [1] 캐닭(211.248) 11.04.13 42 0
244485 30만 카피정도 팔린게임 McHello갤로그로 이동합니다. 11.04.13 150 0
244484 마소는 망하진 않음 [5] 분당살람갤로그로 이동합니다. 11.04.13 90 0
244482 형들 [1] ㅁㄴㅇ(121.136) 11.04.13 26 0
244480 금주의 추천 도서 [1] 분당살람갤로그로 이동합니다. 11.04.13 101 0
244478 횽들...어떤 활동을 해야 올바른 게임문화를 만들 수 있을까??? [3] 오천원(121.159) 11.04.13 59 0
244477 명색이 코드짜서 먹고 사는 사람인데. [6] ByunJa갤로그로 이동합니다. 11.04.13 153 0
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

뉴스

디시미디어

디시이슈

1/2