디시인사이드 갤러리

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

갤러리 본문 영역

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

ㅇㅇ(75.6) 2021.09.29 12:26:34
조회 48 추천 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/07/07 - -
AD 휴대폰 바꿀까? 특가 구매 찬스! 운영자 25/07/02 - -
1895088 하이퍼커넥트란 회사 첨들어봄 [1] ㅇㅇ(223.33) 21.09.29 61 0
1895086 티맥스 그룹 1700명이래 ㅇㅇ(59.13) 21.09.29 88 0
1895085 무서어 ㅇㅇ(218.50) 21.09.29 17 0
1895083 개발력 떨어질까봐 여친 안사귀는중 ㅇㅇ(175.121) 21.09.29 29 0
1895082 곧 리눅스마스터2급을 이력서에 쓸수있음 [1] ㅇㅇ(223.33) 21.09.29 70 1
1895081 지금부터 리액트 글 보이는 즉시 ㅇㅇ(211.36) 21.09.29 37 0
1895077 사무직들 재택근무 개꿀임?? ㅇㅇ(223.62) 21.09.29 18 0
1895074 주변에 재택하는놈들 개꿀빨던데 ㅇㅇ(117.111) 21.09.29 37 0
1895073 한드 영향력 크긴 한듯 [2] ㅇㅇ갤로그로 이동합니다. 21.09.29 40 0
1895071 코시국에 작년부터 풀재택중이라 [3] ㅇㅇ(223.38) 21.09.29 68 0
1895070 국비여러분에게 알립니다 [1] ㅇㅇ(124.51) 21.09.29 88 0
1895068 프로로타입 왜쓰나 했더니.. [8] ㅇㅇ(114.203) 21.09.29 84 0
1895067 ㅇㅅㅇㅋㅋㅋ 쓰지 말아야하는데 ㅇㅅㅇㅋㅋㅋ [2] ㅇㅇ(59.13) 21.09.29 52 0
1895065 티맥스 어케 망했는지 이해가 안 가는게 [7] ㅇㅇ(59.13) 21.09.29 214 0
1895064 꼰대들 조온나피곤한거같아 [4] ㅇㅇ(61.43) 21.09.29 62 0
1895063 안드로이드 개발자는 풀스택 개발자인거야?? [3] ㅇㅇ(218.39) 21.09.29 639 0
1895062 현대차 생산직 vs 컴공 4년제 입학 [11] ㅇㅇ(223.38) 21.09.29 248 0
1895057 형들은 자위 [4] ㅇㅇ(39.7) 21.09.29 55 0
1895056 인텔리제이 자동완성기능 어케킴? ㅇㅇ(211.230) 21.09.29 28 0
1895055 쉬운거 같은데 깊이 있는 고수의 질문은 무엇인가 [5] ㅇㅇ(59.13) 21.09.29 70 0
1895054 집에서 공부하다 심정지오면 어케됨... [4] ㅇㅇ(39.7) 21.09.29 43 0
1895053 Yes24 어플 좆같다 진짜 [3] ㅇㅇ(115.188) 21.09.29 70 0
1895051 코테 자스 어떰? ㅇㅇ(210.183) 21.09.29 51 0
1895050 본인 리액트하는데 [21] 데버.갤로그로 이동합니다. 21.09.29 179 0
1895049 r에서 넘버링 어케 합니까... [1] ㅇㅇ(116.41) 21.09.29 24 0
1895048 형들 이거 강의 안보고 내가 직접 구현하면 포폴 ㅆㄱㄴ? ㅇㅇ(168.131) 21.09.29 55 0
1895047 하느님 제발 과거로 보내주세요 [2] ㅇㅇ(223.39) 21.09.29 118 0
1895046 학식들 과제 어느정도 수준임? [4] ㅇㅇ(175.197) 21.09.29 88 0
1895045 자스충 C 진작에 공부할걸. [4] ㅇㅇ(115.188) 21.09.29 179 0
1895044 이미 사라진 사이트도 저작권이 있음?? [1] ㅇㅇ(1.230) 21.09.29 53 0
1895043 올해 목표 코포 블루 ㅇㅅㅇ ㅇㅇ(39.7) 21.09.29 33 0
1895042 자료구조가 어려운 과목이냐? [3] ㅇㅇ(210.113) 21.09.29 129 0
1895041 애플 아카데미 왠 포항이야 갑자기 [3] WalletOverflow갤로그로 이동합니다. 21.09.29 129 0
1895039 빅데이터 국비 어떰? ㅇㅇ(117.111) 21.09.29 111 0
1895037 지금 연봉 얼마 받아야 정상임? [2] Kyle(115.131) 21.09.29 92 0
1895036 한국에서 태어난 게 죄악일까 [5] ㅇㅇ(175.198) 21.09.29 57 1
1895033 야 이거 강의 안보고 처음부터 끝까지 개발하면 포폴로 쓸 수 있음? ㅇㅇ(168.131) 21.09.29 41 0
1895030 오늘도 슬퍼서 엉엉 울었어 ㅠ ㅇㅇ(39.7) 21.09.29 38 0
1895028 네트워크 진짜 개재미없다... [4] WalletOverflow갤로그로 이동합니다. 21.09.29 161 0
1895027 오늘 국비 여자한테 좋아요 이모티콘 받음 [4] ㅇㅇ(220.84) 21.09.29 158 2
1895026 소는 참 귀엽게 생겼어 [6] 타블로갤로그로 이동합니다. 21.09.29 51 1
1895025 어떠케 하면 머리가 핑핑 돌까 ㅇㅅㅇ ㅇㅇ(1.249) 21.09.29 26 0
1895024 나두 그래픽스 배워보고 싶어 [1] ㅇㅇ(223.62) 21.09.29 66 0
1895023 쇼핑몰만들기나 디씨같은 커뮤니티만들기나 비슷함? ㅇㅇ(168.131) 21.09.29 34 0
1895022 JS에서 상속시키고싶을 때 ㅇㅇ(114.203) 21.09.29 27 0
1895021 영어이름문화 찐따갓음 ㅋㅋㅋ [4] ㅇㅇ(218.50) 21.09.29 61 0
1895020 너희들 유튜브에서 소 돼지 도축장 영상 봐봐라 ㅇㅇ(175.198) 21.09.29 445 0
1895019 능력은 ㅈ도 없는데 연봉은 높은걸 원하고 [3] ㅇㅇ(112.170) 21.09.29 96 0
1895016 애들아 맘마 맛있게 먹으렴 [6] 타블로갤로그로 이동합니다. 21.09.29 59 1
1895015 오라클 리눅스 센트 os 차이점이 뭐임?? ㅇㅇ(122.42) 21.09.29 36 0
뉴스 ♥이도현은 전역했는데…임지연, ‘8살 연하’ 남배우 입대 소식에 ‘눈물’ 디시트렌드 14:00
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

뉴스

디시미디어

디시이슈

1/2