RAINBOW-LAB

◎ Greedy Algorithm 이란? 탐욕 알고리즘(Greedy Algorithm) 이란, 최적해를 구하는데 사용되는 근사적인 방법으로 여러 경우 중 하나를 결정해야할 때마다 그 '순간'에 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종적인 해답에 도달하는 최적화 방법이다. '순간' 이라고 정의하는 선택은 Local 하게는 최적이지만, 그 선택을 계속 수집하여 Global하게 해답을 만들었다고 해서 그것이 최적이라는 어떠한 보장도 없다. 탐욕 알고리즘에는 대표적으로 '분할 가능 배낭문제' 가 있는데, 다음과 같은 예시를 들어보자. 한 은행의 화폐 단위가 7원/5원/1원 이라고 하자. 한 사람이 14원의 돈을 들고 화폐를 교환하려고 은행에 들렀다. 은행은 Greedy Algorithm을 사용하여 ..

어떤 문제가 반복적이고 최적 하위구조로 이루어질때, 하위 구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법이 동적계획법(Dynamic Programming) 이다. Divide-and-conquer 와 비슷해 보이지만 DC는 문제를 큰 부분에서 작은 부분으로 나누는 Top-Down approach인데 반해, DP는 작은 문제부터 큰 문제로 풀어가는 Bottom-Up approach이다. 또한 DC는 나눈 문제들을 완전히 새로운 하나의 독립된 문제로 보지만 DP는 이전 단계의 답에 의존적이다. 그래서 한 번 푼적 있는 문제는 다시 풀지 않도록 테이블에 저장해둔다. 정리하면, 1. 문제를 작은 부분 문제로 나눈다. 2. 가장 작은 부분의 문제부터 답을 구한 뒤 테이블에 저장한다. (Mem..