문제https://leetcode.com/problems/take-gifts-from-the-richest-pile/description/ 해설최대 힙을 이용하는 문제였다. import heapqclass Solution: def pickGifts(self, gifts: List[int], k: int) -> int: heap = [-v for v in gifts] heapq.heapify(heap) for _ in range(k): heapq.heapreplace(heap, -int((-heap[0]) ** 0.5)) return -sum(heap)
문제https://www.acmicpc.net/problem/19638 해설최대 힙을 사용하는 문제였다. # PyPy3import heapqdef solution(target, cnt, heap): heapq.heapify(heap) hammer_cnt = 0 for _ in range(cnt): height = -heap[0] if height == 1 or height
문제https://www.acmicpc.net/problem/2075 해설최소 힙을 사용하여 해결하는 문제이다. 공간복잡도를 고려해야하는 문제이므로 모든 데이터를 입력받은 후 pop을 진행하는 것이 아닌 input 과정 중 필요한 공간만큼만 사용하는 것이 핵심이었다. # PyPy3import heapqdef solution(cnt): heap = [] for _ in range(cnt): for v in list(map(int, input().split())): heapq.heappush(heap, v) if len(heap) == cnt+1: heapq.heappop(heap) return heapq.heap..
머신러닝과 딥러닝에서 모델의 성능을 개선하고 일반화 능력을 높이기 위해 흔히 정규화 기법을 사용한다고 말한다. 여기서 정규화는 크게 Regularization과 Normalization으로 나뉘는데, 두 개념은 서로 다른 목적과 방식으로 적용된다. 하나의 명칭으로 해석되어 혼란스러울 때가 있어 이번에 정리해보려 한다. RegularizationRegularization은 모델의 복잡도를 제어하여 과적합(Overfitting)을 방지하는 데 사용된다. 모델의 가중치(Weight)에 제약 조건을 추가하여 학습된 모델이 새로운 데이터에 대해서도 잘 일반화할 수 있게 한다. 주요 특징가중치 규제과적합 방지모델 일반화 Regularization 방식에는 대표적으로 L1 정규화(Lasso)와 L2 정규화(Ridge..
문제https://www.acmicpc.net/problem/1927 해설최소 힙(Min Heap)을 이용하여 해결하는 문제였다. Heap은 기본적으로 이진트리 구조로 형성되므로 insert와 delete 연산의 시간 복잡도는 \( O(logn) \)이 된다. 여기서 \( log \)는 일반적으로 밑이 2인 로그로 \( log_{2}{n} \)를 얘기한다. 이 문제에서는 입력 횟수만큼 반복하므로 \( O(Nlogn) \)이 된다. 패키지를 사용하여 해결하는 방법과 직접 구현 두 가지 방식으로 풀어보았다. 이번에도 input() 메소드가 시간초과를 유발하여 PyPy3를 이용하였다. Solution 1.아래는 heap을 이용하여 해결한 방식이다. # PyPy3import heapqdef solution(l..
문제https://www.acmicpc.net/problem/26042 해설로직은 단순했지만 기존 input() 메소드 사용에서 시간초과가 발생하였다. 패키지 import 없이 모든걸 해결해보려 했는데 결국 한계가 있을 수 있을 것 같다. 이번엔 PyPy3를 사용하여 해결하였다. # Python만 사용시 아래 메소드 사용 필요# input = __import__('sys').stdin.readline# PyPy3def solution(lst): max_cnt = -1 last_student = -1 queue = [] for v in lst: if v[0] == 1: queue.append(v[-1]) if max_cnt == le..
