알고리즘을 설계하는 방법은 무엇입니까? 일반적인 알고리즘 패러다임 소개

알고리즘은 어떻게 설계하나요? 다음 기사에서는 일반적인 알고리즘 패러다임을 분석합니다. 도움이 필요한 친구들이 모두 참고할 수 있기를 바랍니다.

먼저 세 가지 개념을 명확히 합니다.

알고리즘: 문제를 단계별로 해결하는 과정입니다.

패러다임: 문제에 대한 사고 방식.

알고리즘 패러다임: 문제에 대한 효율적인 솔루션을 구축하기 위한 일반적인 접근 방식입니다.

이 기사에서는

• 분할 정복 알고리즘
• 동적 프로그래밍
• 탐욕 알고리즘
역추적 알고리즘

분할 정복

정렬 알고리즘 중 병합과 퀵 정렬 두 알고리즘의 공통점은 분할 정복 알고리즘이다.

분할 정복은 문제를 원래 문제와 유사한 더 작은 하위 문제로 분해하는 아이디어입니다. 하위 문제는 일반적으로 재귀적으로 해결되며 하위 문제에 대한 솔루션을 결합하여 원래 문제를 해결합니다.

분할정복 방식의 논리는 세 단계로 나눌 수 있습니다.

원래 문제를 더 작은 하위 문제로 나눕니다.
1. 하위 문제를 재귀적으로 해결하고, 해결이 완료된 후 하위 문제로 솔루션을 반환합니다.
2. 하위 문제에 대한 해결책을 원래 문제에 대한 해결책에 병합합니다.

분할정복 방법의 예: 이진탐색

다음은 분할정복을 이용하여 구현한 이진탐색이다.

function binarySearchRecursive(array, value, low, high) {
    if (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const element = array[mid];

        if (element < value) {
            return binarySearchRecursive(array, value, mid + 1, high);
        } else if (element > value) {
            return binarySearchRecursive(array, value, low, mid - 1);
        } else {
            return mid;
        }
    }
    return null;
}

export function binarySearch(array, value) {
    const sortedArray = quickSort(array);
    const low = 0;
    const high = sortedArray.length - 1;

    return binarySearchRecursive(array, value, low, high);
}

위의

함수는 타인이 호출하는 함수이고, binarySearch 함수는 분할 정복 방식을 구현한 함수임을 참고하시기 바랍니다. binarySearchRecursive

동적 프로그래밍

동적 프로그래밍은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 데 사용되는 최적화 기술입니다. 분할 정복과 매우 비슷해 보이지만 문제를 독립적인 하위 문제로 분해한 다음 함께 결합하는 대신 동적 프로그래밍은 문제를 독립적인 하위 문제로만 분해합니다.

알고리즘 로직은

하위 문제 정의의 세 단계로 나뉩니다.
반복하여 하위 문제를 해결하세요.
기본적인 문제를 파악하고 해결합니다.

동적 프로그래밍 사례: 최소 코인 변경 문제

코인 변경 문제라고 불리는 일반적인 면접 질문입니다. 동전 교환 문제는 주어진 동전의 양에 따라 몇 개의 동전을 사용하여 동전을 바꿀 수 있는지 구하는 방법입니다. 최소 동전 교환 문제는 단순히 주어진 화폐 단위를 사용하는 데 필요한 최소 동전 수를 찾는 것입니다. 예를 들어, 37센트를 잔돈으로 바꿔야 한다면 1 2 센트, 1 5 센트, 1 1 다임, 1 2 센트를 사용할 수 있습니다.

function minCoinChange(coins, amount) {
    const cache = [];
    const makeChange = (value) => {
        if (!value) {
            return [];
        }
        if (cache[value]) {
            return cache[value];
        }
        let min = [];
        let newMin;
        let newAmount;
        for (let i = 0; i < coins.length; i++) {
            const coin = coins[i];
            newAmount = value - coin;
            if (newAmount >= 0) {
                newMin = makeChange(newAmount);
            }
            if (newAmount >= 0 && 
            (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
                min = [coin].concat(newMin);
            }
        }
        return (cache[value] = min);
    }
    return makeChange(amount);
}

위 코드에서

매개변수는 단위([1, 2, 5, 10, 20, 50] RMB)를 나타냅니다. 중복 계산을 방지하기 위해 coins을 사용합니다. cache 함수는 재귀적으로 구현되며 makeChange에 접근할 수 있는 내부 함수입니다. cache

console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20]
console.log(minCoinChange([1, 3, 4], 6)) // => [3, 3]

그리디 알고리즘

그리디 알고리즘은 현재 최적해와 연관되어 전역 최적해를 찾으려고 합니다. 동적 프로그래밍과 달리 전체적인 상황을 고려하지 않습니다. 그리디 알고리즘은 간단하고 직관적인 경향이 있지만 전체적으로 최적의 솔루션은 아닐 수 있습니다.

그리디 알고리즘 사례: 최소 코인 변동 문제

위의 동적 프로그래밍으로 해결한 코인 문제는 그리디 알고리즘으로도 해결할 수 있습니다. 이 솔루션이 최적인지 여부는 사용된 명칭에 따라 다릅니다.

function minCoinChange(coins, amount) {
    const change = [];
    let total = 0;
    for (let i = coins.length; i>= 0; i--) {
        const coin = coins[i];
        while (total + coin <= amount) {
            change.push(coin);
            total += coin;
        }
    }
    return change;
}

보시다시피 그리디 알고리즘은 동적 프로그래밍 솔루션보다 훨씬 간단합니다. 두 문제의 차이점을 이해하기 위해 동일한 해결 사례를 살펴보겠습니다.

console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20]
console.log(minCoinChange([1, 3, 4], 6)) // => [4, 1, 1]

그리디 알고리즘은 첫 번째 문제에 대해 최적의 솔루션을 제공하지만 두 번째 문제는 최적 솔루션이 아닙니다(

). [3，3]

그리디 알고리즘은 동적 프로그래밍 알고리즘보다 간단하고 빠르지만, 얻은 솔루션이 최적의 솔루션이 아닐 수도 있습니다.

역추적 알고리즘

역추적 알고리즘은 단계별로 솔루션을 찾고 구축하는 데 적합합니다.

한 가지 방법으로 문제를 해결해 보세요.
1. 작동하지 않으면 적합한 해결책을 찾을 때까지 되돌아가서 1단계를 반복하세요.

역추적 알고리즘에 대해서는 또 다른 글을 써서 좀 더 복잡한 알고리즘을 소개하겠습니다. 아직 무엇을 써야할지 생각하지 못했습니다. 어쩌면 스도쿠를 풀기 위한 프로그램을 작성하는 것일 수도 있습니다. 이에 관심이 있으시면 제 공식 계정을 팔로우해주세요!

알고리즘은 끝이 없습니다. 이 글이 몇 가지 일반적인 알고리즘 패러다임을 이해하는 데 도움이 되기를 바랍니다.

관련 무료 학습 권장사항: js 비디오 튜토리얼

위 내용은 알고리즘을 설계하는 방법은 무엇입니까? 일반적인 알고리즘 패러다임 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!