링크

징검다리

문제 요약

  • 돌이 일정거리로 나열된 rocks에 n개의 돌을 지웠을때 각 돌 사이의 간격의 최소중 최대인 값은?

초반 접근

  • 모든 경우를 확인해보았다.
    • rocks에서 n개를 뺀 경우를 모두 출력
    • 경우에서 나오는 돌의 간격을 계산
    • 각 최솟값에서 최댓값 구하기
  • 당연하게 runtime error가 나왔다.
    • n개를 뺀 경우를 모두 계산하는데 시간이 많이 걸린다.

해결법

  • 이분법에 대한 접근 방식은 다르게 생각 해야 했다.
  • 문제를 있는 그대로 읽고 해결하는게 아닌, 기준을 무엇으로 할지가 관건인게 이분법문제이다.
  • n개를 지운다는것에 집중하지 말고, 돌사이 간격을 만드는것에 집중해보자.
    • 이렇게 생각하는게 많이 어렵고, 많이 접하고 익숙해져야 이런 접근이 바로 나올거 같다.
  • 문제에서 돌사이 최솟값은 각 돌을 지웠을때, 해당 값보다 크거나 같은 값들로 돌사이 거리가 이루어진것을 볼 수 있다.

알고리즘 간단 정리

  • 먼저 rocks는 돌의 위치를 저장한 배열로 정렬을 오름차순으로 해준다.
  • 돌사이 간격을 이분법으로 걸정한다.
    • left는0, right는 distance, mid는 left와right를 더하고 나눈 값
      • 시작위치(0)에서 시작하여 rocks의 마지막까지 mid만큼의 거리가 만들어지는지 확인한다.
        • 만약 mid보다 낮으면
          • 아직 mid가 최솟값이 아니라는 의미가 된다.
          • 돌을 하나 건너뛴다.
        • 만약 mid보다 크거나 같으면
          • mid가 최솟값이 되었단는 의미가 된다.
          • 시작위치를 현재 돌의 위치로 변경한다.
    • 돌을 건너뛰는게 n보다 많으면 기대치를 낮춘다.
      • right를 mid-1로
    • 돌을 건너뛰는게 n과 같거나 낮으면 기대치를 높인다.
      • left를 mid+1로

후기

  • 이런 문제는 어떻게 문제를 다르게 생각하느냐가 중요했다.
  • 많이 어려웠고, 이분법의 기준을 찾는것도 이해하고 완벽히 습득하는데 오래결렸다.
  • 이것을 못해도 한시간 내로 바로 해결하라 하면 못했을 것이다.
  • 이분법의 힌트를 얻기위해 인터넷의 힘을 빌렸다.
    • 힌트를 봐도 바로 이해하기 힘들어 정리하고 생각하는데도 오래걸렸다.
  • 이런 이분법은 대부분 완전탐색으로도 풀린다. 완전탐색만 자주 하다보니 문제를 보면 바로 완전탐색으로 푸는 경향이 있다.
    • 완전탐색방식도 좋지만 이런 이분 탐색방식 처럼 좀더 효율적으로 해결하는 방식을 바로 도출하는 숙련도가 많이 부족하다.

출처

https://taesan94.tistory.com/154 https://velog.io/@hyeon930/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC-Java