[CS] Greedy Algorithm/Implementation Day-46

Greedy Algorithm

すべての瞬間、最良の答えを探して、その上で最終的な問題の答えを見つけています.(常に最良の結果が得られるわけではありません.)

貪欲選択プロパティ:前の選択は後の選択に影響しません.

最適局所構造:問題の最終解決策は局所問題の最適解決策から構成される.

インプリメンテーション

アルゴリズムの問題を解決するのは、私が考えている問題解決プロセスを計算思考に変換し、コードで実現するようにします.

フルナビゲーション

すべての問題は完全なナビゲーションで解決できます.とても簡単で無知な方法です
これは有効な方法ではありません.

Dynamic Programming

DPは任意の数を組み合わせることによって最適な解決策を探す方法である.
与えられた問題を複数のサブ問題に分解し,サブ問題の解決法と組み合わせて最終問題を解決した.
DPは2つの条件を満たさなければ使用できない.

の大きな問題を小さな問題に分けて、この小さな問題を繰り返し発見することができます.

の小さな問題から求めた答えは、大きな問題でも利用できるはずです.

ex)再帰関数で実現されるフィボナッチ数列

function fib(n) {
	if(n <= 2) return 1;
	return fib(n - 1) + fib(n - 2);
}

ex)動的プログラミングを採用したフィボナッチ数列

function fibMemo(n, memo = []) {
		// 이미 해결한 하위 문제인지 찾아본다
    if(memo[n] !== undefined) return memo[n];
    if(n <= 2) return 1;
		// 없다면 재귀로 결괏값을 도출하여 res 에 할당
    let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
		// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
    memo[n] = res;
    return res;
}

ex)再帰的および動的プログラミングによるフィボナッチ数列

function fibTab(n) {
    if(n <= 2) return 1;
    let fibNum = [0, 1, 1];
		// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
    for(let i = 3; i <= n; i++) {
        fibNum[i] = fibNum[i-1] + fibNum[i-2];
		// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
		// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다 
    }
    return fibNum[n];
}