[2023-09-27] TIL - 그리디

그리디

- 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘

- 최적해를 보장해주지 않는다.

 

그리디 알고리즘의 특징

- 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다.

- 크루스칼 알고리즘과 다익스트라 알고리즘 등에 사용된다.

- 직관적인 문제에 사용된다.

 

동전 반환 문제

- 거스름돈은 번거롭기 때문에 최대한 적은 갯수의 동전을 사용해서 거슬러 주고 싶다.

 -> 큰 단위의 동전부터 거스름돈을 만들면 된다.

 

 

코딩테스트 그리디 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

내 제출

function solution(number, k) {
    var answer = '';
    var stack=[];
    
    for(var i=0;i<number.length;i++){   
        var tt= number[i];
        while(k>0 && stack[stack.length-1]< tt){
            stack.pop()
            k--;
        }
        stack.push(tt)
        
    }
    console.log(stack)
    stack.splice(stack.length-1,k); //만약에 k개를 모두 못뺀 상태라면 뒤에서부터 작은 수들을 남은 k개 빼는게 큰 수를 만들수 있다.
    answer = stack.join("");
    return answer;
}

 

다른 풀이

// 큰 값이 나오면 이전 값 중 더 작은 값은 전부 다 삭제한다.
// 즉, 스택의 바닥에서부터 탑은 큰 수부터 작은 수로 나열

function solution(number, k) {
    let count = 0;
    let stack=[];
    
    for(const item of number){   
    	//스택안의 값과 현재 값을 비교하면서 현재값이 더 크면 스택안의 숫자를 계속뺀다.
        while(count < k && stack[stack.length-1]< item){
            stack.pop()
            count+=1;
        }
        stack.push(item);
        
    }
    // "9876543"처럼 스택안의 값을 빼지못하고 넣기만한다면 k개의 수를 만들 수가 없다.
    // 즉 k가 0이 되거나 k만큼의 길이의 숫자가 되어야 정답이된다.
    while(count < k) {
    	stack.pop();
        count +=1;
    }
    
    return stack.join("");
}

1.

2.