알고리즘/이론

백준에는 잘 나오지 않는 부분 배열/부분 집합 DP 로직에 대해 정리해 보았다. 1차원 배열 A에서 생각해볼 수 있는 DP 접근을 다양하게 해볼 수 있다. 간단한 목차는 아래와 같다. 1. 배열 A의 부분 배열의 최댓값 (제한 X) 2. 배열 A의 k개의 연속한 부분 배열의 최댓값 (k개라는 제한이 존재한다) 3. 배열 A의 k개 이상 연속한 부분 배열의 최댓값 (k개 이상이라는 제한이 존재한다.) 4. 배열 A에서 부분집합의 합이 S인 부분집합이 존재하는가? (존재 여부, 제한 X) 5. 배열 A에서 k개의 부분집합의 합이 S인 부분집합이 존재하는가? (존재 여부, k개라는 제한이 존재한다)1. 배열 A의 부분 배열의 최댓값 (제한 X)배열 A가 주어졌을 때, 이 배열의 부분 배열 A의 최댓값을 구하라..

분할정복의 시간복잡도는 NlogN이다. (단계 별 문제 개수 (N//2^K) X 해당 단계에서 쪼개는/병합하는 시간(2^K) X 단계 개수(크기가 이진탐색 수준으로 줄기 때문에 logN)) 이것을 밑으로 내려가면서 쪼갤 때 / 위로 올라오면서 병합할 때 2번해서 어차피 2 NlogN이므로 시간복잡도는 그냥 NlogN이다. (DP테이블은 문제 종류가 M이라고 하면 O(NM)이라 더 효과적인 것을 확인할 수 있음) ★DP와 다른 점 부분 문제가 서로 중복되지 않는다. 위 사항 덕분에 Memoization이 필요하지 않다. 굳이 내가 알아낸 데이터를 저장하지 않는다. ★이분탐색트리 또는 세그먼트 트리와 다른 점 이분탐색/세그먼트는 일단 아는 노드를 쭉 나열해 두고 둘씩 짝지어서 위로 올라가며 판단하는 과정을 ..

binary search, 이분법적으로 딱 ' 이 시간. 이 숫자. 이 갯수 '를 구하고 싶을 때 매우 강력한 툴이다. 하지만 너무 생각할 게 많다.. 그래서 꾸준히 정리를 해보도록 하겠다!!! (자꾸 끼워 맞추면서 풀다가 실전에서 시간 너무 오래 잡지 말자...) [1, 2, 3, 3, 3, 3, 4, 5, 5] 라는 배열이 있다. 우리는 3을 찾고 싶다. 음.. 3 중에서도 가장 최소의 index를 가지는 3을 찾고 싶다면, 이렇게 mid가 가장 왼쪽을 향하게 하도록 극한으로 몰아세운다. (직접 해보면 이해 잘 됨) while lo target: return binary_search(array, target, start, mid) #중간값의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 elif ar..

대뜸 다음 코드에서 값이 어떻게 나올지 예상해 보자. def spam(eggs): eggs.append(1) eggs=[2,3] ham=[0] spam(ham) print(ham) 그래, 배열은 메모리 주소값을 할당하는 거라고 했고, 함수 spam에 인수로 넣은 ham이 eggs가 되는 격이니까 답은 [2,3]! 이라고 했다면... ㅎㅎ이 글을 보게 된 것이 다행이다!! spam에 함수의 parameter는 eggs이다. 따라서 우리가 ham을 spam에 넣어준 동시에 함수의 parameter eggs는 ham 자체가 된다. 3행에서 eggs는 새로운 리스트를 만드는 코드이다. 그래서 이 경우, 더는 ham과 eggs와 같은 메모리 주소를 가리키지 않고 eggs는 자신만의 메모리 주소를 가지게 된다. 함..

먼저 python list의 메모리 관리 방식에 대한 이해가 필요하다. python에서 연산자 중에 '=='는 값을 비교하는 연산자이고, 'is'는 메모리의 주소를 비교하는 연산이다. 아래 코드를 보자.a=300 b=300 a is b #False a == b #True그런데 조금 다른 결과가 나타나는 경우가 있는데,a = 1 b = 1 a is b #True a == b #True엥? 이 때는 a와 b의 메모리 주소가 같은 걸까?? 이것은 파이썬의 정수형 저장 방식의 특성 때문인데, -5부터 256까지의 정수값은 특정 메모리 주소에 저장한 후 해당 숫자를 할당하려고 하면 해당 변수는 그 숫자가 가진 메모리 주소로 연결한다. 리스트가 위와 같은 메모리 저장 방식을 택하고 있다고 생각하면 되는데, 파이썬은..