그리디 알고리즘[탐욕법]

그리디 알고리즘이란?

---

• Greedy를 직역하면 "욕심많은, 탐욕스러운" 이라는 뜻

• 단어의 뜻처럼 선택의 갈림이있을때 최적이라고 생각되는것만을 쫓아 최종 해답에 도달하는 방식의 알고리즘.

• 즉, 최적의 값을 구해야 하는 상황에서 사용 되는 근시안적인 방법론.

• 항상 최적의 값을 보장하는 것이 아닌 최적의 값의 '근사한 값'을 목표로 함.

• 그렇게 때문에 어느정도 최적에 근사한 값을 빠르게 도출할수 있는 장점이 있음.

• 그리디 알고리즘은 근사 알고리즘으로 사용할 수 있다.

• 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이어야 한다.

근시안적 방법론

• 단기 목표를 중심으로한 전략적인 접근 방법을 의미.

• 주로 현재의 문제를 해결하는 데 초첨을 맞추며, 장기적인 전망보다는 단기적인 성과를 중요시 함.

 

근사 알고리즘

• 최적의 해를 구할 수 없는 문제에서 근사한 해를 구하는 알고리즘을 의미.

• 항상 최적해를 보장하지는 않지만, 많은 경우에는 최적해에 근접한 값을 구할 수 있다. 

 

탐욕법에는 한가지 문제가 있는데 그것은 탐욕법으로 문제를 풀지만 그문제가 정말 맞는 방법인지 확인하기 어렵다.

 

탐욕법을 사용하여 x의 해당위치에서 최솟값을 찾기 위해서는

계속해서 최솟값을 찾아 내려간다음 최솟값이 있는 위치를 찾아낼수가 있다.

 

하지만

만약 y의 위치에서 시작한다면 전체의 최솟값은 x의 최솟값일텐데 y기준에서는 y의 최솟값이 가장 낮은 값이므로

정확한 값을 찾을수가 없다.

 

그렇기 때문에 여러 유형의 문제를 만나보고 해결할수 있는 경험을 해보아야 한다.

 

 

그리디 알고리즘 속성

---

그리디 알고리즘을 적용하기 위해 필요한 2가지 속성

 

■ 탐욕 선택 속성(greedy choice property)

    • 각 단계에서 '최선의 선택'을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말함. 

    • 즉, 각 단계에서 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것이며,

      앞의 선택이 이후의 선택에 영향을 주지 않는 것이다.

 

■ 최적 부분 구조(Optimal Substructure)

    • 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있는 경우를 말함.

    • 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후

      이를 조합하여 전체 문제의 최적해를 구하는것을 의미.

      즉, 문제에 대한 최종 해결방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됨.

 

 

그리디 알고리즘 단계

---

1. 선택 절차(Selection Procedure)

    → 현재 상태 에서 최적인 선택을 함, 이 후에는 선택을 바꿀수 없음 

 

2. 적절성 검사(Feasibility Check)

    → 선택한 항목이 문제의 조건을 만족시키는지 확인, 조건을 만족시키지 않으면 해당 항목 제외.

 

3. 해답 검사(Solution Check)

    → 모든 선택이 돤료되면, 최종 선택이 문제의 조건을 만족시키는지 확인

 

 

그리디 적용시키기

---

프로그래머스 체육복 문제

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 
다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 
학생들의 번호는 체격 순으로 매겨져 있어, 
바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 
예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 
체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 
여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 
체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 
  이때 이 학생은 체육복을 하나만 도난당했다고 가정하며,
  남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

 

풀기전 정리 내용

• 체육복은 바로 앞 또는 뒤 학생에게만 빌려줄수 있음

• 전체 학생의 수는 2명이상 30명 이하 : n

• 도난 당한 학생의 수 1명이상 n명 이해 : lost[]

• 여별의 체육복을 가져온 학생의수 1명이상 n명 이하 : reserve[]

• 여벌의 체육복이 있는 학생만 빌려줄수 있음 위 아래로 -1, +1

• 도난 당한 체육복이 여벌을 가져온 학생의 것이면 여벌 학생은 옷을 빌려줄수 없음

• 체육 수업을 들을수 있는 학생의 최댓값구하기

 

예시 풀이

입출력 1번 예시

• 총 학생수 5명 = [1,2,3,4,5] , 체육복 도난 인원 2명=[2,4] , 여벌 체육복 가져온 인원 [1,3,5]

• 문제없이 수업들을수 있는 학생 = 총 학생수 - 도난당한 학생수 | 3 = 5 - 2

• 도난당한 인원 -1학생과 +1학생이 여벌체육복 가져온 인원이면 문제 없이 수업들을수 있는 학생수 + 1을 해준다.

    if(reserve.includes(2-1)||reserve.includes(2+1)) 문제없이 수업들을수 있는 학생++

• 2-1 = 1, 1번학생에게 여벌체육복이 있으므로 학생 +1

• 4-1 = 3, 3번학생에게도 여벌체육복이 있으므로 학생 +1

• 총 수업 듣는 인원 5명

 

입출력 2번 예시

• 총 학생수 5명 = [1,2,3,4,5] , 체육복 도난 인원 2명=[2,4] , 여벌 체육복 가져온 인원 [3]

• 문제없이 수업들을수 있는 학생 = 총 학생수 - 도난당한 학생수 | 3 = 5 - 2

   if(reserve.includes(2-1)||reserve.includes(2+1)) 문제없이 수업들을수 있는 학생++, 여벌 체육복인원 공백으로 만들기

• 2+1 = 3, 3번학생에게 여벌체육복이 있으므로 학생 +1

• 4-1 = 3, 3번학생에게 여벌옷이 있었지만 빌려줬으므로 추가 x

• 총 수업 듣는 인원 4명

 

그리디 알고리즘 단계 적용

1. 선택절차 : 체육복을 잃어버린 학생과 여벌 옷을 가져온 학생을 정렬한다.

2. 적절성 검사 : 체육복을 잃어버린 학생중 여벌이 있던 학생의 수와 여벌이 있던 학생에게 빌릴수 있는 학생의 수를 계산한다.

3. 해답 검사 : 체육수업을 들을수 있는 학생의 수를 계산하여 반환한다.

 

function solution(n, lost, reserve) {
    let noProblemStd = n-lost.length // 수업들을수 있는 학생의 수
    lost.sort() // 지문에 자동 정렬된다는 조건이 없으므로 정렬시켜주기
    reserve.sort()
    
    // 도난 당한 체육복이 여벌을 가져온 학생의 것이면 여벌 학생은 옷을 빌려줄수 없음
    for(let i=0; i < lost.length; i++){
        for(let j=0; j < reserve.length; j++){
            if(lost[i] === reserve[j]){
                noProblemStd++ // 수업들을수 있는 학생의 수증가
                reserve[j] = "" // 본인의 체육복은 빌려줄수 없음
                lost[i] = -99 // 본인이 본인의 옷을 갖고있으므로 빌릴수없음.
                break;
            }
        }
    }
    
    for(let i = 0; i<lost.length;i++){
        if(reserve.includes(lost[i]-1)){
            noProblemStd++ // 수업들을수 있는 학생의 수증가
            reserve = reserve.filter(student=>student !== lost[i]-1) // 빌려주면 표시 x
        }else if(reserve.includes(lost[i]+1)){
            noProblemStd++ // 수업들을수 있는 학생의 수증가
            reserve = reserve.filter(student=>student !== lost[i]+1)
        }
    }
    return noProblemStd;
}