Post

Greedy

Posted
By Hyoeun Choi
19 min read
Greedy

1. What is a Greedy Algorithm? (Concept and Working Principle)

As the name suggests, Greedy Algorithms adopt a “greedy” approach. This means they are algorithms that arrive at a final solution by making the locally optimal choice at each step. By selecting what appears to be the best option in the current situation, they attempt to find the globally optimal solution for the entire problem.

While this approach has the advantage of being simple and efficient, it doesn’t always guarantee an optimal solution. For a greedy algorithm to work successfully, it must satisfy two properties:

  • Greedy Choice Property: The greedy choice made at each step must contribute to finding the overall optimal solution, independent of future choices. In other words, the current optimal choice should not hinder any future optimal choices.
  • Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions to its subproblems. This property also appears in Dynamic Programming, but the difference in greedy algorithms is that they proceed directly to the next step via a greedy choice without separate calculations to find the optimal solution for subproblems.

Working Principle:

  1. Identify Problem Characteristics: First, determine if the problem can be solved using a greedy algorithm.
  2. Define Selection Criteria: Define clear criteria for what constitutes the “most optimal” choice at each step.
  3. Iterative Selection: Repeatedly make the most optimal choice in the current situation according to the defined criteria.
  4. Derive Final Result: Once all steps are complete, obtain the final result.

2. Solving Greedy Algorithm Problems: The Change-Making Problem (Example)

Let’s look at one of the most classic examples of a greedy algorithm: the Change-Making Problem.

Problem: You need to give change for $N$ Won. The available denominations are 500 Won, 100 Won, 50 Won, and 10 Won. How can you give change for $N$ Won using the minimum number of coins? (Assume you have an ample supply of each coin.)

Greedy Approach: Use as many of the largest denomination coins as possible first.

Solution Process:

  1. Calculate the maximum number of 500 Won coins that can be used from $N$ Won.
  2. Calculate the remaining amount after subtracting the value of the 500 Won coins.
  3. Repeat the above process for the remaining amount using the next largest denomination, 100 Won.
  4. Continue this process until all coin denominations have been used.

Pseudocode:

1
2
3
4
5
6
7
8
9
10

function getChange(N, coins):
    total_coins = 0
    coins.sort(descending) // Sort coins from largest to smallest denomination

    for coin in coins:
        num_coin = N / coin  // Maximum number of current coin that can be given
        total_coins += num_coin
        N = N % coin         // Update remaining amount

    return total_coins

Python Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def get_change(n_amount: int, coins: list) -> int:
    """
    A greedy algorithm to give change for a given amount using the minimum number of coins.

    Args:
        n_amount: The total amount to give change for.
        coins: A list of available coin denominations (e.g., [500, 100, 50, 10]).

    Returns:
        The minimum number of coins.
    """
    total_coins = 0
    # Sort coins in descending order (key to the greedy choice)
    coins.sort(reverse=True) 

    for coin in coins:
        num_coin_current = n_amount // coin  # Max number of current coin to use
        total_coins += num_coin_current
        n_amount %= coin                   # Update the remaining amount

    return total_coins

# Example Usage
amount = 1260
available_coins = [500, 100, 50, 10]
print(f"Minimum coins needed for {amount} Won: {get_change(amount, available_coins)}") # Output: Minimum coins needed for 1260 Won: 6 (500*2 + 100*2 + 50*1 + 10*1)

Time and Space Complexity Analysis:

  • Time Complexity: If the length of the coins list is $M$, coins.sort() takes $O(M \log M)$. The subsequent for loop iterates $M$ times, taking $O(M)$. Therefore, the total time complexity is $O(M \log M)$. If the coins are already sorted, it’s $O(M)$.
  • Space Complexity: It uses very little additional space beyond storing the coin list, so it’s $O(1)$ (or $O(M)$ if sorting creates a copy).

3. Greedy Algorithm Tips and Pitfalls for Coding Interviews

While greedy algorithms are intuitive, as mentioned earlier, they don’t always guarantee an optimal solution. When you encounter a greedy algorithm problem in a coding interview, keep the following points in mind:

Tip 1: Validate the Greedy Choice

If you think a problem can be solved greedily, ask yourself: “Will this greedy choice truly lead to the overall optimal solution?” Try solving a few small test cases manually to see if there are any scenarios where the greedy choice fails. If the greedy choice doesn’t always guarantee optimality, you might need to consider dynamic programming or another algorithm.

Tip 2: The Importance of Sorting

In many greedy problems, sorting plays a crucial role. Like the change-making problem above, processing the largest/smallest elements first or sorting data according to specific criteria can maximize the efficiency of your greedy choice. Consider what criteria you should sort by to make the optimal selection.

Tip 3: Practice Finding Counterexamples

For greedy algorithms, it’s essential to practice finding counterexamples. If a greedy approach fails to find the optimal solution in certain cases, that counterexample can help you view the problem from a different perspective or prove that the greedy conditions don’t hold.

Tip 4: The Boundary with Dynamic Programming

Greedy algorithms and dynamic programming can both be used to solve problems with optimal substructure, making them easy to confuse. The key differences are:

  • Greedy: Makes a locally optimal choice at each step, and this choice does not affect the solution of subsequent problems.
  • Dynamic Programming: Stores optimal solutions to subproblems and uses them to construct the optimal solution for larger problems. Previous choices can influence subsequent steps, and it’s used when all possible cases need to be considered.

If a greedy choice leads to a situation where it’s “optimal right now, but negatively impacts future choices, ultimately not leading to the optimal solution,” then it’s highly likely you should consider dynamic programming. For instance, in the Knapsack Problem, a greedy approach of simply picking items with the highest value-to-weight ratio doesn’t always guarantee the optimal solution.

Conclusion

Greedy algorithms are a crucial concept that frequently appears in coding interviews. While they are intuitive and relatively easy to implement, making them applicable to many problems, you must approach them carefully as they don’t always guarantee the optimal solution.

When solving greedy algorithm problems, ask yourself the following questions:

  • Is a greedy approach valid for this problem? (Does it satisfy the greedy choice property and optimal substructure?)
  • What criteria will I use to make the “optimal choice”? (e.g., sorting criteria)
  • Are there any counterexamples where the greedy choice fails?

By consistently practicing problem-solving and developing an intuition for greedy algorithms, you’ll be able to confidently tackle problems in coding interviews. Feel free to ask if you have any questions!

1. 그리디 알고리즘이란 무엇인가? (개념 및 작동 원리)

그리디 알고리즘은 이름 그대로 “탐욕스러운” 접근 방식을 취합니다. 즉, 각 단계에서 가장 최적이라고 판단되는 선택을 당장(locally) 내리는 방식으로 최종 해답에 도달하는 알고리즘입니다. 현재 상황에서 가장 좋아 보이는 것을 선택함으로써 전체 문제의 최적해(globally optimal solution)를 찾으려고 시도하죠.

이러한 접근 방식은 간단하고 효율적이라는 장점이 있지만, 항상 최적의 해를 보장하는 것은 아닙니다. 그리디 알고리즘이 성공적으로 작동하려면 다음 두 가지 속성을 만족해야 합니다.

  • 탐욕적 선택 속성 (Greedy Choice Property): 각 단계에서 이루어지는 그리디(탐욕적인) 선택이 나중에 이루어질 선택과 무관하게 전체 문제의 최적해를 찾는 데 도움이 되어야 합니다. 즉, 현재의 최적 선택이 미래의 어떤 최적 선택을 방해해서는 안 됩니다.
  • 최적 부분 구조 (Optimal Substructure): 문제의 최적해가 부분 문제의 최적해로 구성될 수 있어야 합니다. 이는 동적 계획법(Dynamic Programming)에서도 나타나는 속성이지만, 그리디 알고리즘에서는 부분 문제의 최적해를 찾기 위해 별도의 계산 없이 그리디 선택을 통해 바로 다음 단계로 넘어간다는 차이가 있습니다.

작동 원리:

  1. 문제의 특징 파악: 그리디 알고리즘으로 해결 가능한 문제인지 먼저 파악합니다.
  2. 선택 기준 정의: 각 단계에서 “가장 최적”이라고 판단할 수 있는 명확한 기준을 정의합니다.
  3. 반복적인 선택: 정의된 기준에 따라 현재 상황에서 가장 최적의 선택을 반복적으로 수행합니다.
  4. 최종 결과 도출: 모든 단계가 완료되면 최종 결과를 얻습니다.

2. 그리디 알고리즘 문제 풀이: 거스름돈 문제 (예시)

그리디 알고리즘의 가장 대표적인 예시 중 하나인 거스름돈 문제를 살펴보겠습니다.

문제: 당신은 $N$원을 거슬러 주어야 합니다. 사용할 수 있는 동전은 500원, 100원, 50원, 10원입니다. 최소한의 동전 개수로 $N$원을 거슬러 주려면 어떻게 해야 할까요? (단, 동전의 개수는 충분하다고 가정합니다.)

그리디적 접근: 가장 큰 단위의 동전부터 최대한 많이 사용하는 것입니다.

풀이 과정:

  1. 가장 큰 단위인 500원 동전부터 $N$원에서 최대로 사용할 수 있는 개수를 계산합니다.
  2. $N$원에서 500원 동전으로 거슬러 준 금액을 제외한 나머지 금액을 계산합니다.
  3. 남은 금액에 대해 다음으로 큰 단위인 100원 동전으로 위 과정을 반복합니다.
  4. 모든 동전 단위를 소진할 때까지 이 과정을 반복합니다.

의사 코드 (Pseudocode):

1
2
3
4
5
6
7
8
9
10

function getChange(N, coins):
    total_coins = 0
    coins.sort(descending) // 동전을 큰 단위부터 정렬

    for coin in coins:
        num_coin = N / coin  // 현재 동전으로 거슬러 줄 수 있는 최대 개수
        total_coins += num_coin
        N = N % coin         // 남은 금액 업데이트

    return total_coins

Python 구현:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def get_change(n_amount: int, coins: list) -> int:
    """
    주어진 금액을 최소한의 동전 개수로 거슬러 주는 그리디 알고리즘.

    Args:
        n_amount: 거슬러 주어야 할 총 금액.
        coins: 사용할 수 있는 동전 단위 리스트 (예: [500, 100, 50, 10]).

    Returns:
        최소 동전 개수.
    """
    total_coins = 0
    # 동전을 내림차순으로 정렬 (그리디 선택의 핵심)
    coins.sort(reverse=True) 

    for coin in coins:
        num_coin_current = n_amount // coin  # 현재 동전으로 거슬러 줄 수 있는 최대 개수
        total_coins += num_coin_current
        n_amount %= coin                   # 남은 금액 업데이트

    return total_coins

# 예시 사용
amount = 1260
available_coins = [500, 100, 50, 10]
print(f"{amount}원을 거슬러주는데 필요한 최소 동전 개수: {get_change(amount, available_coins)}") # 출력: 1260원을 거슬러주는데 필요한 최소 동전 개수: 6 (500*2 + 100*2 + 50*1 + 10*1)

시간 복잡도 및 공간 복잡도 분석:

  • 시간 복잡도: coins 리스트의 길이를 $M$이라고 할 때, coins.sort()는 $O(M \log M)$이 걸립니다. 이후 for 루프는 $M$번 반복되므로 $O(M)$입니다. 따라서 전체 시간 복잡도는 $O(M \log M)$입니다. 만약 동전이 이미 정렬되어 있다면 $O(M)$이 됩니다.
  • 공간 복잡도: 동전 리스트를 저장하는 공간 외에 추가적인 공간을 거의 사용하지 않으므로, $O(1)$ (혹은 $O(M)$ if sorting creates a copy) 입니다.

3. 코딩 인터뷰를 위한 그리디 알고리즘 팁 및 함정

그리디 알고리즘은 직관적이지만, 앞서 언급했듯이 항상 최적해를 보장하지는 않습니다. 코딩 인터뷰에서 그리디 알고리즘 문제를 만났을 때 다음 사항들을 유의해야 합니다.

팁 1: 그리디 선택의 유효성 검증

문제를 그리디하게 풀 수 있을 것 같다는 생각이 들면, “이 그리디 선택이 정말 전체의 최적해로 이어지는가?”를 스스로에게 질문해야 합니다. 몇 가지 작은 테스트 케이스를 직접 손으로 풀어보면서 그리디 선택이 실패하는 경우가 있는지 확인해 보세요. 만약 그리디 선택이 항상 최적해를 보장하지 않는다면, 동적 계획법이나 다른 알고리즘을 고려해야 할 수 있습니다.

팁 2: 정렬의 중요성

많은 그리디 문제에서 정렬(Sorting)은 핵심적인 역할을 합니다. 위 거스름돈 문제처럼 가장 큰/작은 요소를 먼저 처리하거나, 특정 기준에 따라 데이터를 정렬함으로써 그리디 선택의 효율성을 극대화할 수 있습니다. 어떤 기준으로 정렬해야 최적의 선택을 할 수 있는지 고민해 보세요.

팁 3: 반례 찾기 연습

그리디 알고리즘은 반례(Counterexample)를 찾는 것이 중요합니다. 만약 그리디 접근 방식이 최적해를 찾지 못하는 경우가 있다면, 그 반례를 통해 문제를 다른 관점에서 바라보거나, 그리디 조건이 성립하지 않음을 증명할 수 있습니다.

팁 4: 동적 계획법과의 경계

그리디 알고리즘과 동적 계획법은 모두 최적 부분 구조를 가지는 문제를 해결하는 데 사용될 수 있어 혼동하기 쉽습니다. 핵심 차이는 다음과 같습니다:

  • 그리디: 각 단계에서 지역적으로 최적의 선택을 하고, 이 선택이 이후의 문제를 해결하는 데 영향을 주지 않습니다.
  • 동적 계획법: 부분 문제들의 최적해를 저장해두고, 이를 바탕으로 더 큰 문제의 최적해를 구성합니다. 이전 단계의 선택이 다음 단계에 영향을 미칠 수 있으며, 모든 가능한 경우의 수를 고려해야 할 때 사용됩니다.

만약 그리디 선택이 “지금 당장은 최적이지만, 미래의 선택에 부정적인 영향을 주어 최종적으로는 최적해가 아닌” 상황이 발생한다면 동적 계획법을 고려해야 할 가능성이 높습니다. 예를 들어, 배낭 문제(Knapsack Problem)의 경우, 단순히 무게당 가치가 높은 물건부터 넣는 그리디 방식은 항상 최적해를 보장하지 않습니다.

마치며

그리디 알고리즘은 코딩 인터뷰에서 빠지지 않고 등장하는 중요한 개념입니다. 직관적이고 구현이 비교적 쉽다는 장점 덕분에 많은 문제에 적용될 수 있지만, 항상 최적해를 보장하는 것은 아니므로 신중하게 접근해야 합니다.

그리디 알고리즘 문제를 풀 때는 다음과 같은 질문들을 스스로에게 던져보세요:

  • 이 문제에 그리디 접근이 유효한가? (탐욕적 선택 속성, 최적 부분 구조 만족 여부)
  • 어떤 기준으로 “최적의 선택”을 할 것인가? (정렬 기준 등)
  • 그리디 선택이 실패하는 반례는 없을까?
Software Engineering, Algorithms
Greedy Algorithms
This post is licensed under CC BY 4.0 by the author.