Notion에서 작성된 글이라, 여기 에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 징검다리

[징검다리] Parametric Search + Greedy

• 입국심사 문제와 추가로 두 문제정도를 풀면서 Parametric Search 문제에 어느 정도 감이 생겼다고 생각했는데, 아직 부족했다.
• “제거”한다는 것을 어떻게 녹여내야 할지 감이 도저히 잡히질 않았다.
• 최적화 문제가 나온다면, 아래 내용을 꼭 생각해 보고, Parametric Search를 적용할 수 있는지 꼭 꼭 생각해 보자.

  💡 Parametric Search

  • 매개변수에 따른 결과의 단조성 (정렬된 형태)
  • 매개변수 mid를 무엇으로 설정해야할지 전혀 감이 잡히질 않는다면, 최적화하고자 하는 값으로

Solution. $O(n \lg n+n \lg d)$

def solution(distance, rocks, n):
    def check(mid):
        cnt = prev = 0
        for r in rocks:
            if r-prev < mid: cnt += 1
            else: prev = r
            if cnt > n: return False
        return True
    
    rocks.sort()
    rocks.append(distance)
    
    lo, hi = 1, distance
    while lo <= hi:
        mid = (lo+hi)//2
        if check(mid):
            lo = mid+1
        else:
            hi = mid-1
    return hi

결정 문제로 변환

(설명의 편의를 위해, 각 지점 사이의 거리를 ‘간격’ 이라고 표현했습니다.)

• 각 지점 사이의 거리의 최솟값을 $mid$로 설정한다면, 바위를 몇 개 제거해야 하는가?(바위를 $n$개 이하로 제거할 수 있는가?)
  • 바위의 위치를 정렬한 다음 출발지점과 가장 가까운 바위부터 체크한다.
    • 바위의 위치를 순회하며, 설정한 간격의 최솟값 $mid$를 유지하기 위해,
      • 깨야 하는 바위(간격이 $mid$보다 작게 되는 바위)는 깨고,
      • 깨지 않아도 되는 바위(간격의 최솟값 $mid$보다 큰 바위)는 그대로 둔다.
        • 그럼 $mid$만 유지하는 선에서 아무거나 깨고 아무거나 그대로 둬도 되는가?
          • 그리디하게 접근해야 한다. 정렬된 상태에서 깨지 않아도 되는 첫 바위를 그대로 두어야, 제거하는 횟수를 최소로 하면서 최소 간격 $mid$를 유지할 수 있다. 첫 번째로 $mid$ 이상의 간격을 가진 바위를 남겨야, 그 이후의 바위들에 대해 더 많은 선택의 여지가 생긴다. 항상 가능한 한 일찍 바위를 선택하는 것이 이후의 선택에 유리하다.
          • 바위의 위치가 [1, 2, 4, 8, 9] 이고, $mid$가 3이라고 가정해 보자.
            • 첫 번째로 $mid$ 이상의 간격을 가진 바위는 4이다.
            • 4를 선택하면, 다음으로 $mid$ 이상의 간격을 가진 바위로 8을 선택할 수 있다.
            • 만약 4를 제거하고 8을 먼저 선택했다면, 더 이상 선택할 수 있는 바위가 없게 된다.
  • 문제에서는 $n$개를 제거하라고 했는데, $n$개 이하로 생각해도 될까?
    • 된다. 간격의 최솟값 $mid$가 증가함에 따라, 제거해야 하는 바위의 개수는 단조증가하기 때문이다. 가능한 $mid$의 최댓값은 결국 바위를 $n$개 제거할 때 존재한다.
  • 여기에서, 내가 반나절동안 잘못된 생각을 한 부분이 있었다.

    def solution(distance, rocks, n):
        def check(mid):
            cnt = prev = 0
            for r in rocks:
                if r-prev < mid: cnt += 1
                else: prev = r
                if cnt > n: return False
            return distance-prev >= mid
        
        rocks.sort()

    • 도착점과 가장 가까운 바위와 도착점 사이의 간격이 $mid$보다 큰 경우이다.
    • 언뜻 보면 맞는 논리다. 위의 수순을 밟아 최소 간격 $mid$를 유지하기 위해 제거할 바위들은 제거해나가면서 cnt를 증가시킨다. 최소 간격 $mid$를 유지하는 바위는 제거하지 않고 그 다음 지점의 탐색의 기준이 된다.
    • 여기까진 좋은데, 도착점과 가장 가까운 바위와 도착점 사이의 간격이 $mid$보다 작은 경우는 당연히 간격의 최솟값이 $mid$가 아니므로 불가능한 경우는 맞지만,
      • 단순히 불가능으로 False를 return해버리면 결과의 단조성이 깨진다. (똑같이 $x$번 깨면서도 어떤 상황에서는 False, 어떤 상황에서는 True가 return된다.
      • 깨지 않고 유지하는것으로 지정했던 prev 바위를 깨고, 그럼에도 $n$번보다 많이 깼는지 확인해주는 것이 결과의 단조성을 유지시켜준다.
    • 이를 구현하기 위해, rocks의 맨 뒤에 도착점에 해당하는 distance를 이어붙여준다.
      • 엥? 그러면 도착점도 바위로 인식하고 깨는 것 아닐까,,,?
        • 그걸 깨야한단 건 결국 prev를 깨지 않고 유지하면 안되고 깨야 간격의 최솟값 $mid$를 만족한다는 것을 의미한다. 따라서, 깨도록 두고 그래도 $n$ 이하라면 True를 return한다.
    • 또는, 이어붙여주지 않고, 아래와 같이 조금 더 직관적으로 나타낼 수도 있다.

      if distance-prev < mid:
          cnt += 1

이분 탐색 적용

• 거리의 최솟값은 1이고, 최댓값은 distance 이므로 $[1, \text{distance}]$로 이분 탐색을 진행한다.
• 조건을 만족하는 최댓값을 반환해야 하므로, Upper Bound를 이용한다.

---