시뮬레이션 & Dynamic Programming

시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형입니다. 탐욕 알고리즘과 같이 작은 문제에서부터 출발한다는 점은 같습니다. 탐욕 알고리즘은 매 순간 최적의 선택을 찾는 방식이라면, Dynamic Programming은 모든 경우의 수를 조합해 최적의 해법을 찾는 방식입니다.
Dynamic programming의 원리: 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식입니다. 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍입니다.
다이내믹 프로그래밍이 사용되는 조건
1. 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다. (Overlapping Sub-problems) 큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다. 주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라, 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 합니다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다. (Optimal Substructure) 주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아야 합니다. 그리고 작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있습니다.

Recursion + Memorization
다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책을 이용합니다. 이때 결과를 저장하는 방법을 Memorization이라고 합니다. Memorization의 정의는 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술입니다.
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;
}
큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여, 이 방식을 Top-down 방식이라 부르기도 합니다. fib(7) 을 구하기 위해 fib(6)을, fib(6)을 구하기 위해 fib(5)을 호출한다.

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

탐욕 알고리즘의 특징
DP가 중복되는 서브문제를 다뤘다면, 그리디는 중복되지 않는 서브 문제를 다룬다.
탐욕 알고리즘은 발견법(heuristic method)의 방법 중 하나이다.
발견법: 최선, 최적의 답을 찾기보다 주어진 상황을 한단계씩 빠른 시간 내에 해결하기 위해 사용하는 방법론이다.
역추적(backtracking)과 같이 알고리즘 수행 시간이 많이 걸릴 때 사용하는 방법이다.
탐욕법은 이전의 선택으로 돌아가는 역추적과는 반대개념으로 다른 문제들과 독립적이다.
어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.
현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
예시)
1. 여행 짐 싸기: 여행 배낭에 물건을 정해진 시간 내에 담으려는 경우, 우선 순위가 높은 순서대로 물건을 담을 때 한번 배낭에 담은 물건은 다시 빼지 않는다.

DP와 Greedy의 차이점
DP: 문제를 작은 단위로 분할하여 해결한 후, 해결된 중복 문제들의 결과를 기반으로 전체 문제를 해결한다.
Greedy: 각 단계마다 최적해를 찾는 문제로 접근한다. 해결해야 할 전체 문제의 갯수를 줄이기 위해 개별적으로 문제를 해결해 나가는 선택을 한다.

Top-down과 Bottom-up의 소요시간을 비교하였을 때 결과에 어떤 차이가 있고, 그 원인은 무엇이었을까요?
answer: top-down 방식은 점화식을 이해하기 쉽다는 장점이 있고, bottom-up 방식은 함수를 재귀 호출하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다는 장점이 있다. 두 방법 중 어느 것이 시간적으로 더 효율이 있는 지를 묻고 있는데 그 답은 알 수 없다이다. 실제로 재귀는 내부 스택을 만들고 함수를 호출하는 과정이 있어서 반복이 더 빠를 것 같다고 느낄 수 있다. 하지만, top-down을 통해 문제를 풀어가는 경우에는 점화식에 따라 불필요한 계산을 오히려 bottom-up보다 덜하는 경우가 있기 때문에 궁극적으로는 알 수가 없다가 답이다.