[Algorithm] 탐욕 알고리즘과 동적 계획법

 

Greedy Algorithm : 탐욕 알고리즘

• 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
• 항상 최적의 결과를 보장하지는 못한다
• 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있다 (근사 알고리즘으로 사용)

 

탐욕 알고리즘을 적용하려면 해당 문제가 다음의 2가지 조건을 성립해야 한다

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

 

탐욕 알고리즘 작동원리

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

 

 

---

Dynamic Programming (DP) : 동적계획법

 

• Dynamic Programming은 모든 경우의 수를 조합해 최적의 해법을 찾는 방식
• 탐욕 알고리즘과 같이 작은 문제에서부터 출발
• 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식
• 하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다
• 하나의 문제는 단 한 번만 풀도록 하는 알고리즘

 

 

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

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

 

첫 번째 조건인 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다는

큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다 는 말과 같다.

이를 확인하기 위해, 피보나치 수열을 예로 살펴보자.

 

• 작은 문제의 결과를 큰 문제를 해결하기 위해 여러 번 반복하여 사용할 수 있을 때,
• 부분 문제의 반복(Overlapping Sub-problems)이라는 조건을 만족.
• 주의할 점은 주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라,
• 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 한다는 점.

 

 

재귀함수로 구현한 피보나치 수열

function fib(n) {
	if(n <= 2) return 1;
	return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...

 

함수 계산 과정

피보나치 수열 모식도

 

피보나치 수열 예시 : 7번째 피보나치 수 fib(7) 를 구하는 과정

fib(7) = fib(6) + fib(5)
fib(7) = (fib(5) + fib(4)) + fib(5) // fib(6) = fib(5) + fib(4)
fib(7) = ((fib(4) + fib(3)) + fib(4)) + (fib(4) + fib(3)) // fib(5) = fib(4) + fib(3)
.....

 

 

 

두 번째 조건인 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다에 대해 살펴보자

이 조건에서 말하는 정답은 최적의 해결 방법(Optimal solution)을 의미

주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법을 찾아야 한다.

작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있다.

최단 경로를 찾는 문제를 통해 이 조건을 살펴보자

 

 

방향성 그래프 예시

A에서 D로 가는 최단 경로 A → B → C → D

A에서 C로 가는 최단 경로 A → B → C 

A에서 B로 가는 최단 경로 A → B

정리해보면 A에서 D로 가는 최단 경로는 그것의 작은 문제인 A에서 C로 가는 최단 경로,

그리고 한번 더 작은 문제인 A에서 B로 가는 최단 경로의 파악할 수 있다.

다이내믹 프로그래밍을 적용하기 위해서는, 작은 문제의 최적 해법을 결합하여 최종 문제의 최적 해법을 구할 수 있어야 한다.

 

 

 

 

Recursion + Memoization

Memoization

• 다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책 이용하는데, 이때 결과를 저장하는 방법.
• 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술 

 

 

다이내믹 프로그래밍을 적용한 피보나치 수열

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

 

1. 먼저 fibMemo 함수의 파라미터로 n 과 빈 배열을 전달. 이 빈 배열은 하위 문제의 결괏값을 저장하는 데에 사용
2. memo 라는 빈 배열의 n번째 인덱스가 undefined 이 아니라면, 다시 말해 n 번째 인덱스에 어떤 값이 저장되어 있다면, 저장되어 있는 값을 그대로 사용
3. undefined라면, 즉 처음 계산하는 수라면 fibMemo(n-1, memo) + fibMemo(n-2, memo)를 이용하여 값을 계산하고, 그 결괏값을 res 라는 변수에 할당
4. 마지막으로 res 를 리턴하기 전에 memo 의 n 번째 인덱스에 res 값을 저장. (n+1)번째의 값을 구하고 싶을 때, n번째 값을 memo 에서 확인해 사용

 

Memoization을 적용한 피보나치 수열 모식도

fib(7) 을 구하기 위해서는 이전의 작업으로 저장해 놓은 하위 문제의 결괏값을 사용

n이 커질수록 계산해야 할 과정은 선형으로 늘어나기 때문에 시간 복잡도는 O(N) 이 된다.

다이내믹 프로그래밍을 적용한 피보나치 수열에서 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];
}

 

 

 

---

크롬 개발자 도구에서 함수 실행 시간 측정 방법

var t0 = performance.now();
fib(50); // 여기에서 함수 실행
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')