접근 정렬되어 있는 array 의 처음과 끝에 포인터를 둔다. target 과 비교하며 포인터를 움직인다. 사고 정렬되어 있고, 답이 하나로 보장되어 있다길래 two pointer 썼다. class Solution: def twoSum(self, numbers: list[int], target: int) -> list[int]: i, e = 0, len(numbers) - 1 while i < e: if numbers[i] + numbers[e] == target: return [i + 1, e + 1] elif numbers[i] + numbers[e] > target: e -= 1 else: i += 1
사고 같은 크기의 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