8. 11

조합

NextPermutation 활용
  - 다음순열. 사전 순 다음에 오는 순열

전처리 -> 가장 작은 순열 만들고 출발.
  - 오름차 순 정렬 해야함.

do{
	순열 사용 로직.	
} while(np());

1. 꼭대기 찾기(i)
  - i-1 위치 사용할 것(교환위치)
2. 꼭대기 직전(i-1) 위치 교환값 찾기, 맨 뒤에서 부터
  - i-1 위치 값보다 한 단계 큼.(1만큼 큰 게 아닐때도 있음)
3. 꼭대기 직전(i-1) 위치 값과 교환값(j) 위치 값 교환.
4. 꼭대기 위치부터 맨 뒤까지 오름차순 정렬
  - 교환..교환..교환..
  
Bj 배열 돌리기 4에 이용.
  - 배돌 코드에 넥퍼 추가.

-----

static boolean np(int[] p){
        int N = p.length;
        int i = N-1;
        // 맨 뒤부터 꼭대기 찾기
        while(i>0 && p[i-1]>=p[i]) --i;

        if(i==0) return false; // 다음 순열이 없음. 가장 큰 순열

        //꼭대기 직전 위치에서 교환할 한 단계 큰 수 뒤쪽에서 부터 찾기
        int j = N-1;
        while(p[i-1]>= p[j]) --j;

        // 꼭대기 직전 수와 한 단계 큰 수 교환
        swap(p,i-1,j);

        // 꼭대기 부터 맨 뒤까지 교환.
        int k = N-1;
        while(i<k){
            swap(p,i++,k--);
        }
        return true;
    }

탐욕 알고리즘, Greedy Algorithm

최적해를 구하는 근시안적인 방법.

일반적으로 머리속으로 떠오른 생각 그대로 구현하면 Greedy 접근이 됨.
그 순간에 최적이라 생각하는 방법을 선택해 나가는 방식으로 최종까지.
한 번 선택한 것은 번복하지 않음. 믿으니까..!

배낭 짐싸기, Knapsack
  - 0-1 KnapSack
    - 배낭에 물건을 통째로!
    - 쪼갤 수 없다.
  - Fractional Knapsack
    - 물건을 부분적으로 담는 것이 허용.
    - 물건을 쪼갤 수 있는 경우
    
0-1 Knapsack에 대한 완전 검색 방법
  - 완전 검색으로 물건들의 집합 S에 대한 모든 부분집합을 구함.
  - 총 무게가 W를 초과하는 집합 바로바로 버림.
  - 개수가 증가하면 시간 복잡도가 지수적으로 증가..
    - 2^10 = 1024
    - 2^20 = 1048576
    - 2^30 = 약 10억..
  
0-1 Knapsack에 대한 탐욕적 방법.
  - 값이 비싼 물건 부터
  - 가벼운 물건 부터 채운다.
  - 무가비(무게 대비 가격비) 좋은 것부터 채운다.

탐욕 기법 활용 - 회의실 문제
  - 종료시간이 빠른 회의부터. (정렬)
  - 언제나 최적해로 향한다.

Bj11047 - 동전 0
  - 그냥 큰 단위부터 빼기
Bj1931 - 회의실 배정
  - comparator, lambda 사용.
  - nlogn 정렬 필요.
  - 끝나는 시간 기준으로 그리디~ 하게.
Bj11399 - ATM

Bj19621 - 회의실 배정 2
  - 그리디? 같은 느낌으로 시도했는데 반례를 모르겠음.
  - 편안 
    - 여전히 편안
    - 불편
  - 불편
    - 충돌..!
    - 여전히 불편.
    
반례 -> counter..example