탐욕 알고리즘 (2) 썸네일형 리스트형 최적화 - 동적 알고리즘(Dynamic programming) 이번에는 동적 알고리즘과 이것을 통해 0-1 knapsack problem (배낭 채우기)를 다루려고 합니다. 우선적으로 동적 알고리즘에 대해 알아보자면 사전적 의미로서 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이라고 되어 있습니다. 그리고 그 대표적인 예로 재귀 함수 형태의 피보나치 수열이 떠오를 텐데요. 예를 들어 f(1)을 넣게 되면 1, f(2)를 넣게 되면 f(1) + f(0) = 2, f(3) = f(1) + f(2) = 3, f(4) = f(3) + f(2) =5...... 이렇게 됩니다. 하지만 이 함수를 메모리 관리적인 차원에서 본다면 매우 비효율적이라고 할 수 있습니다. f(7)을 컴퓨터에서 컴파일했을때 f(7)을 구하기 위해서 f(7) = f(6) + f(5) 를 호출하.. 최적화 - 탐욕 알고리즘, activity selection problem 이전 글에서 최적화에 대한 개념에 대해 알아봤습니다. 이번 글에서는 대표적인 최적화 문제 중 하나인 An activity selection problem과 이를 해결하기 위한 Greedy-Algorithm 또는 탐욕 알고리즘에 대해 다뤄보도록 하겠습니다. An activity selection problem (활동 선택 문제) 활동 선택 문제는 쉽게 말하면 한 강의실에서 여러 개의 수업을 하려고 할 때 겹치지 않고 한 번에 가장 많은 수업들을 고르는 알고리즘입니다. A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 시작시간 1 3 0 5 3 5 6 8 8 2 12 끝시간 4 4.5 6 7 9 9 10 11 12 14 16 위의 스케줄들을 가지고 가장 많은 개수의 일정을 만들어라는 문제가 주어.. 이전 1 다음
