[CS] Greedy Algorithm / Implementation Day-46

Greedy Algorithm

매 순간, 최적이라 생각되는 해답을 찾으며, 이를 토대로 최종 문제의 해답에 도달하는 문제 해결 방식입니다. (항상 최적의 결과를 보장하지는 못합니다.)

• 탐욕적 선택 속성: 앞의 선택이 이후에 선택에 영향을 주지 않습니다.
• 최적 부분 구조: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.

Implementation (구현)

알고리즘 문제를 푼다는 건, 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것과 같습니다.

완전 탐색

모든 문제는 완전 탐색으로 풀 수 있습니다. 굉장히 단순한 방법이면서, 무식한 방법입니다.

효율적인 방법은 아닙니다.

Dynamic Programming

DP는 모든 경우의 수를 조합해 최적의 해법을 찾는 방식입니다.

주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식입니다.

DP는 두 가지 조건이 만족해야 사용할 수 있습니다.

• 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
• 작은 문제에서 구한 정답은 큰 문제에서도 사용할 수 있어야 한다.

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];
}