Overview 트리 자료구조는 데이터를 효율적으로 저장하고, 빠른 시간에 탐색, 수정 및 추가 삭제 연산을 진행할 수 있도록 도와줍니다. 구간 트리(Segment Tree)는 이 트리 구조의 이점을 살려서 특정 구간에서의 최대, 최소 값등을 빠르게 구할 수 있도록 합니다. 구간 트리는 특히 일차원 배열의 특정 구간에 대한 질문들(최대, 최소값 등)을 빠르게 대답하는 데에 주로 사용합니다. 예를 들어, 일차원 배열의 특정 구간에서 최대인 값을 찾기 위해서는 특정 구간을 일일이 순회하면서 최소값을 찾아야 했습니다. 하지만, 구간 트리를 이용하면 특정 구간의 최대값을 미리 전처리해서 부모 노드에 저장하는 방식을 취하기 때문에 (일종의 다이나믹 프로그래밍 방법이라고도 할 수 있습니다.) 훨씬 더 빠른 시간에 ..

풀이 펜윅 트리로 검색해서 들어갔던 문제이기 때문에 어떻게든 펜윅 트리를 사용해서 풀어야 한다는 강박관념이 있었던 문제였습니다. 펜윅트리는 저번 포스팅에서도 간략하게 설명했지만 구간합을 빠르게 구하기 위해 사용되는 알고리즘입니다. 따라서 문제의 핵심은 특정 영화의 앞에 놓여있는 영화의 개수를 어떻게 구간합으로 표현할 것인가?입니다. 1. 영화는 한번의 시행때마다 그 위치가 움직이므로 위치의 변동을 표현할 수 있어야 한다. 2. 펜윅 트리는 구간의 합을 빠르게 구할 수 있는 자료구조이므로, 구간의 합을 영화 앞에 쌓여 있는 영화의 개수로 치환할 수 있어야 한다. 3. 영화의 위치가 변했을 때, 트리를 업데이트하기가 용이해야 한다. 위 생각을 적용해볼 때, n+m의 크기를 갖는 펜윅 트리를 구성하고, 특정 ..

풀이 stable sort를 통해 구현한다면 쉽게 해결할 수 있는 문제이다. Stable Sort란 정렬 알고리즘의 종류가 아닌 알고리즘의 정렬 방식에 관한 것으로 동일한 키 값을 가진 원소들에 대하여 정렬하기 전과 정렬하기 후의 value가 같은 순서를 가지도록 정렬하는 방식을 의미한다. 예를 들어 [key, value] 쌍을 갖는 객체들이 다음과 같이 나열되어 있다고 하자 [3, "철수"] [2, "영희"] [1, "훈이"] [2, "맹구"], [2,"뚱이] key값에 대하여 위 객체들을 오름차순으로 정렬한다고 할 때, Stable Sort는 객체들을 다음과 같이 정렬한다. [1, "훈이"] [2, "영희"] [2, "맹구"] [2, "뚱이"] [3, "철수"] 즉, key 값이 동일한 경우 정렬되기..

* 첨부된 자료의 모든 저작권은 COURSERA에 있음을 미리 밝힙니다. Learning Curves 이번 시간에는 머신 러닝 알고리즘이 데이터를 가지고 학습을 할 때에 얼마만큼의 에러를 발생시키는지를 알아보는 Learning Curve(학습 곡선)에 대해 알아보려고 한다. 머신 러닝 알고리즘을 적은 개수의 데이터로 훈련시키게 되면, (예를 들어 1개, 2개, 3개)Training Set의 데이터에 대해서 알고리즘은 Error 값이 0 인 Quadratic Curve h를 예측해 낼 수 있다.하지만 이 에러는 Training Set에만 해당되는 값이므로 Test Set이나 Cross-Validation Set의데이터에 대해서는 굉장히 큰 오류를 일으킬 수 있다. 같은 원리로, Training Set의 크..

* 첨부된 자료의 모든 저작권은 COURSERA에 있음을 미리 밝힙니다. Dimensionality Reduction - Data Compression & PCA 이번에는 주어진 데이터셋의 차원을 낮추는 Data Compression과 그 일종인 PCA에 대해서 알아보고자 한다. 고차원의 데이터에서는 관측단계도 기하급수적으로 증가하고메모리도 굉장히 많이 차지하기 때문에 많은 문제점이 발생하게 된다.즉, 차원이 증가하면 이를 표현하기 위한 데이터의 양이 기하급수적으로 증가한다는 것이다. 따라서 기계학습을 시키기 위해서는 이 데이터의 차원을 축소하여 다룰 필요가 생기는데, 이를 차원 축소(DImensionality Reduction)라 한다. 차원 축소의 의미는 바로 "데이터의 의미를 잘 표현하는 특징을 추..

* 첨부된 자료의 모든 저작권은 COURSERA에 있음을 미리 밝힙니다 Unsupervised Learning- K means Algorithm 지금까지 살펴본 기계학습 방법들은, (크게는 Linear Regression과 Logistic Regression을 사용한 분류 방법부터 좀더 구체적으로는 Linear Regression, One vs One, One vs All 까지) 모두 지도학습 (Supervised Learning) 을 통해 데이터를 훈련시켰다. Supervised Learning 이란 데이터셋을 제공할 때 이 데이터 셋이 출력해야 하는 결과값(y)까지 제공하는 것으로주어진 데이터를 훈련시켜 알고리즘이 어떤 결과를 가져와야 하는지를 알려주는 훈련 방법이다. 예를 들면 위 그림과 같다. x..