Dp

사고 같은 크기의 matrix 에 0, 0 부터 현재 index 까지 만들어지는 사각형 sum 을 저장하는 방식이 쉬우면서도 효율적인 접근이다. 왜인지 모르겠으나 불필요한 operation 이 포함된다고 생각해서 나는 같은 크기의 matrix 에 같은 row 에 있는 현재까지의 column sum 을 저장했다. 결론적으로 첫번째 접근보다 비효율적이다. 긴 row 에는 dp 에 여러번 접근해야할뿐더러 row 가 길수록 col1 을 빼주는 operation 을 많이 하게 된다. class NumMatrix: mat = None def __init__(self, matrix: list[list[int]]): self.mat = [[0] * len(matrix[0]) for _ in range(len(matrix))] for r in range(len(matrix)): self.mat[r][0] = matrix[r][0] for c in range(1, len(matrix[0])): self.mat[r][c] = self.mat[r][c - 1] + matrix[r][c] def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int: blk = 0 for r in range(row1, row2 + 1): blk += self.mat[r][col2] blk -= self.mat[r][col1 - 1] if col1 > 0 else 0 return blk

접근 전체 node 가 head를 제외하고 n개일 때 head 에서 왼쪽에 k, 오른쪽에 n-k 만큼의 node를 갖는 경우의 수는 dp[k] * dp[n - k] 이다. 경우의 수를 곱해서 찾기 때문에 dp[0] 은 1로 둔다. 사고 예제 그림에서 보듯이 가능한 현재 경우의 수는 이전의 경우의 수 전체를 왼쪽 subtree, 오른쪽 subtree 로 갖는 경우로 생각해서 dp[i - 1] * 2 + ? 으로 시작했다. 이건 왼쪽에 dp[n - 1] 개, 오른쪽 0 그리고 오른쪽 dp[n - 1], 왼쪽 0 개를 가지는 하나의 케이스라고 생각했다. 그래서 모든 경우의 수를 수도코드로 생각하고 아래와 같이 구현했다. ...

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

접근 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 중에 무엇을 메모이제이션해야 할 지 감이 안 오는 문제들이 훨씬 어려운 것 같다. ...

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

접근 처음 두 줄의 LCS 를 찾고, 그 결과와 마지막 줄의 LCS 를 찾는 순차적인 방법으로도 가능하다. 하지만 3차원 dp 로 처리하는 방법이 확장 가능성이 있기에 더 좋은 접근법이라 생각한다. import sys input = sys.stdin.readline f = input().strip() s = input().strip() t = input().strip() fl = len(f) sl = len(s) tl = len(t) dp = [[[-1] * tl for i in range(sl)] for j in range(fl)] def LCS(a, b, c): if a < 0 or b < 0 or c < 0: return 0 if dp[a][b][c] == -1: dp[a][b][c] = 0 if f[a] == s[b] == t[c]: dp[a][b][c] = LCS(a - 1, b - 1, c - 1) + 1 else: dp[a][b][c] = max(max(LCS(a, b - 1, c), LCS(a - 1, b, c)), LCS(a, b, c - 1)) return dp[a][b][c] print(LCS(fl - 1, sl - 1, tl - 1))