디시인사이드 갤러리

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

갤러리 본문 영역

그리디 문제 증명 교환논증에 대해서 생각해봤음..

ㅇㅇ(75.6) 2021.09.29 12:26:34
조회 46 추천 0 댓글 5
														


24b0d121e09c28a8699fe8b115ef046c69f7204f9b


1.


문제는 대략 이럼..


슈퍼컴에서 p시간동안 전처리를 한 다음에 개인컴에서 f시간동안 후처리를 하는 작업J들이 여러개있는데


슈퍼컴은 한번에 하나의 작업만 수행할수 있고 개인컴은 동시에 여러개의 작업들을 수행할수 있음.


가장 빠르게 모든 작업을 처리할수 있는 스케쥴을 짜자~! 이건데


2.


어차피 슈퍼컴은 한번에 하나만 처리하니까 슈퍼컴이 모든작업을 끝내는데 필요한 시간은 정해져있고


중요한건 개인컴이 병렬처리를 하니 오래걸리는 작업을 최대한 일찍 줘야 빨리 끝나는거같음


그래서 최적 알고리즘은 f 시간이 높은순으로 작업을 정렬해서 컴터에 넣는다 << 면 되는듯




24b0d121e09c28a8699fe8b115ef046c65f22d4994


3.


증명은 최적인 스케쥴 G가 있고 G가 아닌 무작위 스케쥴 S가 있을때


S에서 붙어있는 작업 J1, J2에 대해서

뒤에 처리되는 작업 J2의 f 처리시간이 J1보다 클 경우

두 작업의 순서를 바꾸면 최종 종료시간이 줄어든 새로운 스케쥴 S`가 만들어짐



24b0d121e09c28a8699fe8b115ef046f5e49919baa


4. 그리고 이 교환을 무현반복하면 

f가 작은순으로 정렬된 스케쥴이 나오면서 이 스케쥴은 그 어떤 다른 스케쥴보다도 절대 더 큰 완료시간을 가지고있지 않음

따라서 이게 최적해임




어떰?? 이정도면 충분히 말이 되는 증명임???



추천 비추천

0

고정닉 0

0

댓글 영역

전체 댓글 0
본문 보기

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

갤러리 리스트
번호 제목 글쓴이 작성일 조회 추천
설문 현역으로 군대 안 간게 의아한 스타는? 운영자 25/06/30 - -
AD 휴대폰 바꿀까? 특가 구매 찬스! 운영자 25/07/02 - -
1894830 약육강식이 맞냐 ㅇㅇㅇ(211.245) 21.09.29 30 0
1894827 국비 바리스타도있던데 ㅇㅇ(117.111) 21.09.29 32 0
1894826 나 국비 이제 2달차인데 수업안듣고 백준풀었음ㅋㅅㅋ [5] ㅇㅇ(218.38) 21.09.29 190 1
1894825 나 이제 담배끊으려구 ㅇㅇ(59.11) 21.09.29 29 0
1894824 버튼에 이벤트 달아놨는데 병신됨 ㅇㅅㅇ [4] ㅇㅅㅇ(223.33) 21.09.29 73 0
1894823 나 국비다닐때 친구없어서 혼밥했음 [1] ㅇㅇ(211.55) 21.09.29 95 0
1894821 굮삐나와서 사수있는 웹개발 SI 들어가기 불가능이냐? [1] ㅇㅇ(116.125) 21.09.29 73 0
1894820 오랜만에 오랫동안 걸으니까 토할 것 같음 [1] 시계누나갤로그로 이동합니다. 21.09.29 54 0
1894818 요기요 파바할인 존나쩌네 ㅋㅋ(223.33) 21.09.29 28 0
1894817 타일러권 사업망해도 제시카랑 이혼안할까? 헬마스터갤로그로 이동합니다. 21.09.29 25 0
1894814 hwp파일은 어떻게보냐? [6] 헬마스터갤로그로 이동합니다. 21.09.29 82 1
1894813 주가 현황 [1] 길나그네(223.39) 21.09.29 43 0
1894812 당연히 프갤이라 그렇게 얘기하는거겠지만 국비=프로그래밍은 아니지 [3] ㅇㅇ(121.151) 21.09.29 84 0
1894810 국비 온라인듣는데 인사박는애는 뭐냐?? [3] ㅋㅋ(223.33) 21.09.29 129 0
1894809 아 국비 4달차인데 형변환 질문 아직도 하는사람있네 ㅋㅋ [6] ㅇㅇ(14.42) 21.09.29 93 1
1894807 엉엉 울었어 캠벨수프후루룩갤로그로 이동합니다. 21.09.29 25 0
1894805 남이짠코드 보는게정말고역이다 ㅇㅇ(223.33) 21.09.29 38 0
1894803 개발자로 진로 바꿨는데 국비 교육 들으면 좀 낫냐? [1] 천상여신유카리갤로그로 이동합니다. 21.09.29 76 0
1894802 근데 나이들고 국비가니까 재미있더라 [2] ㅇㅇ(211.111) 21.09.29 137 0
1894801 신입인데, 인사담당자한테 메일 보낼 때 팁 같은거 있냐? [6] ㅇㅇ(1.235) 21.09.29 63 0
1894799 vue도 리액트 네이티브 같은거 있어요? [1] ㅇㅇ(2.58) 21.09.29 75 0
1894798 국비 첫날이다 [4] 아랑소드갤로그로 이동합니다. 21.09.29 154 0
1894797 포큐 라이브하더라 [1] 헬마스터갤로그로 이동합니다. 21.09.29 45 0
1894796 뭐가 잘못된걸까요 ㅠㅠㅠ 자바 코린이입니다.. [5] 코린이(211.58) 21.09.29 60 0
1894795 애들아 지금 활성화되어 있는 프로그램 알아내서 웹으로 쏠 수 있냐 ? [6] ㅇㅇ(168.131) 21.09.29 42 0
1894794 알트탭 단축키 잠그는 방법 없음? [4] ㅇㅇ(183.99) 21.09.29 39 0
1894793 오늘부터 스프링 다시 빢공한다; 2주 놀아버렸네 ㅇㅇ(168.131) 21.09.29 27 0
1894791 형들 섹션 이동할때 ㅇㅇ(106.102) 21.09.29 16 0
1894790 CSS 개씹고수만 들어와 [7] ㅇㅇ(221.151) 21.09.29 88 0
1894789 C# 문법책 하나 간단한거 추천좀 [1] ㅇㅇ(168.131) 21.09.29 44 0
1894786 백엔드 프론트엔드 [1] ㅇㅇ(211.178) 21.09.29 76 0
1894784 스프링 코드가 가독성이 좋다는데 맞음?? [1] 수크라제갤로그로 이동합니다. 21.09.29 50 0
1894782 대기업 면접 정장입고 하냐? ㅇㅇ(183.106) 21.09.29 33 0
1894781 골프스크립트 레전드네 ㅇㅇ(211.111) 21.09.29 67 0
1894780 아스키코드 스펠링이 너무 어려워 [1] ㅇㅇ(211.111) 21.09.29 50 0
1894779 귀여운게 죄냐!? [6] 캠벨수프후루룩갤로그로 이동합니다. 21.09.29 49 1
1894778 형1아들 씨플도gui프로그램 짤 수 있나요 [6] ㅇㅇ(118.235) 21.09.29 79 0
1894777 vue는 리액트에 비빌 수 없나요 [2] ㅇㅇ(93.177) 21.09.29 122 0
1894775 3년차에 직급 뭐였음? 교묘함갤로그로 이동합니다. 21.09.29 39 0
1894773 졸릴땐 참지말고 자야하는듯 [4] ecko갤로그로 이동합니다. 21.09.29 51 0
1894771 vscode 익스텐션 오지게 다운받으면 어케됨? [3] ㅇㅇ(39.7) 21.09.29 46 0
1894770 층간소음으로 아래층에서 자꾸 민원 들어옴 [2] ㅇㅇ(106.101) 21.09.29 51 0
1894769 아니 솔직히 씨샵이 미래임 [2] 릴다희갤로그로 이동합니다. 21.09.29 70 0
1894768 솔근좌 한결같아서 호감 [3] 릴다희갤로그로 이동합니다. 21.09.29 64 0
1894766 솔근이가 나를 좆샵의 길로 인도했음 ㅇㅅㅇ [2] ㅇㅇ(1.244) 21.09.29 73 0
1894764 아 백신 개짜증나네 ㅇㅇ(211.111) 21.09.29 22 0
1894763 쿼리 질문점 [1] 23ㅇ(1.227) 21.09.29 37 0
1894762 실시간으로 좆되는중임 [3] ㅇㅇ(118.235) 21.09.29 82 0
1894760 국비 조별과제 들어갔는데 하는사람만하네 [1] ㅇㅇ(121.140) 21.09.29 79 0
1894759 일주일 연속 딸쳤더니 힘이 존나 없네 [3] ㅇㅇ(1.244) 21.09.29 45 0
뉴스 ‘41세’ 손담비, 출산 후 체중 충격 급변… “쥐젖 320개” 토로도 디시트렌드 14:00
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

뉴스

디시미디어

디시이슈

1/2