Brute force Study

작업 스케줄링 문제앞으로 해야 할 작업 목록을 가지고 있다고 해보자. 어떤 작업을 어떤 순서로 시행해야 할까?  Case 1) 특정 시점에 오직 하나의 작업만 수행할 수 있을 때솔루션) 종료 시간 기준각각의 작업은 고유한 ID, 시작 시간, 종료 시간을 갖는다. 이러한 작업을 표현할 구조체를 생성하자. 이 구조체는 인스턴스로 각 작업을 표현한다.N개의 작업을 포함하는 list를 생성한다. 각 작업은 1부터 N까지 고유한 ID를 가지며, 시작 시간과 종료 시간은 임의의 정수로 설정한다스케줄링 함수를 작성한다종료 시간을 기준으로 전체 작업 리스트를 정렬한다.현재 리스트에서 그리디 방식으로 가장 빠른 종료 시간을 갖는 작업을 선택하자현재 선택된 작업과 시간이 겹치는 작업은 모두 제거한다. 즉, 현재 작업 종료..

배낭 문제0-1 배낭 문제라고 부르는 일반 배낭 문제는 NP-완전 문제로 알려져 있어 다항 시간 솔루션을 사용할 수 없다.하지만 문제를 조금 변경한 분할 가능 배낭 문제(fractional knapsack problem)은 그리디 방식으로 해결할 수 있다. 0-1 배낭 문제물건들의 집합 O = [O1, O2, O3, .... , On]이 있고, 여기서 i번째 물건 Oi의 무게는 Wi이고 가격은 Vi라고 하자.그리고 최대 무게를 T까지 견딜 수 있는 가방(배낭)이 하나 주어진다이제 물건들을 가방에 담아야 하는데, 가방에 넣은 물건들의 가격 합이 최대가 되로록 물건을 선택해야 한다물건들의 무게 합이 T를 넘지 않아야 한다.위에서 말했듯이 0-1 배낭 문제는 NP-완전 문제로 알려져 있어 다항 시간 솔루션을 ..

최단 작업 우선 스케줄링사람들이 은행 창구에 줄을 서서 순서를 기다리는 상황을 생각해보자. 대기열에는 N명의 사람이 기다리고 있다.각 사람마다 일 처리에 필요한 시간은 다르다대기열에 기다리고 있던 모든 사람이 매우 합리적이어서 평균 대기 시간이 최소화될 수 있도록 대기 순서를 다시 정하는 것에 동의한다고 가정한다.따라서 평균 대기 시간을 최소화하는 것이 목표이다.가능한 많은 사람의 대기 시간을 줄일 수 있는 방법을 찾아보자.일 처리가 가장 빨리 끝나는 사람을 맨 앞에 세워야 한다 최단 작업 우선 스케줄링 구현최단 작업 우선 스케줄링을 구현하는 것은 매우 단순하다. 일 처리 소요 시간 순으로 오름차순으로 정렬하면 된다.정렬 전 대기 시간과 정렬 후 대기 시간을 비교해보는 코드를 작성해보자 #include ..

그리디 알고리즘(greedy algorithm)이란?알고리즘 설계 패러다임 중 하나로, 매 단계에서 '가장 좋아 보이는' 해답을 선택하는 알고리즘이다. 매 단계마다 전체적으로 최적인지는 판단하지 않고 현재 최적이라고 판단되는 결정을 함. 즉 과거(이전 선택)나 미래(앞으로의 선택)는 생각하지 않고, 오직 현재의 최대 만족만을 추구. (근시안적 선택)그리디 방법은 지역적인 최적의 해결 방법으로부터 전역적인 최적의 해결 방법을 구성하는 방식이다.  Example) 지도 지도 서비스에서 두 지점의 최단 이동 경로 기능을 제공한다이 때, 출발 지점에서 아직 방문하지 않은 가장 가까운 지점까지의 경로를 찾고, 이를 목적 지점에 다다를 때 까지 반복하여 경로를 구한다.(다익스트라 알고리즘의 기본 개념) 그리디 접근..