[코테] 그리디 & 분할 정복 & 해시 알고리즘 예제

그리디 알고리즘 : 문제를 해결하기 위해 선택 가능한 옵션 중에서 가장 최선의 것을 선택해 나가는 알고리즘

function greedyCoinChange(amount, coins) {
    coins.sort((a, b) => b - a); // 동전을 내림차순으로 정렬
    let change = [];
    let remaining = amount;

    for (let coin of coins) {
        while (remaining >= coin) {
            change.push(coin);
            remaining -= coin;
        }
    }

    return change;
}

const coins = [25, 10, 5, 1];
const amount = 87;
const result = greedyCoinChange(amount, coins);
console.log(result); // [25, 25, 25, 10, 1, 1]

function buySnacks(budget, snacks) {
    // 과자를 가격이 높은 순서대로 정렬
    snacks.sort((a, b) => b.price - a.price);
    
    let purchasedSnacks = [];
    let remainingBudget = budget;

    for (let snack of snacks) {
        // 남은 예산이 과자 가격 이상인 경우 과자를 구매
        if (remainingBudget >= snack.price) {
            purchasedSnacks.push(snack.name);
            remainingBudget -= snack.price;
        }
    }

    return purchasedSnacks;
}

const snacks = [
    { name: '초콜릿', price: 2 },
    { name: '감자칩', price: 1 },
    { name: '젤리', price: 3 },
    { name: '아이스크림', price: 2.5 },
];

const budget = 5; // 예산 5
const result = buySnacks(budget, snacks);
console.log(result); // ['젤리', '아이스크림']

.push() : 배열의 맨 끝에 값을 추가
.unshift() : 배열의 맨 앞에 값을 추가
.pop() : 배열의 맨 끝에 값을 제거
.shift() : 배열의 맨 앞에 값을 제거
.sort() : 배열 정

 

 

분할정복 알고리즘: 문제를 작은 부분 문제로 나누고, 각각을 독립적으로 해결한 다음, 부분 문제의 해답을 조합하여 전체 문제를 해결하는 알고리즘

function findMax(arr) {
    if (arr.length === 1) {
        // 리스트가 하나의 요소만 갖는다면, 그 요소를 반환
        return arr[0];
    }

    // 리스트를 반으로 나눔
    const mid = Math.floor(arr.length / 2);
    const leftMax = findMax(arr.slice(0, mid));
    const rightMax = findMax(arr.slice(mid));

    // 양쪽의 최대값을 비교하여 반환
    return Math.max(leftMax, rightMax);
}

const numbers = [3, 5, 7, 2, 8, 10, 12];
const maxNumber = findMax(numbers);
console.log(maxNumber); // 12

 

 

해시 알고리즘: 데이터를 고유한 식별 값(해시 값)으로 변환하는 알고리즘

function simpleHash(str) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
        hash += str.charCodeAt(i);
    }
    return hash;
}

const str = "hello";
const hashValue = simpleHash(str);
console.log(hashValue); // 문자열 "hello"의 해시 값