[Algorithm] Greedy, Dynamic Programming

Greedy

Greedy algorithm 은 결정의 순간마다 당장 눈앞에 보이는 최적의 상황만을 탐욕적으로 쫓아 최종적인 해답에 도달하는 방법이다.

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

탐욕 알고리즘은 문제를 해결하는 과정에서 그 순간순간마다 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다. 하지만 항상 최적의 결과를 보장하지는 못한다.

탐욕 알고리즘은 아래의 조건을 만족하는 "특정한 상황" 이 아니면 최적의 해를 보장하지 못한다.

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

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

탐욕 알고리즘은 최소비용 신장 트리(Minimum Spanning Trees), 다익스트라, Kriskal 알고리즘 등에 사용된다.

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

Dynamic Programming

동적 계획법 (DP) - 기억하는 프로그래밍

-> 복잡한 문제를 부분문제로 나누어 풀고, 부분문제의 답을 저장해서 꺼내 쓴다.

다이내믹 프로그래밍은 다음 두 가지 가정이 만족하는 조건에서 사용할 수 있다.

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

Recursion + Memoization

function fibMemo(n, memo = []) {
  
  // 이미 해결한 하위 문제인지 찾아본다
  if(memo[n] !== undefined) 
    return memo[n];
  
  if(n <= 2) 
    return 1;
  
  // 없다면 재귀로 결과값을 도출하여 result 에 할당
  let result = fibMemo(n-1, memo) + fibMemo(n-2, memo);
  
  // memo 에 저장
  memo[n] = result;
  
  return result;
}

Iteration + Tabulation

function fibTab(n) {
  if(n < 2) 
    return n;
  
  // n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
  let fibNum = [0, 1, 1];
  
  // n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
  // n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다 
  for(let i = 3; i <= n; i++) {
    fibNum[i] = fibNum[i-1] + fibNum[i-2];
  }
  
  return fibNum[n];
}

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

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

느낀점

알고리즘이 어렵다기 보다는 알고리즘 문제를 푸는 것이 어렵다. 알고리즘의 종류에 대해 학습하고 그 유형에 맞는 문제들을 많이 푸는 식으로 해서 숙달해야 할 것 같다.