시간 초과의 원인은 말씀하신 부분이 아니고, 29라인으로 보입니다.
우선 말씀하신 부분만 바꿔서 제출시에 정답이 안나오고,
s, e 의 값은 랜선의 길이 범위이기 때문에 231-1 를 가질 수 있을텐데 s+e 는 int 범위를 넘거갑니다.
따라서 long long 으로 하거나 unsigned 를 해야할 것 같습니다.
이진 검색에서 범위를 정하는 것은 m에서 성공하거나 실패했을 경우 다음에 m를 넣어서 검색할 것이냐 말것이냐인 것 같습니다.
지금 작성하신 코드의 방향은 m에서 성공하면 m보다 위를 검색하고, 거기서 실패하면 m를 하겠다는 방식인데.. (말이 좀 어렵습니다.)
범용적인 방식으로 하자면 아래와 같이 하는 것이 어떨까 합니다.
이 문제의 경우를 예를 들어서 보면..
1. 이 문제의 경우 조건을 만족하는 최대 값을 찾아야 하기 때문에,
m이 조건을 만족하면 m보다 큰 수에서 만족하는 부분이 있는지 찾아야 하는데, m이 정답이었다고 하면 m보다 큰 수에서는 조건을 만족하는 답이 없을 수 있습니다.
그래서 m은 포함한 범위에서 찾아야 합니다.
만족 못하면 작은 쪽에서 찾아야하는데, m은 이미 아니기 때문에 m은 포함될 필요가 없습니다.
즉, 항상 내가 찾는 쪽에는 정답이 있습니다.
func(s, e) m 계산 m이 조건을 만족하면, f(m, e) m이 조건을 만족하지 않으면, f(s, m - 1)
2. 그러면 m를 어떻게 계산할 것인가 인데, 무한 루프를 피해야 합니다.
무한루프는 [1,2] 범위를 찾았는데, [1,2] [ 2,2] 혹은 [1,1] [1,2] 로 나뉘게 되면 무한루프에 빠집니다.
1의 룰을 따르면 [1,1] [ 2,2] 로 나뉘기 떄문에 (m이 중복이 안되므로) 이런 문제는 피할 수 있을 것 같습니다.
문제에 따라서 m의 s에 붙는지 e에 붙는지가 중요하다면 (이런 경우가 있을지 저도 잘 기억이... ㅠㅠ)
1차이나는 경우를 홀짝 나워서 따져보면 됩니다. [0,1] [1,2] 정도
m = (s + e) / 2 혹은 m = (s + e + 1) / 2 를 쓰면 s에 붙거나 e에 붙게 됩니다.
3. 중단 조건은 항상 s == e로 하면 되는데... 방어코드를 작성하시다면 (처음 입력부터가 문제가 있다거나..)
s >= e 를 하면 될 것 같습니다.
func(s, e) if s >= e 이면, s가 정답 m = (s + e) / 2 // 문제 따라서 (s + e + 1) / 2 ?? m이 조건을 만족하면, f(m, e) m이 조건을 만족하지 않으면, f(s, m - 1) // 여기까지 오면 s < e는 보장이 되기 때문에 s <= m - 1 입니다.
kevinn 2년 전
안녕하세요!! 문제를 푸는 데 아래 코드에서 왜 시간초과가 나는 것인지 궁금해서 질문드립니다. 그리고 이분탐색 종류 문제들에 공통적으로 궁금한 것들도 있습니다.
아래 코드로 실행하다가 도저히 안되서 31~33번째 줄의 조건을 if(s > e) return e; 로 바꾸고, 44번째 줄의 함수의 m인자를 m-1로 바꾸어서 통과하였습니다. 아래 코드가 무한루프가 발생해서 시간초과가 나타나는 것 같은데, 왜 무한루프가 발생하는 것인지 잘 모르겠습니다.
그리고
1.이분탐색 문제에서 s와 e를 의 조건을 어떻게 해야 할지(예를 들어 s == e일 때 중단해야 할지, s > e일 때 중단해야 할지 같은 것) 궁금합니다.
2. 재귀적으로 이분탐색 함수를 호출할 때에 어떨 때는 m, 어떨 때는 m + 1, 어떨 때는 m - 1이런식으로 쓰는데 정확한 기준을 잘 몰라 이분탐색 문제를 풀 때마다 너무 헷갈립니다. 혹시 명확한 기준이 있나요?
질문이 좀 많고 글도 잘 못썼지만 잘 부탁드립니다 ㅠㅠㅠ