그리디 알고리즘 질문입니다

작성한 질문수 1

0

안녕하세요 ㅎㅎ

만약 해당 문제를 그리디로 푸는것이 확정이라면...

문제 범위를 기준으로 최대, 최소 범위 -> 내가 생각했던 정답후보가 2개가 나오면..? 이런식으로 확장해 나가셔서 생각하면 됩니다.

테스트 케이스에 계속 넣어보면서 안되면 반례가 있다고 생각하는게 편할까요?

-> 기존 TC 통과 후 -> 반례 체킹하시면 됩니다.

강의 중 반례 찾기 힘들었던 문제로 다시 질문주시면 해당 문제 기반으로 설명드리겠습니다.

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

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

감사합니다.

강사 큰돌 올림.

0

안녕하세요, 인프런 AI 인턴입니다. 민재 김님.

그리디 알고리즘 문제에서 반례를 찾는 것은 매우 중요하지만, 때로는 반례를 찾아내는 것이 쉽지 않기도 합니다. 그리디 알고리즘은 항상 최적해를 보장하지 않기 때문에 반례를 찾는 과정에서 몇 가지 접근 방법을 고려할 수 있습니다.

1. 극단값 사례 사용: 최소, 최대값 등의 극단값을 사용하여 알고리즘의 결과를 검증해보세요. 예를 들어, 입력값이 모두 같을 때, 매우 큰 값이나 작은 값으로 구성될 때 등의 경우를 테스트합니다.

2. 직관을 벗어난 시나리오 상상: 일반적이지 않은 작은 변경이나 조건을 넣어보세요. 흔히 그리디 알고리즘은 직관에 기초하므로, 직관을 일단 벗어난 사례를 고려할 수 있습니다.

3. 다른 알고리즘과 비교: 그리디 해결책과 정확한 해결책(예: 완전 탐색)을 비교하여 일관되지 않는 결과가 있는지 본다면, 반례를 찾는데 도움이 될 수 있습니다.

관련된 기존의 질문들에서도 비슷한 주제의 논의가 있었습니다:
- 보통 한문제당 얼마나 붙잡고있어야하나요?: 문제를 푸는 방법을 찾는 팁에 대한 유용한 조언이 포함되어 있습니다.
- 3-D 반례: 반례를 잘 생각해내는 방법에 대한 토론이 있습니다.

이러한 다양한 방법을 사용하여 그리디 알고리즘의 테스트 케이스를 검증해나가시면 도움이 될 것입니다.

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