매순간 현재 기준으로 최선의 답을 선택해 나가는 기법
- 빠르게 근사치를 계산할 수 있다.
- 결과적으로는 최적해가 아닐 수 있다.
* 정렬 안 된 상태로 그리디 사용 불가
그리디 알고리즘 적용 조건 : 이 두 가지 만족시 적용 가능
* 최적부분 구조 (Optimal substructure)
: 전체 문제의 최적해는 부분 문제의 최적해로 이어짐.
* 탐욕적 선택 특성 (Greedy Choice Property)
지금 선택이 다음 선택에 영향을 주지 않음. -> 현재 마주하는 문제가 미래에 영향을 받아 최적이 아니게 바뀌지 않는다 !
이 개념이 좀 헷갈렸는데 500 100 50 10 같은 완벽하게 그리디 적용할 수 있는 것도 내가 지금 500원을 고르냐 안 고르냐에 따라서 100원의 선택값이 달라지니까 영향을 줄거라고 생각이 든다. 근데 이 경우는 그리디 적용이 가능한 거고
500 400 100 50 10 이 있었을 때는 그리디를 적용했을 때 최적해가 나오지 않아서 안 된다. 헷갈린다
다른 분이 질문하셔서 강사님이 답변해주신 건데 음.. 일단 정렬이 중요하고
아 ! 다른 글을 봤는데
뭔가 알 것도 같다. 800원을 거슬러줘야한다고 할 때 500 * 1 , 100 * 3가 최적인데
400원 화폐도 있을 500원을 고르면 최적은 400 *2 인데 이것을 고르지 못하게 된다.
그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다.
아 이말도 어렵고 ... 흠
여러 글을 읽어보면서 이렇게 생각하면 될 것 같다. 그리디는 매 순간 최적을 구하는데
800원을 거슬러줘야할 때 500원이 최적이라고 생각해서 골랐는데 그러면 동전을 4개 쓰게 되니까 (500 *1, 100 *3)
(400*2) 2개를 쓰는 최적해가 아니게 된다. 현재 마주하는 문제가 미래에 영향을 받아 최적이 아니게 바뀌지 않는다 !
그래서 탐욕적 선택 특성을 만족하지 않는 것 !
대표문제 :
1. Activity Selection Problem : N개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때,
한 사람이 최대한 많이 할 수 있는 활동 구하기.
종료시간 기준으로 정렬해서 빠른 것부터 택하고 다음 활동의 시작시간이 종료시간보다 이후인 것을 선택.
2. 거스름돈 (동전의 갯수 가장 적게)
Main) Activity Selection Problem문제
* 생각해야할 것 :
1. 무조건 종료시간 기준으로 정렬하고 시작
2. 다음 활동을 고를 때 현재 끝난 종료시간보다 이후에 시작하는 걸 골라야함.
import java.util.*;
class Activity implements Comparable<Activity>{
String name;
int start;
int end;
public Activity(String name, int start, int end) {
this.name = name;
this.start = start;
this.end = end;
}
@Override
public int compareTo(Activity o) {
return this.end - o.end;
}
}
public class Practice {
static void selectActivity(ArrayList<Activity> list) {
//종료시간 기준 오름차순 정렬
//Collections.sort(list, (x, y) -> x.end- y.end);
Collections.sort(list);
int curTime = 0;
ArrayList <Activity> result = new ArrayList<>();
for (Activity item : list) {
if (curTime <= item.start) {
curTime = item.end;
result.add(item);
}
}
for (Activity item : result) {
System.out.print(item.name + " ");
}
System.out.println();
}
public static void main(String[] args) {
// Test code
ArrayList<Activity> list = new ArrayList<>();
list.add(new Activity("A", 1, 5));
list.add(new Activity("B", 4, 5));
list.add(new Activity("C", 2, 3));
list.add(new Activity("D", 4, 7));
list.add(new Activity("E", 6, 10));
selectActivity(list);
}
}Practice 2 ) 거스름돈 문제
강사님은 HashMap으로 어떤 동전이 얼마나 필요한지 저장하고 출력하셨음.
import java.util.*;
public class Practice {
public static void getChangeCoins(int receive, int price) {
int change = receive - price;
int []money = {500, 100, 50, 10};
int cnt = 0;
for (int i = 0; i < money.length ; i++) {
cnt += change / money[i];
change %= money[i];
}
System.out.println(cnt);
}
public static void main(String[] args) {
// Test code
getChangeCoins(1000, 100);
getChangeCoins(1234, 500);
}
}<그리디 문제풀이>
Practice 1)
// 각 원소의 값은 해당 위치에서 오른쪽으로 이동할 수 있는 최대 값이다.
// 첫 번째 위치에서 시작해서 가장 끝까지 이동이 가능한지 판별하는 프로그램을 작성하세요.
// 이동이 가능하면 true, 불가능하면 false 를 반환하세요.
// 입출력 예시
// nums: 2, 3, 0, 1, 4
// 출력: true
// nums: 3, 0, 0, 1, 1
// 출력: true
// nums: 3, 2, 1, 0, 4
// 출력: false
각 지점에서 맨 끝까지 갈 수 있는지
현재 지점에서 최적을 고른다. 음 근데 고른다기보단 그냥 for문돌려서 한 요소씩 검사하면 되지 않나 ?
그리고 이건 정렬도 안 했는데 그리디인가 이게 ?
import java.util.*;
public class Practice {
public static boolean solution(int []nums) {
int end = nums.length - 1;
for (int i = 0; i < nums.length; i++) {
if (i + nums[i] == end) {
return true;
}
}
return false;
}
public static void main(String[] args) {
// Test code
int[] nums = {2, 3, 0, 1, 4};
System.out.println(solution(nums));
nums = new int[]{3, 0, 0, 1, 1};
System.out.println(solution(nums));
nums = new int[]{3, 2, 1, 0, 4};
System.out.println(solution(nums));
}
}Practice 2) pre코테에도 나왔던 주식문제 ..
// 각 원소의 의미는 주식 가격을 의미한다.
// 한 번에 한 주만 보유할 수 있다고 할 때 prices 를 보고 사고 팔기를 반복해서
// 얻을 수 있는 최대 수익을 반환하는 프로그램을 작성하세요.
// 입출력 예시
// prices: 5, 1, 6, 4, 3, 5
// 출력: 7
// prices: 1, 2, 3, 4, 5
// 출력: 4
정말 간단하게 배열을 1부터 돌려서 arr[i]가 arr[i - 1]보다 크면 answer += arr[i] - arr[i - 1]; 해줌
import java.util.*;
public class Practice {
public static int solution(int []arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int answer = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i - 1] < arr[i]) {
answer += arr[i] - arr[i - 1];
}
arr[i - 1] = arr[i];
}
return answer;
}
public static void main(String[] args) {
// Test code
int[] prices = {5, 1, 6, 4, 3, 5};
System.out.println(solution(prices));
prices = new int[]{1, 2, 3, 4, 5};
System.out.println(solution(prices));
prices = new int[]{5, 4, 3, 2, 1};
System.out.println(solution(prices));
}
}Practice 3 )
// 1. n 이 짝수인 경우, 2로 나누기 연산
// 2. n 이 홀수일 때는 1 을 더하거나 1을 빼는 연산
// 주어진 n 이 1 이 되는데 필요한 최소한의 연산 횟수를 반환하세요.
// 입출력 예시
// n: 8
// 출력: 3
// n: 7
// 출력: 4
// n: 9
// 출력: 4
여기서는 규칙을 찾아봐야 하는데
n이 7일 경우 7 -> 8 -> 4 -> 2 -> 1
7 -> 6 -> 3 -> 4 -> 2 -> 1
7 -> 6 -> 3 -> 2 -> 1
이렇게 있는데 분기케이스를 모두 검사하면 복잡도 증가.
홀수를 4의 배수로 만들어주는게 좋음.
import java.util.*;
public class Practice {
public static int solution(int n) {
if (n == 0 || n == 2) {
return 1;
}
if (n == 1) {
return 0;
}
int answer = 0;
while (n != 1) {
if (n == 3) {
answer += 2;
break;
}
if (n % 2 == 0) {
n /= 2;
} else {
if ((n + 1) % 4 == 0) {
n += 1;
} else if ((n - 1) % 4 == 0) {
n -= 1;
}
}
answer++;
}
return answer;
}
public static void main(String[] args) {
// Test code
System.out.println(solution(8)); // 3
System.out.println(solution(7)); // 4
System.out.println(solution(9)); // 4
System.out.println(solution(6)); // 3
}
}Practice 4)
// 각 주유소의 가스 보유량은 gas 배열에 주어지고,
// 해당 주유소에서 다음 주유소로의 이동 비용은 cost 배열에 주어진다.
// 어떤 위치에서 차량이 가스를 채워 출발하면 모든 주유소를 방문하고 원래의 위치로 돌아올 수 있는지
// 계산하는 프로그램을 작성하세요.
// 입출력 예시
// gas: 1, 2, 3, 4, 5
// cost: 3, 4, 5, 1, 2
// 출력: 3
// gas: 2, 3, 4
// cost: 3, 4, 3
// 출력: -1
모든 위치를 다 돌면서 일일히 계산하기는 오래걸리니까
curGas가 음수에서 양수로 넘어가는 구간을 start위치로 잡고
curGas는 현재 주유소에서 출발할 수 있는지 여부를 알려줌.
import java.util.*;
public class Practice {
public static int solution(int gas[], int cost[]) {
if (gas == null || cost == null) {
return -1;
}
if (gas.length != cost.length) {
return -1;
}
int curGas = 0; //현재가스
int totalGas = 0; //가스 총량
int startPos = 0; //시작부분
for (int i = 0; i < gas.length; i++) {
curGas += gas[i] - cost[i];
totalGas += gas[i] - cost[i];
if (curGas < 0) {
startPos = i + 1; //시작지점 업데이트
curGas = 0;
}
}
return totalGas >= 0 ? startPos : -1;
}
public static void main(String[] args) {
// Test code
int[] gas = {1, 2, 3, 4, 5};
int[] cost = {3, 4, 5, 1, 2};
System.out.println(solution(gas, cost));
gas = new int[]{2, 3, 4};
cost = new int[]{3, 4, 3};
System.out.println(solution(gas, cost));
}
}Practice 5)
// num 숫자에서 두 자리를 최대 한번만 교체하여 얻을 수 있는 최대값을 출력하세요.
// 입출력 예시
// num: 2736
// 출력: 7236
// 입력: 7116
// 출력: 7611
maxArr에 원본 cArr보다 큰 값들을 넣어줌. 이렇게 되면 바꿀 위치를 알 수 있음.
import java.util.*;
public class Practice {
public static int solution(int num) {
char []cArr = String.valueOf(num).toCharArray();
int []maxArr = new int[cArr.length];
int max = 0;
for (int i = cArr.length - 1; i >= 0; i--) {
//반복문을 역순으로 돌면서 maxArr에 저장해놓으면 나중에 원본이랑 비교 했을 때 바뀔 값이 있는 위치를 알게됨
max = Math.max(max, cArr[i] - '0');
maxArr[i] = max;
}
for (int i = 0; i < cArr.length - 1; i++) { //한자리 문자에 '0' 아스키 코드 값을 빼면 숫자로 나온다.
if (cArr[i] - '0' < maxArr[i + 1]) {
for (int j = cArr.length - 1; j >= i + 1; j--) {
if (cArr[j] - '0' == maxArr[i + 1]) { //왜여기가 i + 1인지 모르겠다
char tmp = cArr[j];
cArr[j] = cArr[i];
cArr[i] = tmp;
return Integer.parseInt(String.valueOf(cArr));
}
}
}
}
return num;
}
public static void main(String[] args) {
// Test code
System.out.println(solution(2736));
System.out.println(solution(7116));
System.out.println(solution(91));
}
}후.. 좀 어렵네
'알고리즘 > 개념' 카테고리의 다른 글
| 5주차 알고리즘 - 최소신장트리 (MST) (1) | 2023.08.10 |
|---|---|
| 5주차 알고리즘 복습 - 다이나믹 프로그래밍 (0) | 2023.08.06 |
| 5주차 알고리즘 복습 - 투 포인터 (0) | 2023.08.06 |
