그리디 알고리즘
매 순간 현재 기준으로 최선의 답을 선택해 나가는 방법
- 빠르게 근사치를 계산할 수 있다
- 결과적으로는 최적해가 아닐 수도 있다
Acivity Selection Problem
N개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때, 한 사람이 최대한 많이 할 수 있는 활동 수 구하기
종료 시간 기준으로 정렬
먼저 종료되는 활동순, 겹치치 않는 순으로 선택
정렬하기 전에는 그리디 알고리즘 적용 불가
-> 종료 시간 관점에서는 C에 A가 영향이 없지만, 종료 시간과 시작시간을 비교햇을 때는 영향을 받으므로 선택 불가 ....
거스름돈
잔돈이 890일때 동전의 개수를 가장 적게 주는 경우
-> 큰 동전부터 계산
500원 짜리는 100원 5개로 구성됨(이걸 잘 생각해 보아야함)
-> 100원도 50원 2개 ....
그리디 알고리즘이 안되는 경우 예시
적용 조건
그리디 알고리즘은 빠르지만 최적해를 보장하지 못함
밑 두가지 조건에 해당하는 경우 적용 가능
- 탐욕적 선택 특성 : 지금 선택이 다음 선택에 영향을 주지 않음
- 최적 부분 구조 : 전체 문제의 최적해는 부분 문제의 최적해로 이루어짐
구현
// 알고리즘 - 그리디 알고리즘
// Activity Selection Problem
import java.util.ArrayList;
import java.util.Collections;
class Activity {
String name;
int start;
int end;
public Activity(String name, int start, int end) {
this.name = name;
this.start = start;
this.end = end;
}
}
public class Main {
public static void selectActivity(ArrayList<Activity> list) {
// 종료시간 기준 오름차순 정렬
Collections.sort(list, (x1, x2) -> x1.end-x2.end); // Comparable도 가능
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);
}
}
// 거스름돈 문제
import java.util.HashMap;
import java.util.Map;
public class Main2 {
public static void getChangeCoins(int receivedMoney, int price) {
final int[] coins = {500,100,50,10,5,1};
HashMap<Integer, Integer> result = new HashMap<>();
int change = receivedMoney - price;
int cnt = 0;
for (int i = 0; i < coins.length; i++) {
if(change < coins[i]){
continue;
}
int q = change / coins[i];
// coins[i] 키가 존재하지 않으면 기본값 : 0을 반환함
// coins[i]에 해당하는 key값이 이미 result 객체에 존재한다면 해당 key값에 대한 value를 가져오고
// 그렇지 않다면 0을 가져와서 key-value 쌍을 추가
// 단순히 result.put(coins[i], q)와 같이 작성하면, 만약 해당 key 값이 존재하지 않는 경우에는 null이 반환됩니다. 그리고 이후에 null + q가 수행되면서 NullPointerException이 발생합니다.
// 즉, result.getOrDefault를 사용하는 이유는, key 값이 존재하지 않는 경우에는 기본값인 0을 사용하여 null + q 연산이 수행되지 않도록 하기 위해서입니다. 이렇게 하면 NullPointerException을 방지할 수 있으며, 코드의 안정성을 높일 수 있습니다.
result.put(coins[i], result.getOrDefault(coins[i], 0) + q);
change %= coins[i];
cnt += q;
}
System.out.println("거스름돈 동전 개수 : " + cnt);
for(Map.Entry<Integer, Integer> cur : result.entrySet()){
System.out.println(cur.getKey() + ": " + cur.getValue());
}
}
public static void main(String[] args) {
// Test code
getChangeCoins(1000, 100);
getChangeCoins(1234, 500);
}
}연습 문제
문제 1
// Practice
// 정수형 nums 배열이 주어졌다.
// 각 원소의 값은 해당 위치에서 오른쪽으로 이동할 수 있는 최대 값이다.
// 첫 번째 위치에서 시작해서 가장 끝까지 이동이 가능한지 판별하는 프로그램을 작성하세요.
// 이동이 가능하면 true, 불가능하면 false 를 반환하세요.
// 입출력 예시
// nums: 2, 3, 0, 1, 4
// 출력: true
// nums: 3, 0, 0, 1, 1
// 출력: true
// nums: 3, 2, 1, 0, 4
// 출력: false
// 이중 for문이나 재귀 사용시에는 n^2 복잡도
public class Practice1 {
public static boolean solution(int[] nums) {
int pos = 0;
for (int i = 0; i < nums.length; i++) {
if(pos < i){
return false;
}else if(pos >= nums.length - 1){
return true;
}
pos = Math.max(pos, i + nums[i]);
}
return true;
}
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));
}
}문제 2
// Practice
// 양의 정수 배열 prices 가 주어졌다.
// 각 원소의 의미는 주식 가격을 의미한다.
// 한 번에 한 주만 보유할 수 있다고 할 때 prices 를 보고 사고 팔기를 반복해서
// 얻을 수 있는 최대 수익을 반환하는 프로그램을 작성하세요.
// 입출력 예시
// prices: 5, 1, 6, 4, 3, 5
// 출력: 7
// prices: 1, 2, 3, 4, 5
// 출력: 4
public class Practice2 {
public static int solution(int[] prices) {
if(prices == null || prices.length < 2){
return 0;
}
int profit = 0;
for(int i = 1; i < prices.length; i++){
if(prices[i] > prices[i-1]){
profit += prices[i] - prices[i-1];
}
}
return profit;
}
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));
}
}
문제 3
// Practice
// 양의 정수 n 이 주어지고 다음의 연산을 수행할 수 있을 때,
// 1. n 이 짝수인 경우, 2로 나누기 연산
// 2. n 이 홀수일 때는 1 을 더하거나 1을 빼는 연산
// 주어진 n 이 1 이 되는데 필요한 최소한의 연산 횟수를 반환하세요.
// 입출력 예시
// n: 8
// 출력: 3
// n: 7
// 출력: 4
// n: 9
// 출력: 4
public class Practice3 {
public static int solution(int n) {
if(n == 0 || n == 2){
return 1;
}
if(n == 1){
return 0;
}
int cnt = 0;
while(n != 1){
if(n == 3){
cnt += 2;
break;
}
if(n % 2 == 0){
n /= 2;
}else if((n+1) % 4 ==0){
n += 1;
}else if((n-1) % 4 == 0){
n -= 1;
}
cnt++;
}
return cnt;
}
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
}
}문제 4
// Practice
// 원형 루트 상에 n 개의 주유소가 있다.
// 각 주유소의 가스 보유량은 gas 배열에 주어지고,
// 해당 주유소에서 다음 주유소로의 이동 비용은 cost 배열에 주어진다.
// 어떤 위치에서 차량이 가스를 채워 출발하면 모든 주유소를 방문하고 원래의 위치로 돌아올 수 있는지
// 계산하는 프로그램을 작성하세요.
// 입출력 예시
// gas: 1, 2, 3, 4, 5
// cost: 3, 4, 5, 1, 2
// 출력: 3
// gas: 2, 3, 4
// cost: 3, 4, 3
// 출력: -1
public class Practice4 {
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));
}
}문제 5
// Practice
// 정수 num 이 주어졌을 때,
// num 숫자에서 두 자리를 최대 한번만 교체하여 얻을 수 있는 최대값을 출력하세요.
// 입출력 예시
// num: 2736
// 출력: 7236
// 입력: 7116
// 출력: 7611
public class Practice5 {
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--) {
max = Math.max(max, cArr[i] - '0');
maxArr[i] = max;
}
for(int i = 0; i < cArr.length-1; i++){
if(cArr[i] - '0' < maxArr[i+1]){
for(int j = cArr.length - 1; j >= i + 1; j--){
if(cArr[j] - '0' == maxArr[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));
}
}
Journey for Backend Developer