본문 바로가기

알고리즘(Algorithm)/그리디(Greedy)

 (7)
집합 덮개 문제(Set Cover Problem) [출처 : 위키백과] 집합 덮개 문제(set cover problem)는 전산학과 복잡도 이론에서 다루는 오랜 문제로, 어떠한 전체집합과 그 집합의 부분집합들이 주어졌을 때, 부분집합들 중에서 가능한 한 적은 집합을 골라서 그 집합들의 합집합이 원래 전체집합이 되도록, 즉 그 집합들이 원래 전제집합을 '덮도록' 집합을 선택하는 문제이다. 이때 집합을 가능한 한 적게 골라내는 것이 목표이다 N개의 원소를 가진 집합 U가 주어진다면 U의 부분집합(subsets)들은 S = {S1, S2…,Sm} 말하고 모든 부분 집합 Si는 관련된 비용(cost)을 갖는다. S의 부분집합들을 합집합하여 U의 모든 요소를 ​​커버할수있도록 해야 한다면 이때 선택되는 부분집합의 최소 비용 집합을 찾아야 한다. 집합 덮개 문제(..
거스름돈 알고리즘(Coin Change Algorithm), 동전교환 알고리즘 [출처] https://www.amazon.com/School-Smart-Assorted-Plastic-Coins/dp/B00JKIEQPS 거스름돈 알고리즘(Coin Change Algorithm) 또는 동전교환 알고리즘은 동전 coins = { 1, 2, 5, 10, 20, 50, 100, 500, 1000}이 있고 값 V 가 주어졌을 때 V와 동일하도록 동전을 선택하는 문제인데 이때 동전의 개수를 최소화(minimum)하는 방법을 찾는 것이다. (단, 같은 동전을 여러번 선택 가능하다) 예를들어 coins = { 1, 2, 5, 10, 20, 50, 100, 500, 1000} 들이 있을때 선택한 동전의 개수는 최소화 하면서 동전의 합이 70원이 되도록 해야만 한다면 20원, 50원 동전 2개를 선택..
배낭 문제(Knapsack Problem) 배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제로 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치(value)와 무게(weight)가 있는 N개의 짐(item)들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. [출처] https://en.wikipedia.org/wiki/Knapsack_problem 이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭..
데드라인 스케줄링(Deadline Scheduling) - Job Sequencing Problem 마감일 전에 작업이 끝나면 모든 작업의 ​​마감 시간과 관련 이익이있는 일련의 작업이 제공됩니다. 또한 모든 작업에 단일 단위 시간이 걸리므로 모든 작업의 ​​최소 마감 시간은 1입니다. 한 번에 하나의 작업 만 예약 할 수있는 경우 총 이익을 최대화하는 방법. 작업순서문제 (Job Sequencing Problem)는 마감(deadline) 전에 작업을 완료하면 해당 작업에 연관된 이익(profit)이 제공된다. 데드라인이 있는 여러 작업들이 있을때 한번에 하나의 작업만 할 수 있는 경우 총 이익을 최대화 하는 방법을 푸는 것이다. 조건은 모든 작업에 단일 단위 시간(single unit of time)이 걸린다는 것이다. 즉 마감이 2시간 이면 최소 모든 작업에 걸리는 시간은 1시간이므로 최소 1시부..
이집트 분수(Egyptian Fraction) 이집트 분수(Egyptian fraction)란 유리수를 단위분수((분자가 1인것))의 합으로 표현하는 것을 말한다. [출처 ] https://www.futurelearn.com/courses/maths-puzzles/0/steps/13994 이집트 분수는 이집트에서 기원전부터 사용한 역사적인 사실 외에도, 분수의 또 다른 표현에서 많은 개체를 동일하게 공유할수있도록 나눈데 도움을 줄 수 있는 장점이 있다. 예를들어 만약 8명의 저녁 식사에 5개의 피자를 똑같이 나누기를 원한다면, 이집트 분수 표현은 아래처럼 표현 가능한데 이는 각 사람이 피자 반쪽(1/2)과 나머지 피자 8분의 1을씩 동일하게 공유할 수 있다는 것을 보여준다. 이것은 피자 4개를 반으로 나누고 나머지 피자는 8개로 나눌수 있고 또는 5..
활동 선택 문제(activity selection problem) Greedy 알고리즘의 첫 번째 예제는 활동선택문제(Activity Selection Problem) 이다. 활동선택은 먼저 시작(start)과 끝(finish) 시간이 n 개의 활동이 주어진다. 개인이 한 번에 하나의 활동에만 작업(즉 겹치는 시간에는 동일한 활동을 할 수 없다는 뜻) 할 수 있다고 가정 할 때 한 사람이 수행 할 수있는 최대 활동 수를 선택하는 문제라고 본다. [출처] https://aleen42.github.io/PersonalWiki/Algorithmn/Analysis/Greedy/Activity/Activity.html 예를들어 A라는 영업사원이 판매를 위해 a,b,c, 3개 업체와 미팅을 해야하는데 각 회의이 시작 시간과 회의 종료시간이 다음과 같다고 할때 A영업사원은 최대한 ..
탐욕 알고리즘(Greedy Algorithm)이란? 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 문제를 해결과는 과정에서 결정(decsion) or 선택의 순간이 오면 그 순간만큼은 가장 최적의 답을 선택하여 최선의 결과를 만들어 내자라는 컨셉을 가지고 있는 알고리즘이다. 예를들어, A를 출발하여 B 경유지를 거처 목적지 C로 갈때 ( A -> B - > C) A->B 로 갈때 선택 할 수 있는경로가 3개가 있고 B->C 는 4개의 경로가 경로가 있다고 하면 A->B 로 갈수 있는 경로 3개중 1나를 선택한다면 가장 짧은 경로를 선택하고 B->C 로 갈때도 가장 빨리 갈수 있는 경로를 선택해서 최종적으로 A->C로 갈때 가장 빨리 갈수 있는 길을 찾아낼수 있다. 매 선택의 순간마다 항상 최소, 최대 또는 가장 최선의 답만 선택하..

티스토리툴바