탐욕법 (greedy algorithm)

탐욕법(Greedy Algorithm)은 각 단계에서 그 순간에 최적이라고 생각되는 선택을 하는 알고리즘이다. 

 

탐욕법의 주요 특징:

1. 단순성: 구현이 비교적 간단다
2. 지역적 최적: 각 단계에서 최적의 선택을 한다
3. 빠른 실행: 일반적으로 실행 속도가 빠다

주의할 점:

• 탐욕법이 항상 최적의 해를 보장하지는 않다
• 특정 문제에만 적용 가능하다

탐욕법이 잘 동작하는 다른 예제들:

1. 회의실 배정 문제
2. 크루스칼 알고리즘(최소 신장 트리)
3. 허프만 코딩

 

가장 대표적인 탐욕법 예제가 "거스름돈 문제"이다.

 

function getChange(amount) {
    // 사용 가능한 동전들 (큰 단위부터 정렬)
    const coins = [500, 100, 50, 10];
    const result = [];
    
    for (let coin of coins) {
        // 현재 동전으로 거슬러 줄 수 있는 개수 계산
        const count = Math.floor(amount / coin);
        
        if (count > 0) {
            // 결과 배열에 [동전 단위, 개수] 추가
            result.push([coin, count]);
            // 남은 금액 계산
            amount -= coin * count;
        }
    }
    
    return result;
}

// 사용 예시
console.log(getChange(1260));
// 출력: [[500, 2], [100, 2], [50, 1], [10, 1]]
// 의미: 500원 2개, 100원 2개, 50원 1개, 10원 1개

 

 

예제 1

/*
손님에게 최대한의 잔돈을 주는 방법
*/
function giveChange(itemPrice, amountPaid) {
    // 거스름돈을 계산한다.
    let change = amountPaid - itemPrice;

    if(change < 0) {
        console.log("지불 금액이 부족합니다.")
        return;
    }

    const denominations = [10000, 5000, 1000, 500, 100, 50, 10];
    const changeResult = {}

    for(const denomination of denominations.reverse()) {
        // 최대 100개 사용 가능
        // 화페 단위로 거스름돈을 나눠서 정수 형태의 몫을 구하고, 이것과 100중에 작은 값을 택한다
        const count = Math.min(Math.floor(change / denomination), 100);

        if(count > 0) {
            // 카운트가 0보다 크다면 객체에 해당 단위가 키로 들어가고 개수가 값으로 들어간다.
            changeResult[denomination] = count;
            // 거스름돈에서 해당 단위에 대한 금액을 차감한다.
            change -= denomination * count;
        }
    }

    if(change === 0) {
        console.log("손님에게 최대한 많은 잔돈을 주는 방법:");
        console.log(changeResult);
    } else {
        console.log("거스름돈을 줄 수 없습니다. (동전/지폐가 부족합니다)")
    }
}

giveChange(5000, 10000);

/*
손님에게 최대한 많은 잔돈을 주는 방법:
{ '10': 100, '50': 80 }
*/

 

예제2

/*
회의실 문제
최대한 많은 회의를 할 수 있도록
- 개발1팀: 오후 12시 ~ 오후 2시
- 개발2팀: 오후 1시 ~ 오후 3시
- 디인팀: 오후 2시 ~ 오후 4시
- 기획팀: 오후 3시 ~ 오후 5시
- 마케팅팀: 오후 4시 ~ 오후 6시
*/

function maxMeetings(meetings) {
    // 종료 시간으로 정렬
    meetings.sort((a, b) => a[1] - b[1]);

    let currentMeeting = meetings[0];
    let count = 1;

    for(let i = 1; i < meetings.length; i++) {
        // 다음 미팅의 시작 시간이 현재 미팅의 종료 시간보다 늦거나 같으면
        // 예약하고 현재 미팅을 업데이트 한다.
        if(meetings[i][0] >= currentMeeting[1]) {
            currentMeeting = meetings[i];
            count++;
        }
    }
    return count;
}

let meetings = [[0, 2], [1, 3], [2, 4], [3, 5], [4, 6]];
console.log(maxMeetings(meetings)); // 3

 

예제3

/*
    황금연휴를 넷플릭스로 보내는 방법
    :주어진 시간 내에 가장 많이 보기
*/

let series = [
    {name: '더글로리 시즌2', time: 7.25},
    {name: '킹덤 시즌2', time: 4.5},
    {name: '스위트룸 2', time: 9.5},
    {name: '이태원 클라쓰', time: 18.6},
]

function maxSeries(series, timeLimit) {
    // 총 시간별로 시리즈 정렬
    series.sort((a, b) => a.time - b.time)
    
    let count = 0;
    let currentTime = 0;

    for(let i =0; i < series.length; i++) {
        if(currentTime + series[i].time <= timeLimit) {
            currentTime+=series[i].time;
            count++;
        } else {
            break;
        }
    }
    
    return count;
}


let timeLimit = 20;
console.log(maxSeries(series, 20))  // 2 

/*
이 방법이라면 킹덤과 더 글로리를 보게 된다.
그런데 가장 좋은 선택은 사실 이태원 클라쓰이다.
탐욕법이 최적해를 구하는 방법은 아니라는 것을 보여준다.
*/

 

예제4

/*
'분할 가능한' 가방문제
: 한정된 무게 내에서 가방에 담을 수 있는 물건들의 가치를 최대화 하는 문제이다.
*/

let items = [
    {name: "책", weight: 1, value: 6000},
    {name: "노트북", weight: 3, value: 20000},
    {name: "카메라", weight: 2, value: 15000},
    {name: "", weight: 2, value: 8000},
]



const maxValue = (items, weightLimit) => {

    let totalValue = 0;
    let currentWeight = 0;
    
    items.sort((a, b) => b.value / b.weight - a.value / a.weight);
    
    for(let item of items) {
        if(currentWeight + item.weight <= weightLimit) {
            totalValue += item.value;
            currentWeight += item.weight;
        } else {
            
            let remainingWeight = weightLimit - currentWeight;
            totalValue += item.value * (remainingWeight / item.weight); //곱하기가 할당연산자보다 먼저 수행된다.
            // 물건의 가치 * (넣을 수 있는 무게 / 물건의 원래 무게)
            // 예: 10000원짜리 2kg 물건의 1kg 가치 = 10000 * (1/2) = 5000원
            // 만약 나눌 수 없다면 그냥 break만 있으면 된다.
            break;
        }
    }
    return totalValue;
}


let weightLimit = 5;
console.log(maxValue(items, weightLimit));	//35000

 

 

예제5: 팰린드롬

/*
팰린드롬(palindrome, 회문) 만들기
: 문열에서 한 번에 한 개의 문자를 선택하여 문자열의 맨 앞이나 뒤에 추가시킬 수 있다.
    이러한 조작을 통해 주어진 문자열을 팰린드롬으로 만드는 데 필요한 최소 조작횟수를 구하라

입력: 문자열 s(1<=s<=2000)
출력: 문열 s를 팰린드롬으로 만드는 데 필요한 최소 조작 횟수를 출력한다.

--> 탐욕법을 사용하여 문자열의 앞이나 뒤에서 접근하여 같은 문자가 나올 때까지 문를 추가하는 방식을 사용한다. 최적X
*/


function makePalindrome(s) {

    let left = 0;
    let right = s.length - 1;
    let moveCount = 0;

    while (left < right) {
        //아스키값을 비교하는 것임
        if(s[left] === s[right]){
            left++;
            right--;
        } else if(s[left] < s[right]){
            right--;
            moveCount += 1;
        } else {
            left++;
            moveCount += 1
        }
    }

    return moveCount;
}

console.log(makePalindrome("abcd")) //3

/*
	팰린드롬 문제를 탐욕법이 아닌 방법으로 풀이
*/

function makePalindrome(s) {
    let arr = s.split('');
    let left = 0;
    let right = arr.length - 1;
    let count = 0;
    
    while(left < right) {
        if(arr[left] === arr[right]) {
            left++;
            right--;
        } else {
            // 왼쪽에 문자를 추가하는 경우와 오른쪽에 문자를 추가하는 경우 중
            // 더 적은 조작이 필요한 쪽을 선택
            count++;
            if(isPalindromePossible(arr, left+1, right)) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return count;
}

// 주어진 범위의 문자열이 팰린드롬이 될 수 있는지 확인
function isPalindromePossible(arr, left, right) {
    while(left < right) {
        if(arr[left] !== arr[right]) return false;
        left++;
        right--;
    }
    return true;
}

// 테스트
console.log(makePalindrome("abcd")); // 3
console.log(makePalindrome("aabb")); // 2

 

예제6: 팰린드롬 적용 가능여부 판단하고 팰린드롬 반환

/*
애너그램(anagram)으로 팰린드롬 만들기
: 주어진 문자열로 팰린드롬을 만들 수 있으면 팰린드롬 만들어서 반환
    만약 불가하다면 false 반환
*/

function makePalindrome(S) {
    let charCount = {};
    // 개별 문자가ㅏ charCount객체에 속하는지 확인하고 있는 경우 1증가. 없으면 추가하고 1로 초기화
    for( let char of S) {
        if( char in charCount) {
            charCount[char]++;
        } else {
            charCount[char] = 1;
        }
    }
    //console.log(charCount)  //{ A: 2, B: 2, D: 1 }

    let oddCount = 0;
    let oddChar = '';
    let evenChars = [];

    for (let char in charCount) {
        if(charCount[char] % 2 === 0) { // 문자의 개수가 2의 배수인 경우, evenChars배열에 넣는다.
            for( let i = 0; i < charCount[char] / 2; i++) {
                evenChars.push(char);
            }
        } else {    // 개수가 2의 배수가 아닌 경우, 예를 들어 개수가 1,3 등 나머지가 1이 되는 경우
            oddCount++;
            oddChar = char;
            
            // 증가 되기 전의 현재 오드 카운트가 1보다 큰 경우 false반환. 홀수개인 문자가 2개 이상이면 가운데 놔도 팰린드롬이 되지 않으므로
            if(oddCount > 1) {
                return false;
            }

            // 그렇지 않은 경우 evenchars배열에 넣기
            for( let i = 0; i < Math.floor(charCount[char] /2 ); i++) {
                evenChars.push(char);
            }
        }
    }
    // evenChars배열을 스트링으로 만들고, 그 역순으로 만든 배열을 스트링으로 만들고, 가운데에는 홑수인 문자를 넣어서 합친다
    let palindrome = evenChars.join('') + oddChar + evenChars.reverse().join('');
    return palindrome;
}

console.log(makePalindrome('ABDDDAB'));   //ABDBA
console.log(makePalindrome('ABDAB23')); //false