본문 바로가기

문제 해결 알고리즘 기초/탐욕법

 (3)
[알고 스팟] 도시락 데우기 - 탐욕법 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 도시락 데우기(링크) #include using namespace std; vector M, E; int lunchBox() { vector EM; // push -E[i] to sort it in descending order for (int i = 0; i < M.size(); ++i) EM.push_back(make_pair(-E[i], M[i])); // Sort by descending order of eating duration sort(EM.begin(), EM.end()); int ret = 0, beginEat = 0; for (int i = 0; i < EM.size(); ++i) { // Add microwave time ..
[알고 스팟] 출전 순서 정하기 - 탐욕법 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 출전 순서 정하기(링크) 탐욕적으로 해결할 수 있을까? 매번 승부에서 탐욕적인 선택들을 시도해보자. 먼저 항상 가장 실력이 좋은 선수를 출전시킨다. 이 경우 2 번 이긴다. 러시아팀 3,000 2,700 2,800 2,200 2,500 1,900 한국팀 2,995 2,800 2,750 2,600 2,000 1,800 약간의 직관을 이용해 좀 더 개선해보자. 많은 게임에서 이겨야 하는데 실력 좋은 선수를 모두 먼저 내보내면 후반부에 레이팅이 높은 상대가 나오는 경우 속수무책이다. 따라서, 매번 게임에서 가장 근소한 차이로 이길만한 선수를 내보내자. 약한 상대를 만나는 경우에 우리팀의 강한 선수를 굳이 낭비하지 않을 기회를 얻을 수 있다. 이 경..
탐욕법에 대해서, 회의실 예약 문제 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 탐욕법 문제를 여러 조각으로 쪼개고, 각 조각으로 답의 일부를 작성하는 것은 다른 알고리즘과 같다. 핵심은 각 조각을 해결할 때 눈 앞의 가장 좋은 방법을 선택하는 것이다. 즉, 지금 하는 선택이 남은 선택에 끼칠 영향을 고려하지 않는다. 탐욕법을 통해 최적해를 구할 수 있다면 동적 계획보다 빠르지만, 최적해를 찾지 못 하는 경우가 많다. 따라서, 탐욕법을 사용할 정당성을 증명하는 과정이 필요하다. 탐욕적으로 해결하는 순서 전체 문제를 여러 조각으로 나누고 각 조각을 해결함에 있어서 탐욕적인 선택이 무엇일지 생각해본다. 예제 입력 몇 개를 손으로 풀어보면 직관을 얻을 수도 있다. 동작할 것 같은 방법이 생각나면 다음 속성들을 증명해봐야 한다...

티스토리툴바