본문 바로가기

Computer Science

(4)
Kruskal's Algorithm과 MST의 성질 어떤 가중치 있는 (연결) 그래프 $G = (V, E, w)$가 있을 때, 트리 $T$가 $G$의 스패닝 트리 임은 $T$가 $G$의 부분 그래프이고, $V(T) = G(T)$(정점 집합이 같음)으로 정의된다. 최소 스패닝 트리(Minimum Spanning Tree, MST)는 스패닝 트리 가운데 모든 간선의 가중치의 합($\sum_{e \in E(T)} w(e)$)이 최소인 것을 의미한다. (최소 스패닝 트리는 여러개가 있을 수도 있다.) 예를 들어, 7개의 정점으로 이루어진 그래프 $G$가 있다고 하자. 이 때, 이 그래프의 MST는 다음과 같다: MST는 다음과 같은 알고리즘을 통해 $O(E \log E)$ 시간에 구할 수 있으며, 이는 Kruskal 알고리즘이라 불린다. 편의상 모든 간선의 가중..
[UCPC 2018 예선 B] 카드 합체 놀이 보호되어 있는 글입니다.
Bayesian Hyperparameter Optimization 겉핥기 Bayesian hyperparameter optimization(베이지안 하이퍼 파라메터 최적화)은 나름 유명한 주제인데, 이를 겉핥기 수준으로 한 번 맛보자. Optimization Problem 베이지안 최적화를 알려면 먼저 최적화가 뭔지를 알아야 한다. 최적화 문제는 함수 $f$와 $f$의 (bounded) domain $X$가 주어졌을 때, $$x^* = \arg\max_{x \in X} f(x)$$ (혹은 $x^* = \arg\min_{x \in X} f(x)$) 를 구하는 문제라고 할 수 있다. 우리가 관심을 두는 대상은 최적화 문제 중에서도 기계학습에서 발생하는 최적화 문제이다. 기계학습에서의 최적화 문제는 대개 다음과 같은 양상을 띈다고 할 수 있다: 함수 $f$는 closed-form을..
Google Hash Code 2020 참가 후기 생애 처음으로 Google Hash Code에 참가했습니다. 저는 import_torch_as_tf 라는 이름의 팀으로 김민철, 김상범 님과 함께 참가했습니다. 최종 26,282,007점이라는 점수로 세계 1,119등, 한국 24등 이라는 다소 저조한 성적을 냈지만, 그래도 나름대로 재밌었습니다. 각 문제에 대해 저희 팀의 풀이를 소개하자면, 다음과 같습니다. 스포일러가 될 수 있으니 주의해주세요! B - read on / 5,822,900 데이터를 살펴보면 sign up time 순으로 출력하면 해결할 수 있음을 알 수 있습니다. C - incunabula / 5,521,060 Library를 sign up time이 작은 순으로 정렬하고, library 안의 책들을 그리디하게 정렬하면 충분한 보상을 ..