Greedy Algorithm

Greedy : "탐욕스러운, 욕심 많은"

결정의 순간마다 당장 눈앞에 보이는 최적의 상황만을 탐욕적으로 쫓아 최종적인 해답에 도달하는 방법
BUT 항상 최적의 결과를 보장하지는 못함
ex)knapsack(backpack) problem : 제한된 조건 속에서 아이템들 중 최적의 가치의 아이템들을 고르는 것

1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택합니다.

2. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사합니다.

3. 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 위의 과정을 반복합니다.

그래프나 정렬, 다익스트라(Dijkstra) 알고리즘까지 폭넓은 영역에서 사용된다.

최소비용 신장 트리 : 그래프 내의 모든 정점을 최소 비용으로 연결하는 트리
Kruskal 알고리즘 : 최소비용 신장 트리를 만드는 알고리즘 중 탐욕 알고리즘을 이용한 풀이

<2가지 조건을 성립하여야 잘 작동>

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

Dynamic Programming(DP)

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

• 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제들은 중복된다. (Overlapping Sub-problems)

• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다. (Optimal Substructure)

  • 주어진 문제에 대한 최적의 해법을 구하고자 할 때, 그것의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾은 후 그것들을 결합하면 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있다

Recursion + Memoization

Memoization : 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

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

마지막으로 res 를 리턴하기 전 memo 의 n 번째 인덱스에 res 값을 저장. 그 이유는 (n+1)번째의 값을 구하고 싶을 때 n번째 값을 memo 에서 꺼내 사용하기 위함

fib(7)을 구하기 위해 fib(6)을 호출, fib(6)을 구하기 위해 fib(5)을 호출하는 풀이 과정->위에서 아래로 내려가는 것처럼 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 이 방식을 Top-down 방식이라 부르기도

Iteration + Tabulation

작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법-> Bottom-up

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