프로그래밍22 leetcode 62. Unique Paths 풀이 문제 : int m 과 n 이 주어질때 m x n grid (0,0) 에서 출발해서 right, down으로만 이동하여 (m-1, n-1) 에 도달한다. 도달하는 유니크한 경우의 수를 반환하라 Follow up : 아이디어 : 이전에 풀었던 경로상의 비용을 최소화 하는 dp문제와 유사하다고 생각했다. 가로로만 가는 경우, 세로로만 가는 경우는 유니크 경로가 하나만 존재한다. 이 경우를 먼저 설정한 후. 나머지 경로에 대해서는 인접한 left, top 경로의 경우의 수 합으로 유니크 경로를 저장한다. 코드 : class Solution: def uniquePaths(self, m: int, n: int) -> int: p = [[0 for j in range(n)] for i in range(m)] for.. 2021. 4. 23. leecode 238. Product of Array Except Self 풀이 문제 : int 로 이루어진 list가 주어질 때 해당 인덱스의 원소를 제외한 나머지 원소의 곱을 인덱스와 원소로 가지는 list는 반환하라 Follow up : 아이디어 : K * O(n) 의 시간 복잡도를 가지기 위해, 0을 제외한 나머지 모든 원소의 곱을 곱해서 저장한다. 0은 갯수를 카운트 한다. 다음 번 순회에서 0일때는 다른 0이 있는 지 확인 후 있으면 0 반환, 없으면 m을 반환. 0이 아닐때는 0이 있다면 0 반환, 없으면 m // num을 반환한다. 코드 : class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: m = 1 zc = 0 ans = [] for num in nums: if num == 0: zc.. 2021. 4. 23. leecode 22. Generate Parentheses 풀이 문제 : 아래와 같이 n이 주어질 때 ( 1 2021. 4. 23. leetcode 494. Target Sum 풀이 문제 : int 로 이루어진 list가 주어질때 원소들의 +, - 를 통해 target에 도달하는 경우의 수를 반환하라. Follow up : 아이디어 : DFS 를 통해 풀었지만 풀면서도 이거 반드시 timeout 날 것이라 생각했고 역시나 timeout이 발생했다. dictionary 를 통해서 tracking을 해야할거 같은데 명확한 방법이 생각나지 않았다. 코드 : 처음 작성한 코드 class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: global ans ans = 0 def dfs(i, s): global ans print(i, s, ans) if i == len(nums) - 1: if s == tar.. 2021. 4. 22. 이전 1 2 3 4 5 6 다음