그리디

그리디

매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘이다. 항상 최적해를 보장해주지는 않는다.

그리디 알고리즘의 특징

• 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다.
• 크루스칼, 다익스트라 알고리즘 등에 사용된다.
• 직관적인 문제 풀이에 적합하다.

그리디 알고리즘 예시 : 동전 반환 문제

거스름돈을 최대한 큰 단위로 거슬러 주려면 어떻게 해야할까?
=> 큰 단위인 지폐, 동전 순으로 거스름돈을 만들면 된다.

출처: 이선협 강사님 데브코스 강의자료

그리디 관련 코딩테스트 문제

큰 수 만들기

function solution(number, k) {
    let answer = '';
    let removed = 0;
    let stack = [];
    
    for (let i=0; i<number.length; i++) {
        const current = number[i];
        // k개 제거 또는 스택의 TOP이 현재 수보다 작을 경우
        while (removed < k && stack[stack.length - 1] < Number(current) ) {
            stack.pop(); // 작은 수(현재 수) 제거
            removed ++;
        }
        stack.push(current); // 크다면 스택에 추가
    }
    // k가 제거가 되지 않았을 때 추가 처리
    while(removed < k) {
        stack.pop();
        removed ++;
    }
    
    return stack.join('');
}

가장 큰 수를 만들기 위해서는 왼쪽에서부터 큰 자릿수를 남겨야 했다.
number에 있는 숫자를 한 자리씩 순회하면서 스택에 큰 자릿수를 남겨두는 방식으로 문제를 해결했다.

---

😅 해당 내용은 공부하면서 정리한 글입니다. 틀린 부분이나 오해하고 있는 부분이 있다면 피드백 부탁드립니다.