Algorithms

접근 dp 는 s의 현재 index를 단어의 끝으로 가장 길게 완성할 수 있는 시작 index를 가리킨다. 각 스트링 인덱스 i 마다 0부터 i까지 loop 돌며 딕셔너리에 있는지 확인한다. 딕셔너리에 있다면 그 앞선 단어와 연결되는지 확인 후 dp 업데이트 한다. i-5 ~ i 까지 이어지는 단어가 있다면 ?? ~ i-6 까지 이어진 단어가 있는지 보는식이다. 사고 처음에 dfs 로 접근하였다. 시간초과를 받고 dp 로 다시 풀었다. 시간 복잡도 O(s.length ^ 2) ...

접근 linear 로 훝으며 모든 값을 곱하며 진행한다. 메모리 절약을 위해 부호만 기록한다. 각 index 에서 여태의 곱연산 부호에 따라 조건부로 최대 부분 수열 길이를 갱신한다. 0 을 만나면 필요한 변수들 초기화한다. 사고 0은 처리해줘야 하고, 양수는 곱해져도 어딜 slicing 하는지에 따라 부호가 바뀌지 않는다. 따라서 0이 아닌 값들을 쭉 이어서 길이를 기억한다. 첫번재 음수가 나오는 인덱스를 표시해놓고 현재 pointer 까지 곱연산이 양수이면 현재 까지 이어진 값의 길이와 max 를 비교해서 값을 갱신하고 음수라면 (pointer - 첫번째 음수 인덱스) 와 max 를 비교하여 갱신한다. ...

접근 현재 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 도 매우 많았을 거라 생각된다. ...

접근, 사고 확실히 푼 문제 수가 쌓일수록 유형별로 나눠서 생각하기가 수월한것 같다. 이 유형의 베이스는 Two Sum 이다 (무려 리트코드의 첫번째 문제!!). 배열을 탐색하며 두 개의 합의 target 이 되는 쌍을 찾는 문제인데 해쉬를 이용해 한 번 linear 로 훑는 것으로 풀 수 있다. 대략적인 풀이과정은 set 선언 배열 지나가며 각각 원소 i에 대해 target - i 가 set 에 있으면 해당 쌍 리턴, 없으면 set.add(i) 해준다. 본 문제도 이와 크게 다르지 않다. ...

접근 s 와 e 를 받아서 2차원 배열로 각각의 질문에 O(1) 에 답하는 것이 목표이다. 2000 X 2000 배열을 미리 초기화 한다면 초기화에 O(N ^ 2), 질문에 답하는 데 O(1) 이다. 점화식으로 top-down 으로 접근해서 풀었다. 이때 질문과 답하면서 배열을 조정한다. dp[s][e] 는 dp[s + 1][e - 1] 이 팰린드롬이라면 칠판배열[s] == 칠판배열[e] 에 따라 갈린다. base case 는 s == e 와 s == e - 1 인 경우 (s + 1, e - 1을 조회할 수 없기 때문에) 로 뒀다. 사고 이렇게 대놓고 배열로 풀어주세요 하는 건 어느정도 익숙하다. DP 중에 무엇을 메모이제이션해야 할 지 감이 안 오는 문제들이 훨씬 어려운 것 같다. ...

접근 기본적인 배경은 이분 탐색이다. 현재 pivot 기준으로 왼쪽을 봐야할지, 오른쪽을 봐야할지 조건을 생각하는 것이 관건이다. 만약 nums[low] <= nums[mid] 라면, 왼쪽 subarray 는 정렬되어있다. target 이 해당 range 를 벗어나면 오른쪽을 본다. 만약 nums[low] > nums[mid] 라면, 오른쪽 subarray 가 정렬되어있다. target 이 오른쪽 subarray 의 range 를 벗어나면 왼쪽을 본다. 사고 binary search 를 필요한 만큼 수정해서 직접 이용할 수 있는지 묻는 문제이다. 직접 sorting algorithm 을 구현하는 것보다는 개인적으로 쉽고 또 자주 직접 customizing 해야한다. 다양한 정렬 문제들을 Comparator 를 이용해서 접근하는 것처럼 binary search 또한 다른 상황에서 직접 필요한 부분을 수정해서 쓸 수 있도록 연습하자. ...

접근 열 길이가 기차의 수 + 1이고, 행 길이가 3인 dp 행렬로 접근한다. 13번째 행은 각각 현재 인덱스에서 13번째 열차가 골라졌다면 실을 수 있는 최대 손님의 수다. 입력으로 받은 train 리스트를 탐색하며 window 만큼 떨어져 있는 dp 를 업데이트 한다. dp 업데이트는 dp[현재 열 - window][현재행 - 1] 과 dp[현재 열 - 1][현재 행] 중 큰 것을 고른다. 사고 반복되는 연산을 최소화하는 DP 문제를 연습하는 중이니 다른 최적화도 가능하다면 시도해보자. 문제에서 소형 기관차의 길이가 길다면 겹치는 구간을 반복해서 구해야 할 것이다. ...

접근 방문 기록을 리스트로 기억한다. DFS 에 현재 탐색 중인 좌표들이 담긴 큐와 현재 위치를 인자로 받는다. 방문마다 방문 기록을 업데이트 해주고 DFS 를 진행한다. 방문한 곳을 마주하면 경우는 두 가지이다. Safe zone 으로 나갈 수 있는 경우, 만들어줘야 하는 경우. 사고 제약 조건이 적어 쉽게 접근할 수 있었다. 사이클을 찾으면 그 사이클과 사이클에 들어올 수 있는 모든 경로는 Safe Zone 하나로 도망 가능하다. 이 원칙 하나로 구현하면 큰 어려움 없이 풀 수 있다. ...