반응형 전체 글571 [ 리트코드 leetcode] 70. Climbing Stairs leetcode.com/problems/climbing-stairs/ Climbing Stairs - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이 문제는 사실 피보나치 수열과 같은 문제다. n번째 계단에 도착을 하려면 그 이전 시점에는 n-1번째 또는 n-2번째 계단에 위치해있을 것이다. 즉 f(n) = f(n-1) + f(n-2) 임을 알 수 있다. class Solution: def climbStairs(self, n: int) -> int: if n 2021. 4. 19. [리트코드 leetcode] 53. Maximum Subarray leetcode.com/problems/maximum-subarray/ Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com class Solution: def maxSubArray(self, nums: List[int]) -> int: maximum= -sys.maxsize sum=0 for num in nums: sum+=num maximum = max(maximum, sum) if sum < 0 and num 2021. 4. 19. [알고리즘 algorithm] 다이나믹 프로그래밍 dynamic programming 방법론, 예제 이 글은 '파이썬 알고리즘 인터뷰'라는 책을 참고하여 작성하였습니다. - 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘. - 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우의 문제, 즉 최적 부분 구조를 갖고 있는 문제를 풀이할 수 있다. - 타뷸레이션(Tabulation): 상향식 접근법 - 메모이제이션(Memoization): 하향식 접근법 ex) 피보나치 수열 코드 작성 예제 ## tabulation def fib(n): dp[0]=0 dp[1]=1 for i in range(2,n+1): dp[i] = dp[i-1]+ dp[i-2] return dp[n] ## memoization def fib(n): i.. 2021. 4. 19. [알고리즘 algorithm] 분할 정복 divide and conquer 활용 예제 분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임이다. - 대표적인 분할정복 알고리즘으로 병합정렬이 있다. - 문제를 재귀로 쪼개 직접 해결할 수 있을 정도로 만든 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어낸다. 분할 정복은 재귀 구조랑 거의 동일하며, 단지 넘겨주는 인자를 점점 분할하여 넘긴다. 이때 윈도우 슬라이싱이 잘 활용된다. - 분할 정렬 : 대표적인 분할 정복 알고리즘 분할 과정) 긴 배열을 정렬해야 한다 => 어렵다. 쪼개자. 두 개의 배열로 쪼갬 => 여전히 어렵다. 더 쪼개자. 각각의 배열이 다시 2개로 쪼개져 총 4개의 배열이 됨. => 계속 쪼개자. 이런 방식으로 계속 진행하다보면 마지막에는 1개의 원소만을 가진 배열로 쪼개짐. 정복 과정).. 2021. 4. 19. [리트코드 leetcode] 241. Different Ways to Add Parentheses leetcode.com/problems/different-ways-to-add-parentheses/ Different Ways to Add Parentheses - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com class Solution: def diffWaysToCompute(self, expression: str) -> List[int]: values = [] def compute(left,right,op): for l in left: for r in ri.. 2021. 4. 19. [리트코드 leetcode] 621. Task Scheduler leetcode.com/problems/task-scheduler/ Task Scheduler - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 2시간 고생해서 heap으로 풀어냈다. 하지만 너무 1차원적인 풀이라서 시간이 매우 오래 걸렸다.. class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: wait = {} for task in tasks: wait[task]=0 counter.. 2021. 4. 17. 이전 1 ··· 73 74 75 76 77 78 79 ··· 96 다음 반응형
