그리디 알고리즘(Greedy Algorithm)
그리디 알고리즘(Greedy Algorithm)은 최적화 문제를 해결하기 위한 방법 중 하나입니다. 이 알고리즘의 기본 원칙은 각 단계에서 지역적으로 최적인 선택을 함으로써 전체적으로 최적의 결과를 얻는 것입니다. 즉, 각 단계에서 가장 좋아 보이는 선택을 하고, 이러한 선택들이 최종적으로 전체적인 최적해를 제공한다는 가정 하에 작동합니다.
그리디 알고리즘의 주요 특징은 다음과 같습니다:
-
단순성과 효율성: 그리디 알고리즘은 간단하고 이해하기 쉬우며, 종종 빠른 솔루션을 제공합니다.
-
지역 최적 선택: 각 단계에서 최적의 선택을 하여, 전역 최적해에 도달하려고 합니다.
-
탐욕적 속성: 알고리즘은 각 단계에서의 최적해가 전체 문제의 최적해로 이어진다는 ‘탐욕적 속성’을 가지고 있어야 합니다.
-
한 번의 선택: 일단 선택이 이루어지면, 이 선택은 취소되거나 재고되지 않습니다.
그리디 알고리즘의 예로는 거스름돈 문제, 최소 신장 트리(Kruskal, Prim 알고리즘), 최단 경로(다익스트라 알고리즘) 등이 있습니다. 이 알고리즘은 항상 최적의 해를 보장하지는 않지만, 특정 조건에서는 최적 또는 근사 최적해를 빠르게 찾을 수 있습니다.
이 문제에서 그리디 알고리즘을 사용하는 방법은 각 단계에서 건전지 사용량을 최소화하는 선택, 즉 가능한 한 순간이동을 최대한 많이 사용하는 것입니다. 이 방식은 주어진 문제의 조건과 탐욕적 속성에 따라 최적의 해를 제공합니다.
그리디 알고리즘을 사용하는 방법을 이해하기 위해, 구체적인 예를 들어 설명하겠습니다. 가장 대표적인 예시 중 하나는 ‘거스름돈 문제’입니다.
거스름돈 문제
상점에서 물건을 샀을 때, 최소 개수의 동전으로 거스름돈을 주는 방법을 생각해 봅시다. 예를 들어, 거스름돈이 380원이고, 사용할 수 있는 동전이 100원, 50원, 10원이 있다고 가정해 보겠습니다.
- 최대한 큰 단위의 동전을 사용하기 (탐욕적 선택)
- 먼저, 거스름돈 중 가장 큰 단위인 100원 동전을 최대한 사용합니다. 380원 중 300원을 100원 동전 3개로 줍니다.
- 이제 남은 거스름돈은 80원입니다.
- 남은 금액에 대해 반복
- 다음으로 큰 단위인 50원 동전을 사용합니다. 80원 중 50원을 50원 동전 1개로 줍니다.
- 남은 거스름돈은 30원입니다.
- 모든 거스름돈을 줄 때까지 반복
- 마지막으로 10원 동전을 사용합니다. 30원을 10원 동전 3개로 줍니다.
결과적으로, 100원 동전 3개, 50원 동전 1개, 10원 동전 3개를 사용하여 총 7개의 동전으로 거스름돈을 줄 수 있습니다. 이것이 그리디 알고리즘의 핵심 원리입니다: 각 단계에서 가장 큰 값(혹은 가장 작은 값)을 선택하여 문제를 해결합니다.
문제 설명 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.
예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다. 아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.
처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다. 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다. 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다. 위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.
이 문제에 적용하기
본 문제에 그리디 알고리즘을 적용하는 방법은
본 문제에서 그리디 알고리즘을 적용하는 방법은 다음과 같습니다:
문제의 목표는 주어진 거리 ( N )에 도달하기 위해 사용하는 건전지의 양을 최소화하는 것입니다. 여기서 그리디 선택은 가능한 한 순간이동을 사용하는 것입니다. 왜냐하면 순간이동은 건전지를 소모하지 않기 때문입니다. 반면, 점프는 건전지를 소모합니다.
그리디 알고리즘을 적용하기 위한 단계는 다음과 같습니다:
-
순간이동 선택: 현재 위치에서 순간이동을 사용하면 거리가 두 배가 됩니다. 이것은 건전지 소모 없이 가능한 최대 이동 거리를 제공합니다. 따라서, 목표 거리 ( N )에 도달할 때까지 순간이동을 최대한 많이 사용합니다.
-
점프 선택: 순간이동만으로 목표에 도달할 수 없는 경우 (즉, 현재 거리가 목표 거리보다 작은 경우), 점프를 사용합니다. 점프는 건전지를 소모하지만 필요한 경우에만 사용합니다.
-
반복 및 결정: 위의 두 선택을 반복하면서 목표 거리에 도달할 때까지 최소한의 건전지 사용량으로 이동합니다.
예를 들어, 거리가 5인 경우:
- 0에서 시작하여 1만큼 점프 (건전지 1 사용)
- 현재 거리 1에서 순간이동하여 거리 2가 됨 (건전지 사용 없음)
- 다시 1만큼 점프하여 거리 3이 됨 (건전지 1 사용)
- 거리 3에서 순간이동하여 최
종 목표인 거리 5에 도달합니다.
이러한 방식으로 건전지 사용량을 최소화할 수 있습니다. 각 단계에서 가장 효율적인 선택(순간이동 또는 점프)을 하여 전체적으로 건전지 사용량을 줄이는 것이 핵심입니다.
이 문제에서 그리디 알고리즘의 중요한 점은 ‘순간이동은 건전지를 사용하지 않는다’는 사실입니다. 따라서, 순간이동을 최대한 활용하여 점프(건전지를 사용하는 행동)의 횟수를 최소화하는 것이 최적의 해결책입니다. 이처럼 각 단계에서의 최적 선택이 전체 문제의 최적해로 이어지는 것이 그리디 알고리즘의 핵심 원리입니다.
2진수의 1이 최소한으로 있을 때 최소한의 점프로 간주되는 이유를 이해하려면, 먼저 문제의 규칙과 2진수 표현 방식을 이해해야 합니다.
문제에서는 두 가지 이동 방식이 있습니다:
- 점프: 한 칸을 앞으로 이동하며, 이때 건전지 1만큼 사용합니다.
- 순간이동: 현재 거리의 두 배로 이동하며, 건전지 사용량이 없습니다.
이제 이를 2진수로 어떻게 표현할 수 있는지 살펴보겠습니다:
- 순간이동: 현재 거리를 2배로 늘리는 것은 2진수에서 1비트를 왼쪽으로 이동하는 것과 같습니다. 예를 들어, 2진수
001(10진수로 1)에서 한 번의 순간이동은010(10진수로 2)가 됩니다. 이는 건전지를 사용하지 않습니다. - 점프: 한 칸을 점프하는 것은 2진수의 가장 낮은 자리에 1을 더하는 것과 같습니다. 예를 들어, 2진수
010에서 한 칸 점프하면011(10진수로 3)이 됩니다. 이는 건전지 1만큼을 사용합니다.
목표는 주어진 거리 ( N )에 도달하기 위해 최소한의 건전지를 사용하는 것입니다. 이를 2진수로 표현했을 때, 1의 개수는 점프 횟수와 같고, 0의 개수는 순간이동 횟수와 같습니다. 순간이동은 건전지를 사용하지 않기 때문에, 건전지 사용량을 최소화하기 위해서는 가능한 많은 순간이동과 가능한 적은 점프가 필요합니다.
따라서, ( N )의 2진수 표현에서 1의 개수가 최소일 때, 건전지 사용량도 최소가 됩니다. 예를 들어, 10진수 5는 2진수로 101이며, 여기에는 두 개의 1이 있습니다. 이는 건전지를 두 번 사용해야 함을 의미합니다 (점프 두 번). 이
것이 이 문제에서 거리 ( N )에 도달하기 위해 필요한 최소한의 건전지 사용량을 결정하는 방식입니다. 2진수 표현에서 1의 개수가 점프 횟수를 나타내기 때문에, 이를 최소화하는 것이 전체 건전지 사용량을 최소화하는 핵심입니다.
이러한 방식으로 문제를 해결하는 것은 문제의 규칙과 2진수의 특성을 결합하여, 각 위치에서의 최적의 선택(순간이동 또는 점프)을 통해 전체 최적해를 도출하는 그리디 알고리즘의 좋은 예시입니다.
Share on: