문제 요약 도시 사이의 connection 정보가 input으로 주어집니다. n개의 도시에 대한 connection(edge정보)이 주어지는데, 이는 방향성(directional)이 있습니다. 이중 수도인 capital(0번 도시)로 향하지 않는 방향성을 capital로 향하도록 수정하려고 합니다. 최종 return값은 수정해야 하는 edge의 갯수입...
Overview Hashmap은 Software의 탐색 속도를 개선하는데 활용하게 됩니다. 이때, Hashmap이 어떻게 구현(implementation)되어 있는지 확인해보려 합니다. Source Code import java.io.Serializable import kotlin.collections.* object EmptyIterator ...
Overview Hash를 이용한 자료구조는 Time Complexity를 줄이는데 아주 중요한 역할을 합니다. 여기서는, Hash를 이용한 Data Structure를 소개합니다. 또한, Hash의 Time Complexity는 $O(1)$(insert, delete, search)로 알려져 있는데, 어떻게 이게 가능한지 알아보려 합니다. ...
Computer Engineering을 할때, 개념적인 부분에 대한 이해 없이도 뭔가를 만들어낼 수 있습니다. 하지만 이는 곧 한계에 부딪힙니다. ‘Imperative programming’과 ‘Declarative programming’는 개념으로 들어서는 ‘아하..’하면서 이해는 되지만, 매번 체득되지 않는.. 그런것이었습니다. 도서 ‘Design...
문제 요약 interger로 이루어진 2차원 배열이 주어지는데, 여기서 row 전체와 column전체가 일치하는 경우의 수를 구하는 문제입니다. 문제 풀이 첫번째 시도 Complexity 시간복잡도(time complexity) 는 $O(n^2)$입니다. 여기서 n은 gridmatrix의 1차원(row혹은 column) 크기 입니다. 이는 gri...
문제 요약 interger로 이루어진 2차원 배열이 주어지는데, 여기서 row 전체와 column전체가 일치하는 경우의 수를 구하는 문제입니다. 문제 풀이 첫번째 시도 Complexity 시간복잡도(time complexity) 는 $O(n^2)$입니다. 여기서 n은 gridmatrix의 1차원(row혹은 column) 크기 입니다. 이는 gri...
책 ‘Designing Data-Intensive Applications’을 보면서, 궁금한것들이 많아집니다. 이 책이 2017년 초판이 인쇄 되었는데, 제가 쓰는 기술들에 실제로 적용 되는지 궁금해집니다. 이 글은 그중 하나인, ‘Mongodb(Document db)에서 update는 disk의 rewrite를 발생시키는가?’에 대한 글 입니다. ...
What is XGBoost? Decision Tree의 발전 역사 Decision Trees Bagging(Bootstrap aggregating) sample 데이터를 랜덤으로 선택하여 여러개의 ‘bootstrap’으로 묶고, 이 ‘bootstrap’으로 모델을 학습시키는 방법. sample 데이터의 다양성을 확보하는것. 규칙...
What is Ensemble Learning? 다양한 알고리듬(algorithm)을 결합하여, 개별 알고리듬보다 더 우수한 성능을 만들어내는 방법입니다. 이 자체가 알고리듬은 아니고, 섞는(ensemble) 방법에 관한 얘기입니다. Background(탄생 배경) No Free Lunch Theorem(공짜 점심 같은건 없다.) Ever...
문제 요약 integer array인 nums안에서, k에 해당하는 길이만큼의 요소를 뽑습니다. 이때, 이 요소들의 평균값의 최대를 return합니다. 즉, k길이의 subarray에 대한 average의 최댓값을 구합니다. 문제 풀이 첫번째 시도 Complexity 시간복잡도(time complexity) 는 $O(n)$입니다. 이는 nums를...