그리디 알고리즘
그리디 알고리즘 (Greedy Algorithm)
매 순간 현재 기준으로 최선의 답을 선택해 나가는 기법
빠르게 근사치를 계산할 수 있다.
결과적으로는 최적해가 아닐 수도 있다.
그리디 알고리즘 예시_1 (1)
Activity Selection Problem
N 개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때, 한 사람이 최대한 많이 할 수 있는 활동의 수 구하기
그리디 알고리즘 예시_1 (2)
Activity Selection Problem
종료 시간 기준으로 정렬 → 먼저 종료되는 활동 순, 겹치지 않는 순으로 선택
그리디 알고리즘 예시_2 (1)
거스름돈 (동전의 개수 가장 적게)
잔돈: 890
동전 종류: 10, 50, 100, 500
큰 동전부터 계산
그리디 알고리즘 예시_2 (2)
거스름돈 (동전의 개수 가장 적게)
잔돈: 890
동전 종류: 10, 50, 100, 400, 500
큰 동전부터 계산
그리디 알고리즘 적용 조건
그리디 알고리즘은 빠르지만 최적해를 보장하지는 못함
하기 두 가지 조건에 해당하는 경우 적용 가능
탐욕적 선택 특성 (Greedy choice property)
지금 선택이 다음 선택에 영향을 주지 않음
최적 부분 구조 (Optimal substructure)
전체 문제의 최적해는 부분 문제의 최적해로 이루어짐
알고리즘 - 그리디 알고리즘
// 알고리즘 - 그리디 알고리즘
// 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);
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);
}
}
C B E
거스름돈 문제
// 거스름돈 문제
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++) {
// 동전 단위가 잔돈보다 크면 continue
if (change < coins[i]) {
continue;
}
// 해당 동전 개수
int q = change / coins[i];
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);
}
}
거스름돈 동전 개수: 5
500: 1
100: 4
거스름돈 동전 개수: 10
1: 4
500: 1
100: 2
10: 3
문제풀이
// 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
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 계산
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));
}
}
true
true
false
// 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));
}
}
7
4
0
// 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) {
// 0 이나 1 이면 더하기 또는 나누기 연산 1회
if (n == 0 || n == 2) {
return 1;
}
// 1 이면 연산 필요 없음
if (n == 1) {
return 0;
}
int cnt = 0;
while (n != 1) {
// 3 인 경우는 3 -> 2 -> 1 로 2 더해주고 break
if (n == 3) {
cnt += 2;
break;
}
// 짝수인 경우 나누기 2
// 홀수일 때는 4의 배수가 되는 쪽으로 증감
if (n % 2 == 0) {
n /= 2;
} else if ((n + 1) % 4 == 0) {
n = n + 1;
} else if ((n - 1) % 4 == 0) {
n = 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
}
}
3
4
4
3
// 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) {
// 각 위치에서 출발할 때 gas 충전량 - cost 를 기록
// 전체 계산을 했을 때 total 양이 0 보다 크면 가능 0 보다 작으면 불가능
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));
}
}
3
-1
// 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];
// 역순으로 부분 max 배치
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++) {
// 현재 값이 부분 max 보다 작으면 교체
if (cArr[i] - '0' < maxArr[i + 1]) {
// 역순으로 해당 부분 max 가 처음 등장했던 곳 찾아서 교체
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));
}
}
7236
7611
91
출처 : 제로베이스
Leave a comment