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이런식으로 쓰는데 정확한 기준을 잘 몰라 이분탐색 문제를 풀 때마다 너무 헷갈립니다. 혹시 명확한 기준이 있나요?

질문이 좀 많고 글도 잘 못썼지만 잘 부탁드립니다 ㅠㅠㅠ

seico75   2년 전

시간 초과의 원인은 말씀하신 부분이 아니고, 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년 전

질문이 제가 하고도 너무 난잡하고 이것저것 물어보는게 많아서 답변을 그렇게 기대하지는 않았는데, 이렇게 상세하게 이해되도록 설명해주셔서 너무 감사드립니다ㅠㅠ 이거 너무 헷갈려서 짜증나고 답답했는데, 기분좋아졌네요~ 진심으로 감사합니다!!! 

댓글을 작성하려면 로그인해야 합니다.