[프로그래머스] 피로도. 그리디가 안 되는 이유

• 입력이 적고(8), 문제 자체가 대놓고 완전탐색이라고 써있기 때문에 딱히 그리디를 안 따지고 풀었지만, 좀 더 빠른 코드를 고민하면서 그리디를 생각해볼 수도 있다. 그리디로 풀 수 있을까?

그리디의 두가지 조건

• 최적 부분 구조 : 문제의 최종 해결책이 부분 문제의 최적 해로 구성되어야 한다.
• 탐욕적 선택 속성 : 각 단계의 선택이 이후의 선택에 영향을 주지 않는다.

최적 부분 구조

적은 소모 피로도부터 들르기

• 얼핏 생각하기에, 최대한 많이 들르려면 피로도가 적게 드는 것부터 가야 할 것 같다.
  • 반례: [[80,20],[50,40],[30,10]] K=80
  • 2→0→1 순으로 들르려고 하면 0번째에 피로도가 모자라서 1개 밖에 못 들른다.

많은 필요 피로도부터 들르기

• 그렇다면 많은 피로도부터 들르면 괜찮을까?
  • 반례: [[80,20],[50,40],[30,10]] K=80
  • 0→1→2 순으로 들러야 하는데, 문제의 예시에 나와있는대로 다 들르지 못하낟.

효율이 좋은 던전부터 들르기

• 적은 소모 피로도도 안되고, 많은 필요 피로도도 안되면, (필요 피로도/소모 피로도) 를 기준으로 우선 들르는 건 어떨까?
• 실제 프로그래머스 제출 답안 중에 이런 접근이 있었고, 정답처리 됐던 적도 있던 것으로 보인다.
• [[80,20],[50,40],[30,10]] K=80 의 경우 [4,5/4,3] 으로 우선순위가 0→1→2 로 최선으로 보인다. 이 때 [[80,20], [40,10]] 처럼 기준값이 같은 경우에는 소모 피로도가 적은 곳을 우선 들러야 할 것이다.
• 아싸 알았다! 하고 코드를 짜기 전에 조그만 반례를 들 수 있다.
• 반례: [[81,20],[80,20]] K = 160 의 경우 [4.05,4] 의 우선순위를 가져 0→1 순으로 들러야 하지만 1→0 순으로 들르는 것보다 적은 던전을 들르게 된다.

무수한 반례 제보들

탐욕적 선택 속성

• 사실 이 조건부터 봤으면 더 쉬웠을 수 있다.
• 들를 던전을 선택하는 것이, 이후의 던전 선택에 영향을 주기 때문에 탐욕적 선택속성을 만족하지 못한다.
  • A를 첫번째 선택하면, B가 첫번째로 선택됐을 가능성이 영향을 받는다.
  • A를 선택하면서 피로도를 감소시켜, B가 선택될 수 있을지 여부에 영향을 미친다.
• 강의실 배정과 같은 전형적 그리디 문제에서의 탐욕적 선택 속성과 비교하면 더 좋을 것 같다.

고찰

• 그리디는 명확하게 그리디인 것 같은 경우가 많아서, 그리디로 풀고 맞으면 그냥 넘어가는 경우가 많았다.
• 하지만 이렇게 하나하나 조건을 따져보는 것이 좋은 습관인 것 같다.