▫️그리디 알고리즘 (탐욕법)

• 참고 레퍼런스

<aside> 💡 그리디란!

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 매 순간 가장 좋아보이는 것을 선택 → 현재의 선택이 나중에 미칠 영향이나 경우의 수에 대해서는 고려하지 x (백트래킹을 통해서 추가 점검을 하지 않는다!! 정말 지금 순간에서 만족하고 끝.)
• 단, 그리디 알고리즘은 항상 최적해를 보장하지 않는다. 단순히 가장 좋아보이는 것들을 반복해서 선택했을 때, 최적의 해를 구할 수 있는지 검토하는 과정이 필요하다!
• 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형 </aside>

🤔 이 문제가 왜 그리디야?

그리디 문제들을 보면, 도대체 그리디가 뭔지 감이 안올 때가 있다. 지금 나도 “이 문제는 ‘그리디’유형입니다.” 라고 말해주지 않으면 아직 그리디가 뭔지, 그리디로 풀어야하는건지? 에 대한 감이 잡히지 않는다. 그래서 지금까지 풀어본 그리디 유형들을 정리해보고자 한다.

▫️ [이코테 예제] 백준 5585번 거스름돈

그리디 알고리즘을 설명하는 가장 Well-known

5585번: 거스름돈

이 문제를 보면, ‘최소 동전갯수’로 거스름돈을 주어야합니다. 그렇게 하기 위해서 가장 좋은 방식은? ‘가장 큰 돈을 우선적으로 주는 것’이 가장 좋겠죠. 즉, 500원 짜리부터 아주 탐욕적으로 줘버린다는 소리가 바로 그리디입니다. (나머지 동전들은 고려하지 않은채 500원짜리 먼저 거슬러준다는 것! 500원짜리 이놈이 아주 욕심쟁이다~ 본인이 먼저 거슬러지려고한다~ 이렇게 생각했어요…)

▫️ [boj] 4796 캠핑

4796번: 캠핑

• 가장 많은 캠핑장을 사용하기 위한 시각으로만 접근
• (예제1) 김강산이 묵을 수 있는 최대 일 수: 8일 캠핑장 오픈 일수: 5일씩 김강산 총 휴가 일수: 20일
  • 김강산이 못자는 것은 생각하지 않음 (그냥 무조건 날짜 생기면 묵는다고 생각) → 탐욕법? 넹 이게 최선! 최대의 값을 도출해냄
  • 5일오픈하는데, 김강산은 8일까지 묵을 수 있으니까 5일 전부 그냥 잔소리말고 묵는다고 생각
  • 이렇게 다른 경우 생각하지 않고 지금 현재의 최적상황만 생각하는 것이 ‘그리디’가 아닐까…

▫️ [boj] 1449 수리공 항승

1449번: 수리공 항승

• 그리디는, 정렬을 통해 앞에서부터 최적의 무언가를 찾아나서는 것을 의미한다. 그니까 만약 정렬된 Array를 다룰때, Array의 다음 인덱스는 전혀 고려하지 않는 것이다.
• (예제 1) 누수부분: 4군데 테이프의 길이: 2 누수지점: 1, 2, 100, 101
  • 테이프는 자를 수 없기 때문에, 무조건 2칸이 붙어있는 애들만 매꿀 수 있다.
  • 누수지점이 순서대로 입력되지 않을 수 있기 때문에 오름차순으로 정렬해준다.
  • 그다음, 두칸씩 막아나가면 된다!
  • 두칸씩 막을때, 현재 지점에서 앞에있는 테이프와 연결이되는지? 새로운 테이프를 꺼내야하는지?에 대한 고민만 수행하고, 혹시,,, 뒤에서 또 누수가 생기는 경우 어쩌고 저쩌고,, 이런 경우의수는 일절 생각 하지 않는다!

▫️ [boj] 1931 회의실 배정