dp9 [자료구조] 등굣길 파이썬 (DP) def solution(m, n, puddles): dp = [[0]*(m+1) for _ in range(n+1)] # first row and colum are 1 for i in range(n+1): for j in range(m+1): if i == 1 or j == 1: dp[i][j] = 1 if i == 0 or j == 0: dp[i][j] = 0 if m 2021. 4. 26. [LeetCode] Fatorial Trailing Zeros 파이썬 (dp) cache = {} class Solution: def factorial_recursive(self,n): global cache if n in cache: return cache[n] elif n 1 else 1 def get_zeros(self, ls): ls = list(str(ls))[::-1] cnt = 0 for num in ls: if num == "0": cnt += 1 else: break return cnt def trailingZeroes(self, n: int) -> int: if n == 0: return 0 else: ans = self.factorial_recursive(n) ans = self.get_zeros(ans) return ans DP로 Factorial을 구하는 메.. 2021. 4. 3. [LeetCode] Climbing Stairs 파이썬 (DP) 28ms class Solution: def climbStairs(self, n: int) -> int: if n == 1: return 1 elif n == 2: return 2 else: dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n] swap 사용 32 ms if n == 1: return 1 a, b = 1, 2 for i in range(2, n): a, b = b, a + b return b 2021. 3. 30. [LeetCode] Maximum Subarray 파이썬 (dp, local max, global max) dp 사용 class Solution: def maxSubArray(self, nums: List[int]) -> int: dp = [num for num in nums] for i in range(1, len(nums)): dp[i] = max(dp[i-1]+nums[i], nums[i]) return max(dp) dp 미사용 class Solution: def maxSubArray(self, nums: List[int]) -> int: # 3/26/2021 microsoft prep max_sub = 0 global_max = float('-inf') for n in nums: max_sub = max(max_sub + n, n) global_max = max(max_sub, global_max) .. 2021. 3. 30. [프로그래머스] N으로 표현 파이썬 (DP) 출처:goldfishhead.tistory.com/50 def solution(N, number): answer = -1 DP = [] for i in range(1, 9): num_set = { int(str(N) * i) } for j in range(0, i - 1): for x in DP[j]: for y in DP[-j - 1]: num_set.add(x + y) num_set.add(x - y) num_set.add(x * y) if y != 0: num_set.add(x // y) if number in num_set: return i DP.append(num_set) return answer 2021. 3. 16. [프로그래머스] 2 x n 타일 파이썬 (DP) def solution(n): dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = (dp[i-1] + dp[i-2])% 1000000007 return dp[n] def solution(n): dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = (dp[i-1] + dp[i-2])% 1000000007 return dp[n] 출처: it-garden.tistory.com/410 2021. 3. 16. [프로그래머스] 예상 대진표 파이썬 (DP) def solution(n,a,b): answer = 0 while a != b: answer += 1 a, b = (a+1)//2, (b+1)//2 return answer 2021. 3. 16. [프로그래머스] 피보나치 수 파이썬 역시 재귀로 풀었더니 런타임오류 DP로 수정 def solution(n): fibo = [] for x in range(0,n): if x < 2: fibo.append(1) else: fibo.append(fibo[x-2] + fibo[x-1]) answer = fibo[-1]%1234567 return answer Pythonic way def solution(num): a,b = 0,1 for i in range(num): a,b = b,a+b return a 2021. 3. 16. [프로그래머스] 가장 큰 정사각형 찾기 파이썬 (DP) 예전에 fastcampus에서 한번 다뤘던 문제라고 기억을 하는데 이미 기억에서 지워진 문제 DP로 푸는것만 기억하고 나머지는 다 잊어버림 def solution(board): width = len(board[0]) height = len(board) for x in range(1,height): for y in range(1,width): if board[x][y] == 1: board[x][y] = min(board[x-1][y-1], min(board[x-1][y], board[x][y-1])) + 1 return max([item for row in board for item in row])**2 출처:geonlee.tistory.com/111 굳이 DP list를 만들겠다면 def solutio.. 2021. 3. 15. 이전 1 다음