한국어로 찾았을 때 아무결과도 안나오는거 보면 좀 마이너한듯?? linear data structure이고, linked list와 array의 장점을 모두 살린 자료구조이다. 링크드 리스트 장점: 삽입하는데 O(1)걸린다. 근데 단점 - search시간이 O(n)이다... Q) search시간을 줄일 수 없을까??? unrolled linked list는 array와 linked list의 장점을 모두 갖고 있다 - 한 노드에 여러개를 보관해서 search시간 낮아지고, insertion과 deletion이 linked list만큼 빠르다. 일반적인 구현으로는 꽉 채우지 않고 3/4정도만 채워준다고 한다. 장점) pointer/refernece를 위한 storage down. linked list는 하..
from collections import deque deque = deque(배열) deque.append(원소) : 오른쪽에 삽입 deque.appendleft(원소) : 왼쪽에 삽입 deque.popleft() : 왼쪽 pop deque.pop() : 오른쪽 pop deque.clear() : 삭제 deque.insert(i, 원소) : i번째에 원소 삽입 list()보다는 확실히!! 빠른것을 확인할 수 있다. list도 append, pop, len 다 O(1)이어서 괜찮을 줄 알았는데...😢 * list는 끝 원소의 pop만 O(1)이고 pop(0)은 O(N)이라고 한다 * [시간복잡도] https://wiki.python.org/moin/TimeComplexity https://j-ungry...
decimal.getcontext().prec = 50 decimal.getcontext().rounding = decimal.ROUND_HALF_UP if value decimal.Decimal(-1e-9): pi = Decimal('3.14159265358979323846264338327950288419716939937510') def sin(x): x = x % (2 * pi) getcontext().prec += 2 i, lasts, s, fact, num, sign = 1, 0, x, 1, x, 1 while s != lasts: lasts = s i += 2 fact *= i * (i - 1) num *= x * x sign *=..
포인트는 윗줄에서 무게뺀거 + 새로운 아이템 가치랑, 그냥 윗줄이랑 비교해서 더 무거운걸 채우는거다 아직 현 아이템을 채울 정도의 weight이 되지 않았다면 그냥 윗줄꺼를 채워주면 된다. for i in range(1, N + 1): for j in range(1, K + 1): weight = stuff[i][0] value = stuff[i][1] if j < weight: knapsack[i][j] = knapsack[i - 1][j] else: knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j]) [문제 유형] 평범한 베낭 - 아이템이 한종류 카우버거 알바생
난 재귀를 극혐하므로 가능하면 반복으로 구현한다... target = 25 m_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7] length = len(m_list) m_list.sort() left = 0 right = length-1 while lefttarget: right = mid-1 else : left = mid+1 [문제 유형] 가장 흔한건 숫자가 존재하는지 여부 찾기 나무, 전선 자르기: min을 0으로, max를 리스트의 최대값으로 잡고 점점 좁혀나간다. 조금 번외인건 공유기 설치 - 주어진 개수만큼의 공유기를 최대한 거리 멀게 설치하는 유형. 거리를 min을 0으로, max를 리스트의 최대값으로 잡고 점점 좁혀나간다..