그리디 알고리즘 이해하기 - 매 순간 최적의 선택으로 문제 해결하기

들어가며

이번 시간에는 알고리즘 중 하나인 '그리디 알고리즘'에 대해 알아보려고 합니다.

 

---

소개

그리디(Greedy) 알고리즘, 또는 탐욕법 알고리즘은 매 순간에서 가장 최적의 선택을 통해 문제를 해결하는 방식입니다. 그리디라는 단어는 '탐욕적인'이라는 의미를 가지고 있죠. 이 알고리즘의 핵심은 각 단계에서 '현재 가장 좋은 선택'을 하는 것입니다.

주요 특징

그리디 알고리즘이 가지는 주요 특징은 다음과 같습니다.

1. 탐욕적 선택 속성
   알고리즘이 진행되는 동안, 각 단계에서 최적의 선택을 합니다. 이 선택은 이후의 선택 전략에 영향을 주지 않습니다.
2. 최적 부분 구조
   문제 전체에 대한 최적해(global optimum)가 부분 문제에 대해서도 최적해(local optimum)를 포함하고 있습니다.

접근 방법

그리디 알고리즘을 접근하는 방법은 다음과 같습니다.

1. 문제 이해
   문제를 완전히 이해하고, 어떤 것이 최적의 선택인지 결정하는 기준을 정확히 파악해야 합니다.
2. 선택 절차 설계
   각 단계에서 어떤 선택을 해야 하는지 결정하는 절차를 설계합니다.
3. 증명
   선택 절차가 항상 최적의 해를 도출할 수 있음을 증명합니다.
4. 구현
   이를 바탕으로 알고리즘을 구현합니다.

그러나 그리디 알고리즘은 항상 최적의 해를 찾아주는 것은 아닙니다. 문제의 특성과 요구 사항에 따라 다른 알고리즘(예: 다이나믹 프로그래밍)을 사용해야 할 수도 있습니다.

최적의 선택 결정하기

최적의 선택을 결정하는 것은 문제의 특성과 주어진 조건에 따라 달라집니다. 여기서 중요한 것은 각 선택이 최종 결과에 어떤 영향을 미치는지를 이해하는 것입니다.

 

일반적으로 그리디 알고리즘에서 최적의 선택은 다음과 같은 기준에 따라 결정될 수 있습니다.

1. 최대 또는 최소화
   많은 그리디 알고리즘 문제에서는 특정 값을 최대화하거나 최소화하는 것이 목표입니다. 예를 들어, 최소 비용으로 모든 도시를 방문하는 최적의 경로를 찾는 문제에서는, 각 단계에서 가장 비용이 적은 경로를 선택하는 것이 최적의 선택일 수 있습니다.
2. 자원 제약
   자원이 제한되어 있는 경우, 그 자원을 가장 효율적으로 사용하는 선택을 하는 것이 최적의 선택일 수 있습니다. 예를 들어, 주어진 무게 제한 내에서 가장 가치가 높은 물건들을 배낭에 넣는 배낭 문제에서는, 가치 대비 무게가 가장 높은 물건을 선택하는 것이 최적의 선택일 수 있습니다.
3. 순서 또는 우선순위
   일정한 순서가 있거나 우선순위가 있는 경우, 그 순서나 우선순위에 따라 선택을 하는 것이 최적의 선택일 수 있습니다. 예를 들어, 주어진 마감 기한을 모두 지키면서 가장 많은 작업을 완료하는 스케줄링 문제에서는, 마감 기한이 가장 빠른 작업부터 선택하는 것이 최적의 선택일 수 있습니다.

따라서, 그리디 알고리즘을 적용할 때는 문제의 특성을 잘 파악하고, 각 선택이 최종 결과에 어떤 영향을 미치는지를 이해하는 것이 중요합니다.

그리디 알고리즘 문제 판별 팁

그리디 알고리즘 문제를 판별하는 것은 항상 명확하지 않을 수 있습니다. 그러나 일부 문제 유형은 그리디 알고리즘에 특히 적합합니다.

 

다음은 그리디 알고리즘 문제를 판별하는 데 도움이 될 수 있는 몇 가지 팁입니다.

1. 탐욕적 선택 속성이 있는가?
   문제의 해결법이 현재의 최적해를 선택하고 이 선택이 이후의 선택 전략에 영향을 미치지 않는다면 그리디 알고리즘을 사용할 수 있습니다.
2. 최적 부분 구조가 있는가?
   큰 문제를 작은 문제들로 나눌 수 있고, 그 작은 문제들의 최고의 해결방안을 모아서 큰 문제의 최고의 해결방안을 만들 수 있다면, 그리디 알고리즘을 사용할 수 있습니다.
3. 단계적 결정이 가능한가?
   문제의 해결이 여러 단계의 결정으로 구성되고 각 단계에서의 최적의 결정이 전체 문제의 최적 해결책으로 이어진다면, 즉 이전 단계의 선택이 다음 단계의 선택에 영향을 미친다면 그리디 알고리즘을 사용할 수 있습니다.
4. 정렬이나 우선순위 큐가 관련된 문제인가?
   정렬이나 우선순위 큐가 문제 해결에 중요한 역할을 하는 경우, 그리디 알고리즘을 사용할 수 있습니다. 예를 들어, 최소 비용이나 최대 이익을 찾는 문제, 각 작업에 대해 특정 조건을 만족시키는 스케줄링 문제 등이 있습니다.

이러한 팁들을 통해 그리디 알고리즘이 적합한 문제인지 여부를 판단할 수 있습니다. 그러나 실제로는 문제를 완전히 이해하고, 그리디 알고리즘을 적용했을 때 항상 최적의 해를 구할 수 있는지 확인하는 과정이 필요합니다.

선택이란 무엇인가

탐욕적 선택 속성과 단계적 결정 가능성에서 언급된 '선택'은 비슷한 개념을 가리키지만, 그 역할과 의미는 각각 다릅니다.

• 탐욕적 선택 속성
  이 개념에서 말하는 '선택'은 현재 상황에서 가장 최적인 선택을 의미합니다. 이러한 선택은 매 순간마다 반복되며, 이후의 선택 전략에 영향을 주지 않습니다.
• 단계적 결정 가능성
  이 개념에서 말하는 '선택'은 문제 해결 과정에서 이루어지는 연속적인 결정을 의미합니다. 각 단계는 서로 연결되어 있어 이전 단계에서 이루어진 선택이 다음 단계에서의 선택 범위나 방향을 결정합니다.

이 두 개념을 잘 이해하고 구분하면 그리디 알고리즘을 이해하는 데 큰 도움이 됩니다.

예시 문제

BOJ 12904 문제 'A와 B'를 살펴보며 그리디 알고리즘을 어떻게 적용하는지 알아보겠습니다.

12904번: A와 B

1. 문제 이해
   문자열 S를 입력받고, 문자 'A'를 추가하거나 문자열을 뒤집고 'B'를 추가하는 두 가지 방법을 이용해서 문자열 T를 만들 수 있는지 판단하는 문제입니다.
2. 선택 절차 설계
   문자열 T의 마지막 문자에 따라 다른 변환을 선택합니다. 마지막 문자가 'A'라면 이 문자를 제거하고, 'B'라면 문자열을 뒤집은 후 마지막 문자를 제거합니다. 이 과정을 S와 T의 길이가 같아질 때까지 반복합니다.
3. 증명
   이 문제의 경우 선택 절차가 항상 최적의 해를 도출할 수 있다는 것을 증명하는 것은 쉽습니다. 왜냐하면 T를 만드는 방법이 'A'를 추가하거나 문자열을 뒤집고 'B'를 추가하는 두 가지 방법밖에 없기 때문입니다. 따라서 이 두 가지 방법을 역으로 적용하여 S를 만들 수 있는지 확인하면 됩니다.
4. 구현
   설계한 선택 절차를 코드로 구현합니다. T의 마지막 문자를 확인하고, 해당 문자에 따라 다른 변환을 적용하며 S와 T의 길이가 같아질 때까지 반복합니다. 마지막으로, S와 T가 동일한지 확인하여 문제의 답을 도출합니다.

이 문제를 분석하면서 그리디 알고리즘의 원리를 확인할 수 있었습니다.

1. 탐욕적 선택 속성
   문자열 T의 마지막 문자가 'A'인지 'B'인지에 따라 적절한 변환을 선택하는 것입니다. 이 선택은 현재 상황에서만 최적의 해를 찾는 것이며, 이후의 선택 전략에는 영향을 미치지 않습니다.
2. 최적 부분 구조
   이 문제는 전체 문자열 S를 T로 만드는 문제를, 각 단계에서 하나의 문자를 변환하는 여러 개의 부분 문제로 나눌 수 있으며, 각 부분 문제의 최적해가 전체 문제의 최적해를 구성합니다.
3. 단계적 결정
   각 단계에서 이루어지는 변환이 다음 단계의 선택에 영향을 미칩니다. 즉, T의 마지막 문자가 'A'인지 'B'인지에 따라 다음 단계에서 취할 행동이 달라지게 됩니다.

 

문자열 변환 문제는 크게 세 가지 단계로 구성되어 있습니다. 각 변환 단계를 하나의 부분 문제로 보면 다음과 같습니다.

1. 문자열 분석 단계
   주어진 문자열 T의 마지막 문자가 'A'인지 'B'인지를 확인합니다.
2. 변환 단계
   'A' 또는 'B'에 따라 알맞은 변환을 수행합니다. 'A'라면, 문자열 T의 마지막 문자를 제거하고, 'B'라면 문자열 T를 뒤집은 후 마지막 문자를 제거합니다.
3. 비교 단계
   이 변환 과정을 문자열 S와 T의 길이가 동일해질 때까지 반복하며, 마지막에는 S와 T가 동일한지 확인합니다.

이 세 가지 단계를 반복적으로 수행하면서, 문자열 S가 주어진 변환을 통해 문자열 T로 만들어질 수 있는지를 판단합니다. 이는 그리디 알고리즘의 원리를 따르는 문제로, 각 단계에서 최적의 선택을 하여 전체 문제의 해결을 시도합니다.

 

이제 예시 코드를 한번 보시죠.

 

function solution() {
  const S = input();
  let T = input().split("");

  while (S.length !== T.length) {
    if (T.at(-1) === "A") T = T.slice(0, -1);
    else if (T.at(-1) === "B") T = T.slice(0, -1).reverse();
    else break;
  }

  return S === T.join("") ? 1 : 0;
}

 

코드 구현은 생각보다 간단합니다. 하지만 아이디어를 떠올리는 데는 좀 더 힘이 드는 것 같습니다.

 

---

마치며

그리디 알고리즘은 매 순간 최적의 선택을 통해 문제를 해결하는 방식의 알고리즘입니다.

문제의 특성을 잘 파악하고, 각 선택이 최종 결과에 어떤 영향을 미치는지를 이해하는 것이 중요합니다.

이해를 하시는데 조금이나마 도움이 되셨으면 좋겠습니다.

 

잘못된 내용이 있다면 지적 부탁드립니다.

감사합니다 :D