인프런 커뮤니티 질문&답변
작성한 질문수
안녕하세요 외부 문제 힌트
작성
·
42
·
수정됨
0
안녕하세요 강사님
강사님 강의를 듣고 다른 코테를 풀던 중
아직도 머릿속에서 잊혀지지 않는 문제가 있습니다.
이 문제는 O(n^2)으로 풀어서는 안되는데 제 생각엔 Dynamic Programming 문제인 거 같습니다.
일단 문제는 아래와 같은데 N 이 주어져 이 N은 1~200,000 이고 그
N에 해당하는 숫자의
다른 음의 정수, 0, 양의 정수가 주어집니다
예를 들어 데이터는 아래와 같습니다.
6
0 1 -1 2 -2 3
이렇게 주어졌을 때 내가 한 숫자를 0으로 만들 수 있습니다.
그리고 하나씩 차례대로 더했을 때 0이 가장 많이 나오는 경우의 수를 구하는 겁니다.
이 경우 제가 3을 0으로 만들면 첫 0 의 카운트 1개 그리고 두번째 1를 더해서 1이고 다시 -1를 더하면 0이 됩니다.
이제 카운트는 2개고 2를 더하면 2고 -2를 더하면 0입니다. 다시 카운트가 3입니다.
그리고 마지막 3을 0으로 만들면 카운트가 4가 됩니다.
그래서 답은 4입니다.
참고로 정렬은 불가합니다.
즉 숫자들이 나열되어 있을 때 그걸 하나씩 다 더해서 0이 최대로 나오는 경우를 세는 건데 이 때 그 수 중 딱 한번 0으로 만들 수 있다는 것입니다.
이문제가 DP 문제인 것 같은데 도저히 어떻게 풀어야 될지 감이 안잡힙니다..
물론 강의 문제는 아니지만 도움을 주실 수 있을까 해서 요청드립니다.
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
pds514514님께서 질문하신 문제는 주어진 수를 하나 0으로 바꾸어 연속적으로 더했을 때 0이 되는 횟수를 최대화하는 문제로 보입니다. 이 문제는 부분합을 이용한 최적화 문제로 생각해 볼 수 있습니다. 부분합을 계산하면서 어느 한 숫자를 0으로 바꾸었을 때 가장 많은 0을 얻을 수 있는 경우를 탐색하게 됩니다.
해당 문제에 대해 직접적인 도움을 드릴 수는 없지만, 제가 이해하기로는 부분합과 관련된 아이디어를 잘 활용하면 O(n) 시간복잡도로 해결 가능할 것 같습니다. 직접적인 해결책을 제공하진 않지만, 아래와 같은 방법들을 고려해 보시기 바랍니다.
해결 방법 제안
Prefix Sum(부분합) 활용: 각 숫자에 대해 부분합을 계산하고, 특정 숫자를 0으로 바꾸었을 때 어떤 위치에서 가장 많은 0을 만들 수 있을지 탐색할 수 있습니다.
HashMap을 활용한 최적화: 각 부분합이 나온 위치를 저장하는 자료구조를 활용하여, 특정 부분합이 연속적으로 0이 되는 상황을 추적하는 방식으로 접근할 수 있습니다.
Dynamic Programming: 이 문제를 DP 형태로 변형한다면, 부분합을 추적하며 어떤 숫자를 0으로 만들었을 때 연속합이 0이 되는 최대 횟수를 갱신해나가는 방법을 사용할 수 있습니다.
이 문제의 정확한 해법을 설명하기는 어렵지만, 이러한 고려 사항을 통해 아이디어를 발전시킬 수 있을 것입니다. 강의 외적인 내용도 도움을 드리기 위해 최대한의 노력을 하고 있습니다만, 직접적으로 문제에 대한 구현을 도와드리기는 어렵습니다.
참고 질문 링크: 36강. 알고리즘을 생각해내는 방법을 참고하시면 문제 해결의 접근 방식을 힌트로 얻으실 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.