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

늅늅이(220.68) 2011.03.30 16:18:55

조회 105 추천 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개

등록순

본문 보기

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

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	흡연때문에 이미지 타격 입은 것 같은 스타는?	운영자	24/07/15	-	-
245145	it횽들 절 채용하시면 주식하는데 도움이 되실거에여 으헝'ㅅ' [4]	풀개미'ㅅ'	11.04.15	93	0
245144	프갤 분위기 많이 바뀌었네여 으헝'ㅅ' [3]	풀개미'ㅅ'	11.04.15	94	0
245143	보이어-무어 알고리즘 아는사람 없음? [1]	11(121.172)	11.04.15	871	0
245142	FLOWCHART 그리는 재밋는 문제임 형아들도 심심하면해보셈 [3]	ㅎㅎ(112.222)	11.04.15	92	0
245141	친구놈이 아이폰APP배우고나서 대기업들갔는대 어케생각? [1]	ㅇㅇ(211.181)	11.04.15	112	0
245138	근데 다음 포인터 연산을 설명하시오..이렇게 되있는데 그림으로 해도 됨? [1]	ㅇㅇㅇㅇㅇ(210.117)	11.04.15	74	0
245137	형들 이런거 배울라면 6개월잡으면 충분히 전문가수준될까?? [4]	ㅇ(211.181)	11.04.15	145	0
245136	c언어 초보입니다 질문좀 하겠습니다 [2]	4143(125.130)	11.04.15	54	0
245135	외계달팽횽 감사 그런데... [7]	SODmaster	11.04.15	100	0
245134	그니까 p=p.link를 말로 설명하기가 거지같아서 문제인거임; [1]	ㅇㅇㅇㅇㅇ(210.117)	11.04.15	72	0
245133	C 아주 간단한 질문좀요 [5]	공대생(122.43)	11.04.15	59	0
245132	형들☆ 목욕탕에서 수도꼭지 보다가 든 생각인데 [2]	로레알	11.04.15	118	0
245130	작성한 c나 cpp파일을 asm 코드로 볼려면 어떤 기능을 써야되나요? [2]	공도리(61.75)	11.04.15	60	0
245129	제가 xna c#으로 두더지 잡기 게임 만들고 있는데 도와주세요	으아앙(14.51)	11.04.15	715	0
245128	안드로이드 어려워여 으헝'ㅅ' [8]	풀개미'ㅅ'	11.04.15	137	0
245127	PostMessage 직접 해 봤는데... [8]	SODmaster	11.04.15	107	0
245125	아 ㅅㅂ 리눅스 [1]	풋사과1	11.04.15	74	0
245124	아 c 배열땜에 돌아버리겠음 ㅠㅠ [2]	어린화공	11.04.15	87	0
245123	회사횽들 절 뽑아주시면 휫자쿠폰이 딸려옵니다 으헝'ㅅ' [4]	풀개미'ㅅ'	11.04.15	78	0
245122	WINAPI에서 갑자기 급궁금한게 생겼는데 [3]	SODmaster	11.04.15	98	0
245121	자료구조인데...p=p.link를 어떻게 설명해야하는거야?	ㅇㅇㅇㅇ(210.117)	11.04.15	94	0
245119	it업계에 대기업 3대 막장이 있다는데 어디어디에여?'ㅅ' [7]	풀개미'ㅅ'	11.04.15	1230	0
245118	ㅅㅂ 근데 it 는 진짜 실무 수업 과외몇번받으면 연봉 쫙쫙오를텐데 [1]	풋사과1	11.04.15	121	0
245117	TLP 라는 듣보잡스런 용어가 있다．이것은	때릴꺼야?(119.67)	11.04.15	71	0
245114	프갤도 이제 한계에 이르렀다. [3]	천한플머(61.77)	11.04.15	135	0
245113	형들아 ㅋㅋㅋㅋㅋㅋㅋ 삭니 알지? 삭니 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ [4]	형들아(14.41)	11.04.15	112	0
245112	c 간단한 질문좀용~ [1]	어린화공	11.04.15	37	0
245111	1	미스에이	11.04.15	67	0
245110	1	미스에이	11.04.15	156	1
245107	정말 당당하고 멋있게 발표하는 방법없을까? [4]	난정말찐따(175.205)	11.04.15	89	0
245106	형들 쿼리문 질문!! [3]	rails	11.04.15	65	0
245105	25살 [2]	스티브 짭스	11.04.15	113	0
245104	기자들 진짜 쉽게 돈번다 [4]	김조루(219.251)	11.04.15	175	0
245101	게임은 영업수익률이 진리인 거 같다. [2]	던전파(222.107)	11.04.15	144	0
245100	이번 농협 해킹 도대체 어떻게 일어난거임? [2]	호(110.5)	11.04.15	401	0
245098	형들 도와줘서 고마워..일단 지금 2개했다.. [3]	초코맛초코	11.04.15	98	0
245097	void main() 이랑 int main() 이랑 [11]	균느	11.04.15	136	0
245096	형들아 내친구가 [1]	스티브 짭스	11.04.15	81	0
245094	프갤에 숙제물어보는 대학생 형들아 [3]	McHello	11.04.15	150	0
245093	펀더멘탈 보고잇자니 철학시간이 떠오른다 [1]	ㄹㅇㄴ(210.178)	11.04.15	49	0
245091	파일버스 포인트핵입니다. [3]	test010	11.04.15	775	0
245090	글삭하지마 내 댓글이 줄어들잖아 [9]	자취생੦ܫ੦	11.04.15	66	0
245089	농협 서버 리셋된거 그럼 내꺼 돈은 어떻게 됨? [4]	ㅎ(211.198)	11.04.15	175	0
245087	초보가 묻슴당. [4]	균느	11.04.15	76	0
245083	C언어에서 유니코드 [1]	자취생੦ܫ੦	11.04.15	79	0
245082	게시판 질문좀 [1]	ㄹㅇㄴ(210.178)	11.04.15	58	0
245081	프리섭렉폭발하게만들어주실분 [4]	ddd(119.201)	11.04.15	121	0
245079	물어볼게 있어서 글 적습니다. [13]	1234(58.141)	11.04.15	113	0
245077	농협 사태는 앞으로의 대한민국에 일주일에 한번씩은 있어야 할 것 같다. [5]	ㅇㅇ(222.107)	11.04.15	296	0
245076	xna c#을 이용하여 게임만들기 고수님들의 도움이 레알필요함..ㅠㅠ	지나가던뉴비(14.51)	11.04.15	59	0