CS STUDY

https://leetcode.com/problems/fibonacci-number/ Fibonacci Number - 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 1. 재귀 구조 브루트 포스 class Solution: def fib(self, n: int) -> int: if N int: if n int: self.dp[1]=1 for i in range(2,n+1): self.dp[i] = self.dp[i-1] + self.dp[i-2] return s..

다이나믹 프로그래밍 방법론 피보나치 수열의 예제 코드를 보면 상향식과 하향식의 구분이 금방 이해 된다.

https://leetcode.com/problems/different-ways-to-add-parentheses/ 괄호를 어디에 추가하느냐에 따라 다양한 조합이 가능하다. 모든 조합을 계산해야 하는데 이는 다음 그림과 같이 분할 정복으로 가능하다. *,-,+ 연산자가 등장할 때 좌/우 분할을 하고 각각 계산 결과를 리턴한다. 분할된 값은 compute() 함수로 계산한 결과를 extend()로 확장한다. 분할 결과를 리턴받으려면 input이 숫자형일 때 리턴하게 한다. 계산하는 부분은 다음과 같다. eval() 함수는 문자열을 파싱하고 파이썬 표현식으로 처리해주는 Evaluate 역할을 한다. class Solution: def diffWaysToCompute(self, expression: str) ..

분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임을 말한다. 분할 정복(Divide and Conquer)은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 낸다. 대표적인 분할 정복 알고리즘은 병합 정렬을 들 수 있는데, 병합 정렬 과정을 표현한 그림은 다음과 같다. https://leetcode.com/problems/majority-element/submissions/ Majority Element - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your kn..

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/submissions/ Best Time to Buy and Sell Stock II - 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 maxProfit(self, prices: ..