알고리즘 정복기 (그리디)

그리디 알고리즘 🧩

오랜만에 알고리즘 포스팅을 업로드한다.
지금까지 배웠던 알고리즘들로 프로그래머스의 문제 level2~level3의 문제를 해결해왔다.
그런데 이제 슬슬 알고리즘에서 부족함을 많이 느꼈다! 🥲

현재 프로그래머스 데브코스에서는 여유가 조금 있기 때문에 이럴때 알고리즘 학습을 게을리하지 않고 더욱 정진해 나가야겠다!!

오늘은 그리디 알고리즘!

그리디 알고리즘이란?

미래를 고려하지 않고 현재의 충실해 최적의 해를 찾는것

결국 미래를 고려하지 않는 다는 말보단 미래를 고려하지 않아도 되는 문제에서 최적의 해를 구할 수 있다.

예를 들어?? 6200원을 5000원 1000원 100원을 사용해서
누군가에게 줄때 가장 적게 화폐를 전달해줄 경우의 수
혹은 서울에서 부산을거쳐 대전으로 가는데 가장 빠른 길의 경우의 수 같은 문제들이다.

이렇게 그리디 알고리즘을 사용하려면 몇 가지 문제의 조건이 필요하다.

1. 현재의 선택이 미래의 선택에 영향을 주지 않을때

2. 부분의 최적해가 모이면 전체의 최적해가 될 때

즉, 현재의 선택이 미래와 독립적이고 부분의 최적해가 전체의 최적해가 되면 그리디 알고리즘을 고려해볼만하다.

왜냐하면 그리디 알고리즘은 DP보다 빠른 우수한 성능을 가지고 있다.

그리디 전략 => 결국 핵심은 정렬!!!

그리디 알고리즘을 설명해주는 Youtube

문제로 먼저 살펴보자!!

체육복 📑

문제를 살펴보면 사실 체육복을 빌릴 수 있는 lost 라는 배열과 체육복을 빌려줄 수 있는 give라는 배열이 있다.

그런데 lost한 학생이 reserve를 한다면 해당 학생은 자기가 챙겨온 여벌의 옷을 입어야한다.

그리고 lost한 학생은 내 앞에 있는 학생의 운동복을 빌리는것이 최적의 값을 도출해내는데 큰 포인트이다.

필자가 정리한
1. lost한 학생이 여벌의 옷을 가져와 reserve를 할 수 있다면 해당 lost한 학생은 본인의 여벌의 옷을 입어야한다.
=> lost와 reserve에서 해당 학생의 number는 빠져야한다.
2. lost한 학생은 우선 앞 학생의 체육복을 빌리는 것을 우선해야한다. 그래야 최대한 체육복을 빌릴 수 있다.
why ? 앞 순서부터 체육복을 빌려준다면 2번부터는 앞 학생과 뒤 학생이 겹치게 되니까 그냥 앞에서부터 빌리는 것이 남김 없이 체육복을 빌릴수 있는 방법이 된다.

특히 2번을 적용하려면 lost와 reserve를 sort를 이용해 오름차순으로 배열하는 것이 중요하다.

function solution(n, lost, reserve) {
 
    lost.sort((a,b)=>a-b)
    reserve.sort((a,b)=>a-b)
  // 잃어버린 학생과 줄수있는 학생을 오른차순으로 배열하여 앞에서부터 쭉 나눠줄수 있도록함
    const copyLost = [...lost]
    const copyReserve = [...reserve]
    // 복사본을 만든 이유는 filter를 통해 기존의 lost, reserve의 겹치는 부분을 삭제하기위해
    lost = lost.filter((item)=>!copyReserve.includes(item))
    reserve = reserve.filter((item)=>!copyLost.includes(item))
    
    let safe= 0
    // 체육복 빌린 수
    for(let i = 0; i<lost.length; i++){
        const front = lost[i]-1
        const back = lost[i]+1
// 앞 친구, 뒤 친구
        if(reserve.indexOf(front)!==-1){
            //만약 앞학생이 있으면
            safe++
           const index = reserve.indexOf(front)
           reserve.splice(index,1)
        }
      // 앞 학생이 있으면 우선적으로 체육복을 빌려주고 빌려줄수있는 reserve항목에서 삭제
        else if(reserve.indexOf(back)!==-1){
            safe++
            const index = reserve.indexOf(back)
            reserve.splice(index,1)
        }
      // 그 다음 뒤 학생이 있다면 그 후로 체육복을 빌려주고 빌려줄 수 있는 reserve항목에서 삭제
    }
    return n-lost.length+safe
    // 그 다음 전체 학생수 + 체육복을 잃어버린 학생  - 체육복을 빌린 학생
}