인프런 커뮤니티 질문&답변

안녕하세요 카카누님 ㅎㅎ

이 문제의 핵심은 연속된 부분 배열의 곱 중 최댓값을 구하는 것입니다.

이렇게 한번 생각해볼까요?

현재 위치 i에서 끝나는 최대 곱은 무엇일까요?

dp[i] = max(A[i], dp[i-1] × A[i])

가 아닐까요? 지금까지 만들어놓은 최대값을 기반으로 지금 수를 곱하냐 안곱하냐? 두 가지 경우의 수로 결정이 됩니다.

이는 더하기의 개념으로부터 파생되는 식입니다.

우리는 최대값의 합이라는 것은 최대값을 다 더해서 만들어지는 것을 알고 있습니다. 사과농장에서 사과를 10개 재배한 날과 5개 재배한 날 중 하나의 날만 고르라면 10개를 재배한 날을 골라 그 재배한 사과를 기반으로 다시 더 많은 사과를 구하는 것과 비슷합니다.

더하기를 계속 더하면 곱셈이 되니 이와 같은 논리로 그런 가설을 세울 수 있습니다.

브루트포스로 풀수 있을거라 생각했지만 효율적으로 풀고 싶어서 다른 알고리즘을 생각해봤습니다.

이것저것 시도해보고 가설을 세워봤는데 식이 복잡해지고 잘되지 않습니다 ㅠㅠ

-> 브루트 포스 -> 시간복잡도를 줄여야겠다 -> dp, 투포인터, 그리디 순으로 생각하는게 중요합니다.

생각의 플로우는 정말 좋은 것 같습니다. 보통 코테에서 아 이문제를 그리디로 풀어야겠다. 하고 푸는 경우는 흔치않습니다. 보통 2번은 헤매요(3번 문제의 경우). 이정도면 잘하고 계신거 같습니다. ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 카카누님.

그리디 알고리즘 문제는 그 특성상 ‘현재 상황에서 가장 최적이라고 생각되는 해답’을 선택하는 방식으로 접근합니다. 때로는 최적의 해법이 보이지 않거나 문제의 진짜 속성이 잘 드러나지 않는 경우가 있어 어려움을 겪을 수 있습니다.

1. 그리디 문제 핵심 파악하기: 그리디 알고리즘이 적합한 경우는 ‘국소 최적 해법이 곧 전역 최적 해법’이 될 때 입니다. 이는 각 단계에서 최적 선택을 할 수 있는 조건 하에서 잘 작동합니다. 문제 자체가 이러한 성격을 가졌는지 확인하는 것이 중요합니다.

2. 가설 세우기: 출제자 의도를 파악하며 작은 부분 문제를 풀어나가는 가설을 세워보세요. 문제가 요구하는 여러 조건들을 살펴보면서 각각의 조건들이 어떻게 상호작용하는지를 생각하면서 접근하시면 도움이 됩니다.

3. 오답노트와 패턴 식별: 오답노트를 통해 과거에 실수했던 점이나 문제의 틀린 접근법을 기록하고, 같은 실수를 반복하지 않도록 패턴을 학습하는 것이 좋습니다. 패턴을 식별하고 관련된 문제들을 여러 번 풀어보는 것도 좋습니다.

4. 그리디 선정 연습: 직접 문제를 풀 때 최적의 답을 항상 찾을 수 있는지, 즉 그리디 알고리즘의 적용 법칙이 해당 문제에서도 유효한지를 검증하는 연습이 필요합니다.

비슷한 질문에 대한 강사님의 답변을 참고하시면 도움이 될 것입니다:
- 그리디에 대해서 질문있습니다: 그리디 알고리즘의 특성과 사용법을 이해하고 제대로 적용하는 방법에 대한 설명을 제공하고 있습니다.
- 6-F 그리디 질문입니다: 문제 해결 과정에서 그리디와 다른 알고리즘(이진탐색 등)을 어떻게 조합적으로 사용하는지에 대한 예시를 통해 접근방식을 배울 수 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.