탐욕 기법 & 분할 정복
Updated:
탐욕 기법
- 문제 제시 : 거스름돈 줄이기
- 손님이 지불한 금액에서 물건값을 제한 차액(거스름돈)을 지불하는 문제를 생각해보자
- “어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?”
- => 큰단위의 화폐를 가장 먼저 많이 사용!
- 탐욕 알고리즘의 장점은 모두 경우의 수를 다 해보는게 아니라 우리가 할 수 있는 선택 중 최선의 선택을 해가는 알고리즘.
- 내가 선택한 선택이 최선이라고 생각되어지면 그 외의 선택에 대해선 고민하지 않는다.
- 나머지를 고려하지 않기 때문에 시간적 우위에 있다.
- 탐욕 알고리즘은 최적해를 구하는데 사용되는 근시안적인 방법
- 최적화 문제란 가능한 해들 중에서 가장 좋은(최대 또는 최소)해를 찾는 문제이다
- 일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.
- 여러 경우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
- 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최정적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.
- 일단, 한번 선택된 것은 번복하지 않는다. 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순하며, 또한 제한적인 문제들에 적용된다.
- 단, 동전의 단위가 배수가 아니라 예를들어, 400원이 더 있다고 하면, 무조건 큰 단위부터 나누는 방법이 최선의 방법이 되지 않는다.
예시) 배낭 짐싸기
- 도둑은 부자들의 값진 물건들을 훔치기 위해 보관 창고에 침입하였다.
- 도둑은 훔친 물건을 배낭에 담아 올 계획이다. 배낭은 담을 수 있는 물건의 총 무게(W)가 정해져 있따.
- 창고에는 여러개(n개)의 물건들이 있고, 각각의 물건에는 무게와 값이 정해져 있다.
- 경배원들에게 발각되기 전에 배낭이 수용할 수 있는 무게를 초과하지 않으면서, 값이 최대가 되는물건들을 담아야 한다.
- Knapsack 문제유형
- 0-1 Knapsack
- 배낭에 물건을 통째로 담아야 하는 문제
- 물건을 쪼갤 수 없는 경우
- Fractional Knapsack
- 물건을 부분적으로 담는 것이 허용되는 문제
- 물건을 쪼갤 수 있는 경우
0-1 Knapsack에 대한 완전 검색 방법
- 완전 검색으로 물건들의 집합 S에 대한 모든 부분집합을 구한다.
- 부분집합의 총 무게가 W를 초과하는 집합들은 버리고, 나머지 집합에서 총 값이 가장 큰 집합을 선택할 수 있다.
- 물건의 개수가 증가하면 시간 복잡도가 지수적으로 증가한다 ( 크기 n인 부분집합의 수 2^n)
- 만약 n이 30이면 2^30 은 대략 10억이 되버린다. 그래서 이 방법으로 구할 수 없다.
0-1 Knapsack에 대한 탐욕적 방법
- 값이 비싼 물건부터 채운다.(최적 x)
- 무게가 가벼운 물건부터 채운다.(최적 x)
- 무게 당(예> kg당) 값이 높은 순서로 물건을 채운다.(최적 x)
Fractional Knapsack 문제
- 물건의 일부를 잘라서 담을 수 있다.
- 배낭에 물건을 꽉 채운다.
- 탐욕적인 방법=> 단위무게가 비싼거부터 채워넣는다.
문제 제시
- 김대리는 소프트웨어 개발팀들의 회의실 사용 신청을 처리하는 업무를 한다. 이번 주 금요일에 사용 가능한 회의실은 하나만 존재하고, 다수의 회의가 신청된 상태이다.
- 회의는 시작 시간과 종료 시간이 있으며, 회의 시간이 겹치는 회의들은 동시에 열릴 수 없다.
- 가능한 많은 회의가 열리기 위해서는 회의들을 어떻게 배졍해야 할까?
- 선택 가능한 회의 중 종료시간이 빠른 순서로 해결하는게 좋다.
- 종료 시간이 빠른 순서로 활동들을 정렬
- 첫 번째 활동을 선택한다.
- 선택한 활동의 종료시간보다 빠른 시작 시간을 가지는 활동을 모두 제거한다.
- 남은 활동들에 대해 앞의 과정을 반복한다.
탐욕 알고리즘의 필수 요소
- 탐욕적 선택 속성
- 탐욕적 선택은 최적해로 갈 수 있음을 보여라
- 즉, 탐욕적 선택은 항상 안전하다.
- 최적 부분 구조
- 최적화 문제를 정형화하라
- 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남는다.
- 원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해 임을 증명하라.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class MeetingRoomTest {
static class Meeting implements Comparable<Meeting>{
int start, end;
public Meeting(int start, int end) {
super();
this.start = start;
this.end = end;
}
@Override
public int compareTo(Meeting o) {
int value = this.end - o.end;
if(value != 0) return value; // 종료시간이 다르면
// 종료시간이 같다면 시작시간이 빠른 순서로.
return this.start - o.start;
}
@Override
public String toString() {
return "Meeting [start=" + start + ", end=" + end + "]";
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //회의 개수
Meeting[] meetings = new Meeting[N];
for (int i = 0; i < N; i++) {
meetings[i] = new Meeting(sc.nextInt(), sc.nextInt());
}
for(Meeting meeting: getSchedule(meetings)) {
System.out.println(meeting);
}
}
static ArrayList<Meeting> getSchedule(Meeting[] meetings){
ArrayList<Meeting> list = new ArrayList<Meeting>();
Arrays.sort(meetings); // 종료시간 기준 오름차순 정렬
list.add(meetings[0]); // 첫회의 추가.
for(int i=1,size=meetings.length; i<size; i++) {
if(list.get(list.size()-1).end <= meetings[i].start) {
list.add(meetings[i]);
}
}
return list;
}
}
분할 정복 기법
예시) 가짜 동전 찾기
- n개의 동전들 중에 가짜 동전이 하나 포함되어 있다. 가짜 동전은 진짜 동전에 비해 아주 조금 가볍다. 진짜 동전들의 무게가 동일하다고 할때 양팔 저울을 이용해서 가짜 동전을 찾아보자
- 양팔 저울을 최소로 사용해서 가짜 동전을 찾는 방법은 무엇인가?
- 예를 들어, 동전이 24(진짜 23, 가짜 1)개 있다면?
- 둘씩 쪼개어서 몸무게가 낮은 것을 비교해가면서 구한다.
분할정복 기법
- 유래 : 1805년 12월 2일 아우스터리츠 전투에서 나폴레옹이 사용한 전략
- 전력이 우세한 연합군을 공격하기 위해 나폴레옹은 연합군의 중앙부로 쳐들어가 연합군을 둘로 나눔
- 둘로 나뉜 연합군을 한 부분씩 격파함
- 설계 전략
- 분할 : 해결할 문제를 여러 개의 작은 부분으로 나눈다.
- 정복 : 나눈 작은 문제를 각각 해결한다.
- 통합 : 필요하다면 해결된 해답을 모은다.
거듭제곱
- 반복 알고리즘 : O(n)
- 슈도코드
Iterative_Power(x,n) result <- 1 for i in l -> n result <= result * X RETURN result - 분할 정복 기반의 알고리즘 : O(log2n)
- 슈도코드
Recursive_Power(x,n) if n==1 : RETURN x if n is even y<- Recursive_Poser(x, n/2) RETURN y*y else y<- Recursive_Poser(x,(n-1)/2) RETURN y*y*x - C^n = C^n/2 * C^n/2(n은 짝수)
- = C^(n-1)^2 * C^(N-1)^2 * C (n은 홀수)
public class SquareNumber {
static int callCnt;
//반복 알고리즘
static long exp1(long x, long y) {
callCnt++;
if(y==1) return x;
return x * exp1(x, y-1);
}
// 분할정복
static long exp2(long x, long y) {
callCnt++;
if(y==1) return x;
long r = exp2(x, y/2);
long res = r * r;
if(y%2==1) res *= x; //홀수일 떄
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
// System.out.println(exp1(x,y));
// System.out.println(callCnt);
System.out.println(exp2(x,y));
System.out.println(callCnt);
}
}
이진 검색
- 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
- 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함
- 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.
- O(log2N)의 시간복잡도걸린다.
병뚜껑 속의 숫자 게임
- 술래가 병뚜껑 속 숫자를 확인한 후, 다음 사람부터 숫자르 맞히기 시작한다. 술래는 up 또는 down을 통해 게임에 참여한 사람들이 병뚜껑 속 숫자에 점점 가까워질 수 있도록 힌트를 제시한다.
검색과정
- 자료의 중앙에 있는 원소를 고른다.
- 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
- 중앙 원소의 값과 찾고자 하는 목표 값이 일치하면 탐색을 끝낸다.
- 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
- 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.
- 슈도코드
binarySearch(S[], n, key) start <- 0 end <- n-1 while start <= end mid <- (start + end)/2 if S[mid] == key return mid elif S[mid] <key start <- mid + 1 elif S[mid] > key end <- mid - 1 END WHILE RETURN -1;
import java.util.Arrays;
public class BinarySearchTest {
public static void main(String[] args) {
int[] arr = {10,4,6,20,35,7};
Arrays.sort(arr); //값들을 오름차순 정렬
// 4,6,7,10,20,15
System.out.println(binarySearch(arr,6));
System.out.println(binarySearch(arr,35));
System.out.println(binarySearch(arr,50));
System.out.println(Arrays.binarySearch(arr,6));
System.out.println(Arrays.binarySearch(arr,35));
System.out.println(Arrays.binarySearch(arr,50));
}
//key에 해당하는 원소의 인덱스 리턴.
static int binarySearch(int[] arr, int key) {
int start = 0, end = arr.length-1;
while(start<=end) {
int mid = (start+end)/2; //중간 위치
if(arr[mid] == key) {
return mid;
}else if(arr[mid]<key) {
start = mid+1;
}else {
end = mid-1;
}
}
//못찾았다면
return -1;
}
}
Leave a comment