[이코테]그리디

해피데빙·2022년 7월 1일

코딩테스트

목록 보기

25/52

출처: <이것이 코딩 테스트다> - 나동빈

탐욕법

현재 상황에서 지금 당장 좋은 것만 고르는 방법
일반적으로는 최적의 해를 보장할 수 없다
대부분의 그리디 문제는 얻은 해가 최적의 해가 되는 상황에서 이를 추론하도록 요구
일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구
정당성 분석이 중요
- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다

ex.

둘의 차이!
그리디가 더 작음 (21 > 19)

문제1. 거스름돈

500원을 최대한 넣고, 100을 최대한 넣고, 다음다음...

큰 단위가 작은 단쉬의 배수이므로 작은 단위의 도엊ㄴ들을 종합해 다른 해가 나올 수 없기 때문에 그리디 문제!

화폐의 종류만큼 for문 시간 복잡도 : O(K)

문제2.1이 될때까지

//이렇게 작성하면 한번 반복할 때마다 나눗셈을 하는 아래 방법보다 더 오래 걸림

let count=0; 
while(n!==1){ // 
count++;
if(n%m===0){ n=n/m } //그리디 부분 
else n--; 
}
return n

더 좋은 코드

target을 빠르게 구하기 위해 while을 쓰는 것이 아니라 나눈 몫에 k를 곱해 가장 가까운 배수를 찾는다
그리고 result에서 원래 값에서 target을 빼서 -1을 해야 하는 횟수를 구한다
if문 아래 #K로 나누기는 else문 : 나누니까 +1, 나눈 값으로 n을 대체
위의 코드보다 빠르다 : -를 여러번 해야 하는 상황일 때도 나눗셈 한번으로 처리를 해버림

문제3. 곱하기 혹은 더하기

내 풀이

for(let i=0; i<s.length; i++){ 

if(S[i-1]===0){ 
  result += S[i]//전 값이 0이면 더하기
}else if(S[i]!==0){ 
//해당 값이 0이 아니면 곱하기 
  result *= S[i]
}

return result
}

=> 1인 경우 생각 못함

첫번째 값을 빼고 첫번째와 새로 더하는 값 둘다 1보다 같거나 작은지 확인
같거나 작으면 +, 아니면 *

=> 첫번째는 처음에만 의미 있을 듯

X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹
최대 몇개의 그룹?
X : X명 (X ~ N-X 초과인 값은 모두 여기로 )
최댓값이 N-X이하여야 : N-X명 이하 (나머지 중 가장 최댓값, 위에서부터 X만큼)

function greedy(arr, N){ 
let count=0;
arr.sort((a,b)=>(b-a) 

while(arr[0] < arr.length){  //같을 때 포함하면 밑에서 남은 arr의 길이가 0보다 클 때 합
//같거나 크면 끝남
count++;
arr = arr.slice(0, arr[0]);
}

count++;//마지막 남은 애들(같을 때, 클 때) 
return count;

}