문제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..
Distribution ShiftDistribution Shift는 훈련 데이터와 실제 예측에 사용할 데이터가 다른 분포에서 생성될 때 발생하는 상황을 나타낸다. 이는 조건부 확률로 표현이 가능한데, 사건 B가 일어나는 경우에 사건 A가 일어날 확률을 '사건 B에 대한 A의 조건부확률'이라 하고 \( P(A∣B) \)로 표기한다. Distribution Shift의 대표적인 유형은 다음과 같다. Covariate Shift: \( P(Y|X) \)는 그대로이지만 \( P(X) \)는 변하는 경우.예를 들어, 학습 데이터에서는 대부분 사실적인 이미지(photorealistic images)를 보았지만, 테스트 데이터에서는 대부분 만화 같은 이미지(cartoonish images)가 제공되는 상황이 해당된다..
문제https://www.acmicpc.net/problem/25497 해설스택을 2개 사용하여 해결하였다. 이게 최선일거라 확신이 들지는 않는다. def solution(lst): answer = 0 lr_stack = [] sk_stack = [] for c in lst: if c.isdigit(): answer = answer + 1 elif c == "L": lr_stack.append(c) elif c == "R": if len(lr_stack) == 0: break lr_stack.pop() answer = an..
Cross EntropyCross Entropy는 확률 분포 간의 차이를 측정하는 지표로, 분류 문제에서 모델의 예측 성능을 평가하는 데 자주 사용된다. 이는 손실 함수의 한 종류이며, 손실 함수의 목표는 모델이 예측한 분포와 실제 분포 사이의 차이를 최소화하는 것이다. Cross Entropy를 이해하기 전 먼저 짚고 넘어가야 하는 개념이 있는데 바로 놀람도, 기대값, 엔트로피 이 세 가지이다. 먼저 놀람도에 대한 예를 들어보자.검은색 종이 999개와 흰색 종이가 1개 들어있는 상자가 있다고 가정하자. 이 상자에서 우리가 검은색 종이를 뽑았다면 우리는 당연하다고 생각할 것이다. 확률(\( p(x) \))이 훨씬 높기 때문이다. 하지만 흰색 종이가 나온다면 우리는 놀라게 될 것이다. 다시 말하면 이 놀람..
문제https://www.acmicpc.net/problem/2161 해설큐의 구조를 활용하면 된다. def solution(cards): answer = [] while len(cards)-1: answer.append(cards.pop(0)) cards.insert(len(cards)-1, cards.pop(0)) answer.append(cards.pop(0)) return " ".join(answer)num = int(input())print(solution([str(i+1) for i in range(num)]))
