hi의 초기 최대값 설정
문제에 대한 고민은 아니고 접근법에 대한 고민이 있습니다..
이진 탐색 문제를 풀 때 무지성으로
long long hi = 1e15로 최대한 크게 잡고 들어가는데 이 부분을 저격할 수 있는 문제가 있나요?
코딩테스트에서 위험한 생각인지 궁금해서 여쭤봅니다.
답변 2
0
안녕하세요 ㅎㅎ
먼저 해당 링크 확인부탁드립니다.
long long hi = 1e15
-> 여기에 대해 답변드리면요. ㅎㅎ
일단 long long의 최대값과 근접한 최대값으로 하셔야 합니다.
따라서 long long에서는 1e15보다는 1e18로 하시는게 좋습니다.
해당 부분은 교안 내의 다음 부분을 참고부탁드립니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. ri7116님.
이진 탐색 문제를 풀 때 hi (상한값)를 너무 크게 설정하면 여러 문제를 야기할 수 있습니다. 상한값을 설정할 때는 문제의 요구사항과 입력값의 범위를 고려하는 것이 중요합니다. 다음 설명과 유사한 질문들에서 설명하는 내용을 참고하세요.
이진 탐색에서 상한값 설정의 중요성:
시간 초과 가능성: 이진 탐색의 범위가 지나치게 크다면 불필요한 반복 연산이 발생합니다. 이는 실질적으로 시간 복잡도를 증가시켜 시간 초과로 인한 실패를 가져올 수 있습니다.
오버플로우 문제: 설정한 상한값이 자료형의 최대값에 근접하거나 이를 초과할 경우 오버플로우가 발생할 수 있습니다. 이러한 경우, 잘못된 결과가 도출될 수 있으며 특히
long long형으로도 커버할 수 없는 범위의 연산에 주의해야 합니다.
상한값 설정을 저격할 수 있는 문제:
여러 문제들이 이러한 불필요하게 큰 상한값 설정을 탐지하여 ‘틀렸습니다’로 처리할 수 있습니다. 특히, 가능한 최소/최대 값을 찾는 문제에서는 범위가 더 타이트하게 설정되어야 합니다.
유사한 맥락의 실습 질문들을 참고하세요:
- [이분탐색] 최댓값 설정은 어떤 기준으로 이진 탐색의 최댓값을 설정할지에 대해 논의합니다.
- 비슷한 이슈로 상한값 설정에 대해 더 자세히 다루는 다른 질문들도 꼭 확인해 보시기 바랍니다.
이와 관련하여, 문제에 따라 상한값을 적절하게 설정하는 것은 아주 중요한 부분입니다. 각 문제의 조건을 잘 살피고 가능한 범위를 기반으로 적절한 최대값을 설정해 주시길 권장드립니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
코딩살구클럽 문의
0
6
1
코딩살구클럽 승인
0
18
2
DP 경우의 수 설명이 이해가 되지 않습니다.
0
27
2
3-F 채점 관련 질문
0
23
1
BFS, DFS 활용이 되는 상황에서의 방향성
0
28
2
코딩살구클럽 승인
0
41
2
코딩살구클럽승인
0
33
3
코딩살구클럽 승인
0
48
2
3-D 관련 질문
0
35
2
코살구 회원가입 문의
0
43
2
코살구 로그인 문제
0
65
2
3-A 문제 풀이 관련 질문
0
53
3
2-O 질문 있습니다
0
38
2
2-T 문제에 관한 질문
0
40
2
코딩 살구 클럽 접속 및 사용방법 문의
0
61
2
안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~
0
64
2
코딩살구클럽 로그인문제
0
78
3
코딩 살구 클럽 로그인 문제
0
82
2
2-J 채점관련 질문
0
65
3
코딩 살구 클럽 Python 지원 가능 여부
0
77
1
살구클럽 아이디 없음 문제
0
76
1
1-O 코딩살구클럽 채점관련 질문
0
60
2
히든 테스트 케이스가 사라졌습니다
0
57
1
채점서버 혹시 다른 언어 지원도 가능하게 해주실 수 있나요
1
74
2