[알고리즘] 탐욕 알고리즘 - Greedy

탐욕 알고리즘 - Greedy

탐욕 알고리즘은 매순간에 최적의 선택을 하는 과정을 통해 전역적인 최적해를 구하는 알고리즘이다.

학부 인공지능 수업에서 경사 하강 알고리즘의 개념을 배울 때 나왔던 내용을 여기서도 보게 되니 반가웠다.

탐욕 알고리즘 개념 및 그림 설명

탐욕 알고리즘을 적용하려면 여러가지 조건이 필요하다고 하는데 그림 설명의 왼쪽 그림처럼 local minimum이 최적해가 아닌 경우 탐욕 알고리즘은 적용할 수 없다고 한다.

 

Greedy 적용 문제

개념은 어느 정도 이해가 되지만 실제 문제에서 어떻게 적용해야 하는지 감이 잡히지 않아서 바로 관련된 문제를 풀어봤다.

LeetCode 75 Day 5 Greedy 문제

LeetCode75 문제들 중 Greedy 문제 2가지를 풀어봤는데 Greedy 알고리즘을 어떻게 적용해야 하는지 답을 찾아보기 전에 혼자서 풀어봤다. 난이도가 Easy였던 만큼 문제 풀이는 생각보다는 간단 했다.

121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

문제를 간단히 설명하면 주어진 가격 배열에서 얻을 수 있는 최대의 이익이 얼마인가를 찾는 문제이다.

물론 물건을 구매하는 시점은 판매 시점보다 앞서 있어야 한다.

 

샘플 입력과 출력은 다음과 같다.

// Sample 01
Input: prices = [7,1,5,3,6,4]
Output: 5

// Sample 02
Input: prices = [7,6,4,3,1]
Output: 0

 

혼자서 풀어 본 풀이는 아래와 같다.

public class No_121 {
    public static void main(String[] args) {
        int[] sample1 = new int[] {7,1,5,3,6,4};
        int[] sample2 = new int[] {7,6,4,3,1};

        System.out.println(maxProfit(sample1));
        System.out.println(maxProfit(sample2));
    }

    public static int maxProfit(int[] prices) {
        int maxProfit = -10000;
        int min = 20000;
        for (int i = 1; i < prices.length; i++) {
            if (min > prices[i - 1]) min = prices[i - 1];
            int profit = prices[i] - min;
            if (maxProfit < profit) maxProfit = profit;
        }
        return Math.max(maxProfit, 0);
    }
}

409. Longest Palindrome

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

 

이번 문제는 주어진 문자열의 문자들로 조합 가능한 palindrome(좌우 대칭이 같은 문자열)의 최대 길이를 구하는 문제이다.

예를 들면 "aaccd <- b -> dccaa" 와 같은 구조의 문자열을 palindrome이라고 한다. 

 

샘플 입력과 출력은 다음과 같다.

// Sample 01
Input: s = "abccccdd"
Output: 7 (-> "dccaccd")

// Sample 02
Input: s = "a"
Output: 1 (-> "a")

 

이 문제도 답을 찾기 전에 혼자서 풀어봤는데 테스트 코드가 긴 이유는 여러 번 틀려서 그렇다는..

이 문제를 풀 때 사고 과정은 아래와 같았다.

1. 문자의 갯수가 짝수라면 좌우 대칭이 같은 문자열을 만들 수 있으니 문자 갯수 그대로 더 해준다.
2. 문자의 갯수가 홀수라면 3부터는 -1 을 해주면 짝수를 만들 수 있으니 좌우 대칭이 같은 문자열을 만들 수 있으니 문자의 갯수 -1 만큼 더해준다.
3. 문자의 갯수가 홀수라도 가운데 단일 문자를 둘 수 있으니 문자의 갯수가 홀수인 경우 +1을 해준다.

public class No_409 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("abccccdd"));
        System.out.println(longestPalindrome("aaaccccdd"));
        System.out.println(longestPalindrome("aaabbbccccdd"));
        System.out.println(longestPalindrome("abzxccccdd"));
        System.out.println(longestPalindrome("a"));
        System.out.println(longestPalindrome("bb"));
        System.out.println(longestPalindrome("ccc"));
    }

    public static int longestPalindrome(String s) {
        int answer = 0;
        boolean hasSingleLetter = false;

        Map<Character, Integer> letterCount = new HashMap<>();
        for (char letter : s.toCharArray()) {
            letterCount.merge(letter, 1, Integer::sum);
        }

        for (char letter : letterCount.keySet()) {
            int count = letterCount.get(letter);
            if (count % 2 == 0) answer += count;
            else {
                hasSingleLetter = true;
                answer += (count - 1);
            }
        }

        if (hasSingleLetter)
            answer++;

        return answer;
    }
}

 

2개의 문제를 풀고 나서도 Greedy 알고리즘을 어떻게 적용하는 건지 감이 잡히지 않아 구글 찬스를 사용했다.

To Be Continued..