🌱  풀어볼 문제들 
• 11047 동전 0 
• 1931 회의실 배정 
• 11399 ATM 
• 11650 좌표 정렬하기

그리디 알고리즘

• 미래를 고려하지 않고, 현재 기준 가장 좋은 선택을 내리는 알고리즘, 미래에 어떤 영향을 줄지에는 고려 X, 선택하고 나면 다시 고려하지 않음

그리디 알고리즘을 적용할 수 있는 조건

1. 미래의 선택을 따져보지 않아도, 현재의 선택만으로 선택할 수 있어야한다.
2. 작은 문제들의 최적의 선택이 모여서 전체 최적의 선택이 된다.
   : 조금 더 풀어서 이야기하면, 문제를 부분적으로 쪼갤 수 있어야하고, 쪼갠 문제들의 최적해가 곧 전체 문제의 최적해가 된다는 것이다.

결국, 미래의 선택 고려 없이 현재만 고려해도 최적의 답을 찾을 수 있도록 정렬해야한다.

그리디와 다른 알고리즘을 비교해보자

무조건 부분해로 쪼갤 수 있으면 그리디일까?

여러 알고리즘을 공부하다보면 점점 유형 구분이 헷갈려진다.
물론 "문제를 쪼갠다"는 건 알고리즘의 전반적인 특성이다.

하지만 왠지 부분해라는 대목에 꽂혀서 부분해 => 그리디??라는 로직이 생겨버렸다.. 대표적으로 쪼개서 푸는 알고리즘은 그리디말고도 분할정복, 다이나믹 프로그래밍이 있다.

이 세가지 유형도 나눠서 정리하고 앞으로는 헷갈리는 일 없이 넘어가보자 !!

분할정복 : Divide & Conquer

분할정복은 기본적인 알고리즘인데 큰 문제를 작은 문제로 나눠서 해를 만드는 알고리즘 전략이다.
보통 병합으로 최종 해를 찾지만, 병합없이도 최종해를 찾을 수 있다.
대표적인 예시가 나눈 후 찾기만 하는 이분탐색이다.

계속 작은 문제로 반복해서 나누는게 핵심이다보니 보통 재귀를 사용한다

일반적으로 분할정복은 부분문제가 다른 부분문제와 독립적인 경우가 많다.
나눠진 부분문제끼리 의존적이지 않아서 독립적으로 선택할 수 있고, 해당 해를 합치기만 하면 최종해가 나오게 된다.

반대로 DP는 나눈 문제가 의존적으로 하나의 부분해가 다른 부분에 영향을 준다.
결국 의존성이 너무 크다면 DP 쪽으로 고민해볼 수 있다

그리디

그리디는 분할 정복보다는 당장 최선의 선택이 계속 이어진다고 이해하면 쉬울 것 같다. 합치는 과정없이 연속적인 선택의 결과가 최종해가 된다. 지금의 선택이 뒤의 선택에 직접적인 영향을 주고, 선택 이후에는 다시 고려하지 않는다. 해를 저장할 필요도 없다.

완전탐색와 DP, 그리디

• 완전 탐색의 방식 : 모든 경우를 계산한다.
• DP의 방식 : 최적해를 보장하기 위해 부분문제의 답을 활용하여 계산하고 저장
• 그리디의 방식 : 당장의 최적선택이 최종최적선택으로 보장되는 경우에 사용 (실무에서는 보장되지 않아도 사용 가능)

📌 그리디 vs 분할정복 vs DP 비교 표

구분	그리디 (Greedy)	분할 정복 (Divide & Conquer)	동적 계획법 (DP)
쪼개는 방식	현재 최선 선택 후 남은 문제로 축소	문제를 독립적인 작은 문제로 분할	문제를 작은 부분 문제로 나눠 푼 뒤 저장
부분 문제 관계	앞 선택이 뒤에 직접 영향	부분 문제들이 독립적	부분 문제들이 중복되고 연결됨
합치는 과정	불필요 (선택의 누적 = 답)	보통 필수 (부분 해 → 전체 해로 합침)	불필요 (저장된 값 참조로 확장)
조건	탐욕적 선택 성립 + 최적 부분 구조	부분 문제 독립성	중복 부분 문제 + 최적 부분 구조

그리디 대표 문제들

11047 동전0

• 한줄 복습 : 그리디 기본 문제 !
• 문제 풀이 : 🔗 개인노션링크

1931 회의실 배정

• 한줄 복습 : 앞서 선택한 회의와 지금 회의를 비교해서 추가, 교체하는 최선의 선택 내리기
• 문제 풀이 : 🔗 개인노션링크

11399 ATM

• 한줄 복습 : 연산식이 헷갈려서 틀렸던 문제, 수학적인 감이 부족하면 직접해보자
• 문제 풀이 : 🔗 개인노션링크

1202 보석 도둑

• 한줄 복습 : 그리디에 시간 단축을 위해 우선순위합을 사용! 최대힙으로 쓰고 싶을때는 -(넣을 값)으로 음수 변환하기, 힙큐는 힙큐 메서드로만 다뤄야 최소힙 보장⭐️
• 문제 풀이 : 🔗 개인노션링크

오늘의 최종 한마디 🌱

시간 단축을 위해서는 우선순위 힙 큐를 사용하자
특히 최소값, 최댓값을 계속해서 한 리스트에서 찾아야할때는 자료구조를 힙큐로 관리하자
힙큐는 힙큐 메서드로만 다루자. 안그러면 최소힙을 유지할 수 없다.!