Achievement Goals
탐욕법의 문제해결 과정을 이해한다.
탐욕법으로 어떤 사례에 적용하는지 알 수 있다.
👻 탐욕법이란?
탐욕법(Greedy Algorithm) 선택의 순간마다 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
여기서 최적이라 함은 시간복잡도나 여러가지 변수가 발생함에도 정답을 찾는것으로, 우리가 로직을 짤 때 항상 아무런 방해공작없이 최선의 상황에서만 이루어지진 않는다. 여러가지 조건들을 다 만족하면서 빠르게 도달할 수 있는 방법이 최적의 상황이라고 한다.
탐욕 알고리즘이 항상 최적의 해답을 구하는 것은 아니지만 최대한 최적에 걸맞게 접근하는 방식으로 볼 수 있다.
그렇다면 어떤 경우에 탐욕알고리즘이 적합할까?
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않을때.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성.
탐욕 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있다.
- 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택.
- 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사.
- 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복.
위 사항들을 고려하여 다음 두 문제를 풀어보도록 하겠다.
1. 짐나르기
☠️ 문제
한번에 최대 2개의 짐만 넣을 수 있는 박스가 있다.
예를 들어, 짐의 무게가 [70kg, 50kg, 80kg, 50kg]이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다.
박스를 최대한 적게 사용하여 모든 짐을 옮기려고 할때 필요한 박스 개수의 최소값을 return 해라.
☠️ 입력
인자 1 - stuff : Number 타입의 40 이상 240 이하의 자연수를 담은 배열
인자 2 - limit : Number 타입의 40 이상 240 이하의 자연수
☠️ 문제 이해하기
stuff 배열에 있는 무게 두개를 더했을때 limit 보다 작거나 같을때만 한 박스에 넣을 수 있다. 그것이 아니라면 한번씩만 담겨야 한다.
처음에 생각했던것은, 한번에 2개씩 넣을 수 있으니까 먼저 오름차순으로 솔팅하여 0,1번째 인덱스를 더한값이 limit보다 작거나 같으면 카운팅,
작지 않다면 그 뒤의있는 값과 아무리 더해도 넘을테니 솔팅된배열의 길이를 그대로 리턴하는 식으로 작성하였다.
하지만 이렇게 되면 수가 커질수록 오답이 나왔다. 즉, 정확하지 않다는 뜻.
어떻게 해야할지 꽤나 많이 고민한 후 첫번째와 마지막 순차적으로 깎아내리는 방식을 선택했다.
☠️ 수도코드
- 짐의 무게가 들어있는 배열, stuff 를 오름차순으로 sorting 해준다.
- sorting 된 배열의 첫번째 인덱스와 마지막 인덱스를 더한값을 계속적으로 비교할 수 있도록 변수를 지정해준다.
- 첫번째인덱스와 마지막인덱스를 더한값이 limit 보다 작거나 같으면 카운팅을 1씩 해주고 해당값들을 제외한 0번째,마지막인덱스로 돌아가 비교해준다.
- 첫번째 인덱스와 마지막인덱스를 더한값이 limit 보다 크면 각 하나씩 카운팅해야 하기 때문에 마지막인덱스의 값에서 -1을 해준 후 다시 비교한다.
- 솔팅하기 전, stuff 의 길이에서 카운팅된 값을 빼준다.
☠️ 풀이
function movingStuff(stuff, limit) {
// [70, 50, 80, 50] 두개씩만 고를 수 있고
// 그 두개씩 고른수가 limit을 넘으면 안된다.
let sorting = stuff.sort((a,b)=>a-b)
let count = 0;
let first = 0;
let last = sorting.length-1
while(first < last){
// limit 을 벗어나지않을때랑
if(sorting[first]+sorting[last] <= limit){
count++
first++
last--
}
// limit 을 벗어날때
else{
last--
}
}
return stuff.length - count;
}