CS STUDY

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

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: ..

그리디 알고리즘은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘이다. 그리디 알고리즘이란 바로 눈앞의 이익만을 쫒는 알고리즘을 말한다. 대부분의 경우에는 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 그리디 알고리즘은 최적 부분 구조 문제를 푼다는 점에서 흔히 다이나믹 프로그래밍과 비교되는데, 서로 풀 수 있는 문제의 성격이 다르며 알고리즘의 접근 방식 또한 다르다. 그리디 알고리즘을 중심으로 풀 수 있는문제, 다이나믹 프로그래밍으로 풀어야 하는 문제, 그리디 알고리즘으로는 풀 수 없는 문제들에 대해 차례대로 살펴보자. 배낭 문제 배낭 문제는 조합 최적화 분야의 매우 유명한 문제로, 다..

슬라이딩 윈도우(Sliding Window)란 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다. 슬라이딩 윈도우는 투포인터와 함께 알고리즘 문제 풀이에 매우 유용하게 사용되는 중요한 기법이다. https://leetcode.com/problems/sliding-window-maximum/ Sliding Window Maximum - 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. 브루트 포스로 계산 cla..

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/submissions/ Two Sum II - Input Array Is Sorted - 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 twoSum(self, numbers: List[int], target: int) -> List[i..

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None) 정렬된 순서를 유지하도록 a에 x를 삽입할 위치를 찾는다. nums1 = [4,9,5] nums2 = [9,4,9,8,4] nums2.sort() result=set() for n1 in nums1: index=bisect.bisect_left(nums2,n1) print(index) if len(nums2)>0 and len(nums2)>index and n1==nums2[index]: result.add(n1) print(result) 위 코드는 num1과 nums2의 교집합을 찾는 코드이다. index=bisect.bisect_left(nums2,n1)에서 n1이 정렬된 num2에 들어갈 위치를 반환한..

이진 검색은 값을 찾아내는 시간 복잡도가 O(log n)이라는 점에서 대표적인 로그 시간 알고리즘이며, 이진 탐색 트리와도 유사한 점이 많다. 그러나 이진 탐색 트리가 정렬된 구조를 저장하고 탐색하는 '자료구조' 라면, 이진 검색은 정렬된 배열에서 값을 찾아내는 '알고리즘' 자체를 지칭한다. https://leetcode.com/problems/binary-search/submissions/ Binary Search - 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.c..

https://leetcode.com/problems/kth-largest-element-in-an-array/submissions/ Kth Largest Element in an Array - 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. heapq 모듈 이용 class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heap=list() for n in nums: heapq.hea..