Greedy Algorithm/Dynamic Programming

Greedy Algorithm(탐욕 알고리즘)

선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

=>탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 방법이다

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다

탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다

최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다

 

대표적 예제 (거스름돈)

function keepTheChange(input) {
	
	//1000엔짜리 지폐를 냈다는 가정이 있고, 입력 값으로는 지불해야 할 금액이 들어옵니다.
	let change = Number(1000 - input);
	//카운트하기 위해 변수 count에 0을 할당합니다. 
	let count = 0;
	
	//입력 값에 배열이 들어오지 않으므로 직접 배열을 만들어줍니다.
	const joiCoins = [500, 100, 50, 10, 5, 1];

	//만든 배열의 개수만큼만 돌려줘야 합니다.
	for(let i = 0; i < joiCoins.length; i++){
		//거스름돈이 0원이 되면 for문을 멈춥니다.
		if(change === 0) break;
		
		//거스름돈과 잔돈을 나눈 몫을 카운팅합니다.(쓰인 잔돈의 개수 카운팅)
		count += Math.floor(Number(change/joiCoins[i]));
		//거스름돈을 잔돈으로 나눈 나머지를 재할당합니다.
		change %= joiCoins[i];

	}
	
	//count를 리턴합니다.
	return count;
}

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다

 

Dynamic Programming(DP, 동적 계획법)

주어진 문제를 여러 개의 (작은) 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결한다 하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다

"메모이제이션"이 사용된다

=> 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다

 

두 가지 가정이 만족하는 조건에서 사용할 수 있다

• Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
• Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

1번 루트 실행 후 값을 저장
2번 루트 실행 후 값을 저장
3번 루트 실행 후 값을 저장
(만약에 중복되는 루트가 있으면 실행하지 않는다.)
모든 루트를 비교하여 최단의 루트를 찹아낸다
모든 방법을 검토하여 그중에서 최적의 풀이법을 찾아내는 알고리즘 동적 계획법

 

 

하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해놓은 해결책을 이용

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