접근 현재 pointer 와 닿을 수 있는 최대 거리인 reach, 점프 횟수 카운트, 새로운 reach 후보 변수인 temp 네 가지 변수를 이용한다. 닿는 index 중 가장 멀리까지 갈 수 있는 index 를 temp 후보와 비교해 업데이트 한다. 이제 점프할 차례 때 가장 큰 temp 값을 보장해주는 곳으로 점프하고 이전 pointer에 이어서 후보군을 탐색한다. 지금까지 본 곳 중에서는 지금 자리가 가장 멀리까지 갈 수 있다는 사실을 알기 때문이다. 따라서 pointer 가 linear 로 진행하는 것이 곧 시간복잡도 O(n) 이 되며 최적해이다. 사고 앞선 Jump Game 과 다른 점은 reach 를 계속 업데이트 하지 않고 후보군을 끝까지 탐색 후 jump++ 와 reach 변수 재지정이 이루어지는 것이다. 그렇게 뜨문 뜨문 갱신되는 reach 내에서 loop를 반복적으로 돌아준다. ...
접근 현재 pointer 와 닿을 수 있는 최대 거리인 reach 두 변수를 이용한다. 닿는 index 중 가장 멀리까지 갈 수 있는 reach 로 계속해서 업데이트 한다. reach 만 max 를 이용해 업데이트하고 pointer 는 linear 로 움직인다 O(n). 사고 먼저 최대거리로 포인터를 옮기고 진행이 불가능하면 하나씩 뒤로 무르는 backtracking 이 떠올랐다. 하지만 visit 을 체크하는 과정에서 비효율적이라는 생각이 들어 기각했다. class Solution: def canJump(self, nums: list[int]) -> bool: pointer = 0 reach = nums[pointer] if reach + 1 >= len(nums): return True while pointer < reach: pointer += 1 reach = max(reach, pointer + nums[pointer]) if reach + 1 >= len(nums): return True return False
접근 처음과 마지막이 접하기 때문에 House Robber I 과 다른 방식을 생각해야한다. 첫번째 집을 털면 마지막 집은 고려할 필요가 없다. 그래서 0, len(배열) - 1 과 1, len(배열) 로 자른 두개의 배열에 단순하게 접근하면 된다. 사고 한참 예전에 이와 비슷한 cycle 이 있는 배열 dp 문제를 풀었는데 그보다 시간이 지난 뒤에 못 풀어서 당황했던 기억이 있다. 그 당시엔 아마 배열 마지막 집 전까지 dp 업데이트 후 첫번째 집과 마지막 집 value 를 비교했던것 같은데, 위험한 접근이고 edge case 도 매우 많았을 거라 생각된다. ...
접근 기본적인 배경은 이분 탐색이다. 현재 pivot 기준으로 왼쪽을 봐야할지, 오른쪽을 봐야할지 조건을 생각하는 것이 관건이다. 만약 nums[low] <= nums[mid] 라면, 왼쪽 subarray 는 정렬되어있다. target 이 해당 range 를 벗어나면 오른쪽을 본다. 만약 nums[low] > nums[mid] 라면, 오른쪽 subarray 가 정렬되어있다. target 이 오른쪽 subarray 의 range 를 벗어나면 왼쪽을 본다. 사고 binary search 를 필요한 만큼 수정해서 직접 이용할 수 있는지 묻는 문제이다. 직접 sorting algorithm 을 구현하는 것보다는 개인적으로 쉽고 또 자주 직접 customizing 해야한다. 다양한 정렬 문제들을 Comparator 를 이용해서 접근하는 것처럼 binary search 또한 다른 상황에서 직접 필요한 부분을 수정해서 쓸 수 있도록 연습하자. ...