[내배캠 TIL 260323] C++ 그리디 (Greedy) : 구간 덮기 문제

그리디(Greedy)란

그리디 알고리즘은 매 순간 가장 최선이라고 판단되는 선택을 하면서 전체 문제의 최적해를 구하는 방식이다.

특징

• 현재 상황에서의 최선의 선택을 반복한다
• 이전 선택을 다시 바꾸지 않는다 (되돌리지 않음)
• 모든 경우를 탐색하지 않아도 된다

그리디가 성립하려면 다음 조건이 필요하다

1. 탐욕 선택 속성
   현재의 최선 선택이 전체 최적해로 이어져야 한다
2. 최적 부분 구조
   부분 문제 역시 동일한 방식으로 해결 가능해야 한다

---

문제 요약

길이 n의 벽에서 특정 구간(section)을 길이 m의 롤러로 최소 횟수로 칠해야 한다.

---

핵심 아이디어

• 아직 칠해지지 않은 가장 왼쪽 구간부터 시작한다
• 한 번 칠할 때 가능한 한 오른쪽까지 최대 범위를 덮는다
• 이미 덮인 구간은 건너뛴다

---

구현 방식

• painted : 현재까지 칠해진 가장 오른쪽 위치

if (section[i] > painted)
{
    painted = section[i] + (m - 1);
    answer++;
}

---

전체 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section) {
    int answer = 0;
    int paintedEnd = 0;
    
    for(int i = 0 ; i < section.size() ; ++i)
    {
        if(section[i] > paintedEnd)
        {
            paintedEnd = section[i] + (m - 1);
            answer++;
        }
    }
    
    return answer;
}

---

그리디가 성립하는 이유

1. 탐욕 선택 속성
   가장 왼쪽부터 칠하는 선택이 항상 최적의 결과를 만든다
2. 최적 부분 구조
   한 번 칠한 이후 남은 구간도 동일한 방식으로 해결할 수 있다

---

배운 점

• "최소 횟수" + "구간 커버" 형태는 그리디 문제일 가능성이 높다
• 중요한 것은 "어디서 시작해야 손해가 없는가"를 판단하는 것이다

---

패턴 정리

구간 덮기 (Covering)

조건

• 한 번의 선택으로 연속된 구간을 커버할 수 있음
• 최소 횟수를 요구함

해결 전략

• 필요한 경우 정렬
• 가장 앞 구간부터 시작
• 커버 가능한 최대 범위까지 확장

---

느낀 점

그리디는 단순히 직관적으로 고르는 것이 아니라,
그 선택이 항상 최적이라는 근거가 있어야 한다는 것을 알게 되었다.

이 문제는 시작 지점을 기준으로 사고를 전환하면
복잡한 탐색 없이도 해결할 수 있는 전형적인 그리디 문제였다.