탐욕 알고리즘
문제 해결 방법
- 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다.
- 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.
- 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.
탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다. 그러나 같이 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 한다.
2가지 조건
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.
Dynamic Programming 동적 계획법
전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식
주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식
하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다. 다시 말해, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍이다.
다이내믹 프로그래밍은 다음 두 가지 가정이 만족하는 조건에서 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다. (Overlapping Sub-problems)
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다. (Optimal Substructure)
메모제이션
메모이제이션(Memoization)은 동적계획법에서 아주 중요한 개념이다. 함수의 값을 계산한 뒤 계산된 값을 배열에 저장하는 방식이다. 이러한 메모이제이션은 필요한 때마다 함수를 다시 호출하지 않고 값을 빠르게 가져올 수 있다.
함수 실행 시간 측정
실행 환경에 따라 결과가 다르므로 측정 결과는 학습 용도로만 사용
var t0 = performance.now();
fib(50); // 여기에서 함수 실행을 시켜주세요
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')
start coding