왜 Greedy가 직관에 맞지 않을 수 있는가 (그리고 내가 이를 이해하는 방법)

Source: Dev.to

위의 링크에 포함된 텍스트를 번역하려면 해당 내용을 제공해 주세요. 텍스트를 주시면 한국어로 번역해 드리겠습니다.

동기

누군가 디스코드에서 점프 게임과 최대 물 담는 용기와 같이 직관적이지 않은 문제에서 탐욕 알고리즘을 어떻게 식별할 수 있는지 물었습니다. 그들은 특히 이 두 문제에 대해 탐욕이 직관에 맞지 않는다고 느꼈다고 했습니다.

솔직히 말해서, 제가 처음 이 문제들을 시도했을 때 스스로 완전히 풀 수 없었습니다. 미리 탐욕 문제라는 것을 알고 의도적으로 탐욕 문제를 연습할 때도 같은 의구심이 들었습니다. 탐욕이 저에게도 자연스럽게 다가오지 않았거든요. 그래서 디스코드에서 누군가 이 질문을 올린 것을 보고, 좀 더 깊이 생각해 보고 무엇을 발견할 수 있을지 고민해 보기로 했습니다.

저는 주로 이 두 문제에 집중했습니다. 각각에 대해 먼저 제 직감을 따라가며 도출된 해법을 찾아보았습니다. 그런 다음 그 직감을 되짚어 보고, 탐욕 해법과 대비시키면서 왜 한 접근법은 더 자연스럽게 느껴지고 다른 접근법은 그렇지 않은지 이해하려고 노력했습니다.

가장 큰 물을 담는 컨테이너

각 인덱스가 수직선을 나타내는 높이 배열이 주어집니다. 목표는 두 개의 선을 선택해 그들이 형성하는 컨테이너가 최대량의 물을 담도록 하는 것입니다.

이 문제에서 내 직관은 놀랍게도 바로 의도된 탐욕적 해결책으로 이끌었습니다. 한 가지 이유는 처음에 생각했던 완전 탐색 방식을 최적화할 의미 있는 방법을 찾지 못했기 때문일 수도 있습니다. 완전 탐색에 집착하고 이를 개선하려 하기보다는 문제에 다른 방식으로 접근하기 시작했습니다.

먼저 목표를 명확히 정의했습니다: 면적을 최대화하는 것. 이상적으로는 최대 너비와 최대 높이를 동시에 갖는 것이지만, 현실적으로는 항상 가능하지 않습니다. 그래서 두 요소 사이의 최적의 절충점을 찾는 문제로 재구성했습니다. 가장 큰 가능한 너비에서 시작한 뒤, 필요하다면 너비를 약간 포기하더라도 높이를 높여 면적을 늘릴 수 있는지를 시도했습니다.

이를 적으면서 깨달은 점은 탐욕적 접근법도 완전 탐색의 최적화 형태로 볼 수 있다는 것입니다. 완전 탐색에서는 모든 가능한 컨테이너를 고려하고 그 면적을 비교합니다. 탐욕적 해결책에서는 모든 컨테이너를 만들지는 않습니다. 대신 현재의 탐욕적 선택이 이미 그들을 압도한다는 것을 알기 때문에 절대 최적이 될 수 없는 컨테이너들을 의도적으로 버립니다. 이것이 이 접근법을 효율적이면서도 안전하게 만드는 이유입니다.

Jump Game

각 값이 해당 인덱스에서 앞으로 점프할 수 있는 최대 단계 수를 알려주는 배열이 주어집니다. 인덱스 0에서 시작하여, 마지막 인덱스에 도달할 수 있는지 여부만을 묻는 문제입니다.

Jump Game에서는 처음에 그리디가 명백한 선택처럼 보이지 않았습니다. 이는 제가 문제를 “목표에 어떻게 도달할 것인가?” 라는 관점으로만 바라봤기 때문이라고 생각합니다—이렇게 하면 자연스럽게 DP‑스타일의 풀이가 떠오릅니다. 하지만 나중에 더 효율적인 그리디 풀이를 보았을 때, 문제를 다르게 프레이밍하면 직관적이지 않던 느낌이 크게 사라진다는 것을 깨달았습니다.

문제를 거리 문제로 바라보면—인덱스 0이 끝으로부터 가장 먼 지점이라고 생각하면—목표는 시작점에서 가능한 한 멀리까지 도달하고, 그 도달 범위가 결국 마지막 인덱스를 포함하는지를 확인하는 것이 됩니다. 이런 관점에서는 그리디 풀이가 목표를 직접 겨냥하기보다 단계별로 도달 가능 범위를 확장해 나가는 과정이라고 볼 수 있습니다.

Conclusion

탐욕 알고리즘이 나에게 두려워 보이는 이유 중 하나는 그 올바름을 스스로 증명하는 데 어려움을 겪기 때문인 것 같다. 마치 눈을 가리고 한 방을 쏘아 성공을 바라보는 느낌이며, 제대로 된 논리를 전개하는 “실제 작업”을 하지 않는 것처럼 느껴진다. 이는 아직 탐욕 알고리즘을 비공식적인 정의 이상으로 이해하지 못했기 때문일 것이다.

내가 얻은 교훈은, 탐욕적인 선택이 왜 안전한지에 대한 추론 능력을 향상시키면 이러한 해결책이 더 자연스럽게 느껴질 것이라는 점이다. 더불어 문제를 다양한 방식으로 재구성하고 직관에 기반한 해결책이 실제로 어떻게 작동하는지 되돌아보는 것이 시간이 지남에 따라 탐욕 직관을 키우는 좋은 방법인 것 같다.