9._.coding

Knapsack Problem(배낭 문제)란, 도둑이 배낭에 담을 수 있는 물건의 무게에 한계가 있는 상황에서 각 물건의 가치가 다를 때, 물건의 가치를 최대로 만드는 문제로, Fractional과 0-1의 두 가지 방식이 있다. Fractional Knapsack Problem은 같은 상황에 대해 물건을 일정 비율만큼 훔칠 수 있는 경우로, 물건을 분할해서 가져갈 수 있는 문제이고, 0-1 Knapsack Problem은 하나의 물건에 대해 나눌 수 없고, 훔치거나 훔치지 않는 선택만을 할 수 있는 경우의 문제이다. Fractional Knapsack Problem은 각 물건을 원하는대로 가져갈 수 있기 때문에 단위 무게당 가치(가치/무게)를 구해서 그 값이 높은 순서대로 배낭을 채운다. 그래서 물건을..

활동 선택 문제는 시작 시간과 종료 시간이 주어진 다양한 활동 중에서 가장 많은 활동을 할 수 있는 활동의 집합을 고르는 문제이다. 활동의 정보를 보고 활동 간의 관계를 계산하여 가장 긴 활동들의 sequence를 구한다. 이 문제는 순간의 최적을 전체의 최적이라고 판단하는 그리디 알고리즘으로 구할 수 있는데, 가장 빨리 끝나는 (=종료 시간이 가장 빠른) 활동을 선택하여, 남는 시간이 가장 크도록 하는 활동들을 최적이라고 판단하여 선택한다. 그리디 알고리즘의 개념은 아래 게시물에 잘 설명되어 있다. 가장 짧은 활동, 가장 덜 겹치는 활동, 일찍 시작하는 활동을 선택할 경우 반례가 존재해 문제 전체로 봤을 때 최적의 해를 구할 수 없게 되기 때문이다. 수열 S = {1, 2, … , n}을 종료 시간 순..

그리디 알고리즘은 현재 가장 좋아보이는 선택을 하는 알고리즘이다. 다시 말해, 순간마다 최적의 선택을 진행하여 적합한 해를 도출하며, 그것이 전체의 최적이 될 것이라고 생각한다. 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성되며, 이를 최적 부분 구조라고 한다. 이러한 특성으로 인해, 그리디 알고리즘은 장점과 단점이 뚜렷한 알고리즘이다. 장점은 각 부분에서 최적의 선택을 진행하기 때문에 계산 속도가 빠르다. 단점은 부분에서만 최적을 계산하기 때문에 전체적으로 봤을 떄 최적이 아닐 가능성이 있어 도출된 해가 최적임을 보장하지 않는다. 그리디 알고리즘은 Greedy-Choice Property(탐욕적 선택 속성)과 Optimal Substructure(최적 부분 구조)를 만족하는 문제를..