[알고리즘] 탐욕법과 최적화 (레벨2 구명보트)

문제

기록

그리디(greedy) 알고리즘? 말그대로 탐욕법이라는 건데, 눈앞에 보이는 당장의 가장 바람직한 선택들이 결국에는 최종적으로도 가장 바람직한 선택이 되는 알고리즘을 말한다.

그리디 알고리즘은 두가지 조건이 만족할 때 그것이 바람직한 정답을 가져온다. 하나는 매번 하는 선택이 그 다음 선택에 영향을 미치면 안되고(greedy choice property), 현재 선택한 값들의 모임이 결국 최종적으로 최적의 값이어야만 한다는 것(optimal substructure)이다.

예를들어 만약 도둑이 어느집에 매일같이 몰래 하나씩 삼일 동안 들고 나올 수 있다면, 가장 비싼 것들부터 들고나온다면 최적의 결과가 될 것이다. 그러나 만약 도둑이 하루동안만 도둑질을 할 수 있다고 한다면, 가장 비싸지만 부피가 큰 물건을 담아 가방을 채우는 일은, 남은 작은 물건들을 합했을때 더 비싼 값이 나오는 물건들을 담을 수 없기 때문에 최적의 해가 되지 못한다.

위의 예는 greedy알고리즘이 적용되며, 아래의 예는 적용이 되지 못한다.

1. 해당 문제는 greedy가 적용되는 문제이다. 왜? 보트에는 두명까지만 태울 수 있기 때문에, 어찌됐든 최소의 보트를 이용하는 방법은 가장 큰것에 작은것을 우겨넣을 수 있을때, 먼저 소거하며 값을 구해나가는 것. (눈앞의 최적의 결과)

2. 가장 큰것에 작은것을 우겨넣을 경우를 생각해야 하기 때문에, 크기순으로 정렬했을때, 가장 큰것과 작은것들을 (가장 앞과 뒤)우겨넣으려고 시도해본 후 안들어간다면 우겨넣을 수 있는 경우의 수는 없는 것. (가장 크고 가장 작은 것들을 합칠 수 없다면 가장 크고 가장 덜작은 케이스도 합칠 수 없기 때문에 이부분은 가장 큰것만 소거된다)

3. 가장 큰 난관은 효율성 테스트였다. 효율성 테스트를 통과하지 못해, 반듯이 순회를 해야하는 아랫부분보다는 sort정렬을 퀵정렬 알고리즘을 사용하여 바꾸어보았지만 똑같이 통과하지 못했다.
   그러다가 while문과 splice를 통해 배열을 조작하지 않고, 단순히 for문 하나로 되게 만들어보았더니 통과.

for문이 while문보다 약간 빠르다는점과 splice에 의한 배열조작의 시간복잡도가 사라지니 통과한 듯 했다. 앞으로 탐색 알고리즘에서 그 다음 선택시 배열의 조건들이 바뀌는 로직을 짜야 한다면, 방금과 같이 최대한 배열을 조작하지 않는 방법을 찾아야 할 것 같다. (웅모형이 딥다이브에서 말했듯 사실 splice와 같은 원본 배열을 조작하는 메서드는 지양해야 하는 것이기도 하다.)

내 솔루션

function solution(people, limit) {
    let count = 0;
    	
    people.sort((a,b)=>b-a)
    
    let peopleLength =  people.length;
    for(let i = 0; i<peopleLength; i++){
        if(people[i] + people[peopleLength-1] <= limit){
            peopleLength--;
        } 
        count++
    }

    return count
}

//효율성 테스트를 통과하지 못한 풀이
function solution(people, limit) {
     while(people.length>0){
      if(people[0] + people[people.length-1] <= limit){
           people.splice(0,1)
          people.splice(people.length-1, 1)
        
      } else {
          people.splice(people.length-1, 1)
      }
     count++
 }

return count
}