[day5] 탐욕 알고리즘

생각이 나는대로 짜는 방식...

최적부분구조 : 해결한 부분은 되돌아보지 않는 구조
중복부분구조 :

그 부분에서 최적값이 한개가 나오는데, 합쳐놓고 보니 오답이 나오는 구조
-> 탐욕알고리즘 완전 탐색으로 해결해야 한다!
-> 항상 증명을 해야하거나, 알고 있는 경우 (다익스트라 최단경로 알고리즘, Prim 알고리즘)

ex) 최소 신장트리(minimum spanning tree)

• prim 알고리즘
  ex) aaaabbcaaaaddd -> a4b2c1a4d3 run length 알고리즘?
  ex) 허프만 코딩 : 빈도수가 가장 많이 나온 것을 가장 적은 byte ?
  -> 허프만 트리

ex) 거스름돈 문제: 돈의 관계가 배수 관계가 성립하면 탐욕 알고리즘이지만, 그게 아닌 경우는 완전탐색을 해야한다.
ex) 부정방정식(변수의 개수보다 방정식 개수가 적은 경우): 중복조합으로 짤 경우 시간이 너무 오래걸리므로 dp로 풀기

ex) knapsack
Todo: 가방이 감당할 수 있는 무게, 가격의 총합 max
1) zero one knapsack : 모든 경우의 수

• 부분집합 이용해서 풀이(backtracking) or dp 알고리즘
• 종류: 보석의 개수가 무한개(동전알고리즘과 유사) / 한정적

#include <iostream>
#include <stdio.h>
#define MAXN 31
#define MAXW 1001
using namespace std;
//int j[][2] = { {0} , { 4, 40 }, {10, 50}, {20, 150} };
int jw[MAXN] = { 0, 4, 10, 20 };
int jp[MAXN] = { 0, 40, 50, 100 };
int N, W;
//knapsack1 - 보석이 무한개 : ans => 40 * 7
//중복해서 사용하는 경우 => 1차원 배열 dp
int dp1[MAXW];
int knapsack1() {
	for (int i = 1; i <= W; ++i) { //경우 : 기준 가방
		for (int j = 1; j <= N; ++j) { //검증 : 보석
			//i: 현재 가방 무게 , j: 새로 담을 보석
			if (i >= jw[j]) {
				if (dp1[i] < dp1[i - jw[i]] + jp[j]) {
					dp1[i] = dp1[i-jw[i]] + jp[j];
				}
			}
		}
	}

	return dp1[W];
}

//knapsack2 - 보석이 한개 : ans => 20 , 10kg: 200만원
//중복해서 사용 못하는 경우 => 2차원배열
int dp2[MAXN][MAXW]; //보석이 기준
int knapsack2() {
	for (int i = 1; i <= N; ++i) { //경우 : 기준 보석
		for (int j = 1; j <= W; ++j) { //검증 : 가방
			//i: 현재 보석 가격 , j: 새로 담을 보석
			dp2[i][j] = dp2[i - 1][j]; //복사시켜놔야 다음에 사용가능
			if (i >= jw[j]) {
				if (dp2[i][j] < dp2[i - 1][j - jw[i]] + jp[i]) {
					//직전 데이터로부터 덜어내고
					dp2[i][j] = dp2[i - 1][j - jw[i]] + jp[i];
				}
			}
		}
	}

	return dp2[N][W];
}

int main(int argc, char** argv)
{
	W = 30; N = 3;

	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

2) fraction knapsack : 탐욕 알고리즘

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define MAXN 31
#define MAXM 1001
int moneys[] = { 0, 1, 4, 6 };
int N; int MONEY;
using namespace std;

int dp[MAXM];
//최소 카운트를 세는 것! 
int getCnt() {
#if 0
	//최솟값 찾고 싶으므로, 무한대로 초기화
	for (int i = 1; i <= MONEY; ++i) { //0번지에는 0이여야함?
		dp[i] = 0x7fffffff;
	}
#endif 
	fill(dp + 1, dp + MONEY + 1, 0x7fffffff);

	for (int i = 1; i <= MONEY; ++i) {
		for (int j = 1; j <= N; ++j) {
			if (i >= moneys[j]) {
				if (dp[i] > dp[i - moneys[j]] + 1) {
					dp[i] = dp[i - moneys[j]] + 1;
				}
			}
		}
	}

	return dp[MONEY];
}


int main(int argc, char** argv)
{
	N = 3; //돈의 종류 개수
	MONEY = 8; //돌려받으려는 값

	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

<이미 만들어진 코드들, 문제를 읽고 해당 알고리즘인지 파악하고, 구현>
TSP
LIS
LCS
MCM
동전
knapsack
피보나치