들어가며
이번 시간에는 알고리즘 중 하나인 '그리디 알고리즘'에 대해 알아보려고 합니다.
소개
그리디(Greedy) 알고리즘, 또는 탐욕법 알고리즘은 매 순간에서 가장 최적의 선택을 통해 문제를 해결하는 방식입니다. 그리디라는 단어는 '탐욕적인'이라는 의미를 가지고 있죠. 이 알고리즘의 핵심은 각 단계에서 '현재 가장 좋은 선택'을 하는 것입니다.
주요 특징
그리디 알고리즘이 가지는 주요 특징은 다음과 같습니다.
- 탐욕적 선택 속성
알고리즘이 진행되는 동안, 각 단계에서 최적의 선택을 합니다. 이 선택은 이후의 선택 전략에 영향을 주지 않습니다. - 최적 부분 구조
문제 전체에 대한 최적해(global optimum)가 부분 문제에 대해서도 최적해(local optimum)를 포함하고 있습니다.
접근 방법
그리디 알고리즘을 접근하는 방법은 다음과 같습니다.
- 문제 이해
문제를 완전히 이해하고, 어떤 것이 최적의 선택인지 결정하는 기준을 정확히 파악해야 합니다. - 선택 절차 설계
각 단계에서 어떤 선택을 해야 하는지 결정하는 절차를 설계합니다. - 증명
선택 절차가 항상 최적의 해를 도출할 수 있음을 증명합니다. - 구현
이를 바탕으로 알고리즘을 구현합니다.
그러나 그리디 알고리즘은 항상 최적의 해를 찾아주는 것은 아닙니다. 문제의 특성과 요구 사항에 따라 다른 알고리즘(예: 다이나믹 프로그래밍)을 사용해야 할 수도 있습니다.
최적의 선택 결정하기
최적의 선택을 결정하는 것은 문제의 특성과 주어진 조건에 따라 달라집니다. 여기서 중요한 것은 각 선택이 최종 결과에 어떤 영향을 미치는지를 이해하는 것입니다.
일반적으로 그리디 알고리즘에서 최적의 선택은 다음과 같은 기준에 따라 결정될 수 있습니다.
- 최대 또는 최소화
많은 그리디 알고리즘 문제에서는 특정 값을 최대화하거나 최소화하는 것이 목표입니다. 예를 들어, 최소 비용으로 모든 도시를 방문하는 최적의 경로를 찾는 문제에서는, 각 단계에서 가장 비용이 적은 경로를 선택하는 것이 최적의 선택일 수 있습니다. - 자원 제약
자원이 제한되어 있는 경우, 그 자원을 가장 효율적으로 사용하는 선택을 하는 것이 최적의 선택일 수 있습니다. 예를 들어, 주어진 무게 제한 내에서 가장 가치가 높은 물건들을 배낭에 넣는 배낭 문제에서는, 가치 대비 무게가 가장 높은 물건을 선택하는 것이 최적의 선택일 수 있습니다. - 순서 또는 우선순위
일정한 순서가 있거나 우선순위가 있는 경우, 그 순서나 우선순위에 따라 선택을 하는 것이 최적의 선택일 수 있습니다. 예를 들어, 주어진 마감 기한을 모두 지키면서 가장 많은 작업을 완료하는 스케줄링 문제에서는, 마감 기한이 가장 빠른 작업부터 선택하는 것이 최적의 선택일 수 있습니다.
따라서, 그리디 알고리즘을 적용할 때는 문제의 특성을 잘 파악하고, 각 선택이 최종 결과에 어떤 영향을 미치는지를 이해하는 것이 중요합니다.
그리디 알고리즘 문제 판별 팁
그리디 알고리즘 문제를 판별하는 것은 항상 명확하지 않을 수 있습니다. 그러나 일부 문제 유형은 그리디 알고리즘에 특히 적합합니다.
다음은 그리디 알고리즘 문제를 판별하는 데 도움이 될 수 있는 몇 가지 팁입니다.
- 탐욕적 선택 속성이 있는가?
문제의 해결법이 현재의 최적해를 선택하고 이 선택이 이후의 선택 전략에 영향을 미치지 않는다면 그리디 알고리즘을 사용할 수 있습니다. - 최적 부분 구조가 있는가?
큰 문제를 작은 문제들로 나눌 수 있고, 그 작은 문제들의 최고의 해결방안을 모아서 큰 문제의 최고의 해결방안을 만들 수 있다면, 그리디 알고리즘을 사용할 수 있습니다. - 단계적 결정이 가능한가?
문제의 해결이 여러 단계의 결정으로 구성되고 각 단계에서의 최적의 결정이 전체 문제의 최적 해결책으로 이어진다면, 즉 이전 단계의 선택이 다음 단계의 선택에 영향을 미친다면 그리디 알고리즘을 사용할 수 있습니다. - 정렬이나 우선순위 큐가 관련된 문제인가?
정렬이나 우선순위 큐가 문제 해결에 중요한 역할을 하는 경우, 그리디 알고리즘을 사용할 수 있습니다. 예를 들어, 최소 비용이나 최대 이익을 찾는 문제, 각 작업에 대해 특정 조건을 만족시키는 스케줄링 문제 등이 있습니다.
이러한 팁들을 통해 그리디 알고리즘이 적합한 문제인지 여부를 판단할 수 있습니다. 그러나 실제로는 문제를 완전히 이해하고, 그리디 알고리즘을 적용했을 때 항상 최적의 해를 구할 수 있는지 확인하는 과정이 필요합니다.
선택이란 무엇인가
탐욕적 선택 속성과 단계적 결정 가능성에서 언급된 '선택'은 비슷한 개념을 가리키지만, 그 역할과 의미는 각각 다릅니다.
- 탐욕적 선택 속성
이 개념에서 말하는 '선택'은 현재 상황에서 가장 최적인 선택을 의미합니다. 이러한 선택은 매 순간마다 반복되며, 이후의 선택 전략에 영향을 주지 않습니다. - 단계적 결정 가능성
이 개념에서 말하는 '선택'은 문제 해결 과정에서 이루어지는 연속적인 결정을 의미합니다. 각 단계는 서로 연결되어 있어 이전 단계에서 이루어진 선택이 다음 단계에서의 선택 범위나 방향을 결정합니다.
이 두 개념을 잘 이해하고 구분하면 그리디 알고리즘을 이해하는 데 큰 도움이 됩니다.
예시 문제
BOJ 12904 문제 'A와 B'를 살펴보며 그리디 알고리즘을 어떻게 적용하는지 알아보겠습니다.
12904번: A와 B
수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수
www.acmicpc.net
- 문제 이해
문자열 S를 입력받고, 문자 'A'를 추가하거나 문자열을 뒤집고 'B'를 추가하는 두 가지 방법을 이용해서 문자열 T를 만들 수 있는지 판단하는 문제입니다. - 선택 절차 설계
문자열 T의 마지막 문자에 따라 다른 변환을 선택합니다. 마지막 문자가 'A'라면 이 문자를 제거하고, 'B'라면 문자열을 뒤집은 후 마지막 문자를 제거합니다. 이 과정을 S와 T의 길이가 같아질 때까지 반복합니다. - 증명
이 문제의 경우 선택 절차가 항상 최적의 해를 도출할 수 있다는 것을 증명하는 것은 쉽습니다. 왜냐하면 T를 만드는 방법이 'A'를 추가하거나 문자열을 뒤집고 'B'를 추가하는 두 가지 방법밖에 없기 때문입니다. 따라서 이 두 가지 방법을 역으로 적용하여 S를 만들 수 있는지 확인하면 됩니다. - 구현
설계한 선택 절차를 코드로 구현합니다. T의 마지막 문자를 확인하고, 해당 문자에 따라 다른 변환을 적용하며 S와 T의 길이가 같아질 때까지 반복합니다. 마지막으로, S와 T가 동일한지 확인하여 문제의 답을 도출합니다.
이 문제를 분석하면서 그리디 알고리즘의 원리를 확인할 수 있었습니다.
- 탐욕적 선택 속성
문자열 T의 마지막 문자가 'A'인지 'B'인지에 따라 적절한 변환을 선택하는 것입니다. 이 선택은 현재 상황에서만 최적의 해를 찾는 것이며, 이후의 선택 전략에는 영향을 미치지 않습니다. - 최적 부분 구조
이 문제는 전체 문자열 S를 T로 만드는 문제를, 각 단계에서 하나의 문자를 변환하는 여러 개의 부분 문제로 나눌 수 있으며, 각 부분 문제의 최적해가 전체 문제의 최적해를 구성합니다. - 단계적 결정
각 단계에서 이루어지는 변환이 다음 단계의 선택에 영향을 미칩니다. 즉, T의 마지막 문자가 'A'인지 'B'인지에 따라 다음 단계에서 취할 행동이 달라지게 됩니다.
문자열 변환 문제는 크게 세 가지 단계로 구성되어 있습니다. 각 변환 단계를 하나의 부분 문제로 보면 다음과 같습니다.
- 문자열 분석 단계
주어진 문자열 T의 마지막 문자가 'A'인지 'B'인지를 확인합니다. - 변환 단계
'A' 또는 'B'에 따라 알맞은 변환을 수행합니다. 'A'라면, 문자열 T의 마지막 문자를 제거하고, 'B'라면 문자열 T를 뒤집은 후 마지막 문자를 제거합니다. - 비교 단계
이 변환 과정을 문자열 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