본문 바로가기

전체 글

(104)
C# 문자열 백준 문제풀이 (1157, 1316, 2675, 2908, 2941, 5622) 최근 C#을 공부하면서 차근차근 기본문제들을 C#을 이용해서 풀기로 했다. 이번에 푼 챕터는 문자열 관련 챕터이며 새롭게 알게 된 개념부터 몇 개만 소개하고 정답 공유 후 포스팅을 마치겠다. c# 인풋 받기 (input read) string input = ReadLine(); // string 경우 string[] input = ReadLine().Split(); // string split해서 입력받을 경우 int input = int.Parse(ReadLine()); // int 경우 c# 배열 초기화 (array initialization) using System.Linq; int[] freq = Enumerable.Repeat(0, 32).ToArray(); // 32개의 0값을 가지는 배열 생..
머신러닝 알고리즘 정리 (K-NN, SVM) 1. K-NN (K-nearest neighborhood) classification 알고리즘의 일종으로 user가 직접 정의하는 parameter인 K에 따라 데이터들 간의 거리를 기반으로 가까운 K개의 데이터들의 투표를 통해 분류를 진행한다. 이 때, k는 sqrt(n)보다 작은 값으로 정하며, 너무 작을 시에는 noise가 심하고(variance가 커서 신뢰도가 떨어짐), 너무 클 경우에는 다른 클래스의 데이터가 포함될 가능성이 크므로(bias가 커지므로 부정확해 질 수 있음) k를 잘 정하는 것이 중요하다. 데이터들 간의 거리는 Euclidean, Manhattan, Minkowski, correlation 등 다양한 거리 계산 방법을 활용할 수 있으며, 사전지식이나 cross-validation..
머신러닝 알고리즘 정리 (Decision Tree, Random Forest) 1. Decision Tree (결정 트리) Rull based prediction model로 Tree구조로 각 노드에서 binary 혹은 multi-way의 조건을 체크하면서 모든 응답이 거의 같은 값을 가리킬 때 까지 leaf node로 classification 혹은 regression을 하는 머신러닝 기법이다. 쉽게 설명하면 스무고개를 통해 원래 데이터가 어디에 속하는 지 알아나가는 과정이라고도 볼 수 있다. 각 노드에 질문을 통해 분류되는 클래스들은 homogenous(같은 클래스의 비중이 높을수록)할수록 좋다. 예를 들면 어떤 질문을 통해 5:5로 나누어지는 것 보다는 9:1로 나눌 수 있는 것이 좋다는 것이다. 다시 말해 각 영역의 순도(homogeneity)가 높을 수록, 불순성(Node..
머신러닝 알고리즘 정리 (PCA, LDA) 1. PCA (Principal Component Analysis) Unsupervised learning의 일종으로, independent variable들 사이에 correlation을 없애고, 숨은 latent variable을 찾아내거나, 노이즈(noise)를 줄일 때 사용한다. PCA를 돌린 후 나오는 값들은 다음의 의미를 가진다. PC(eigenvector) : 기존 변수들로 이루어진 선형 벡터이며, 기존의 변수들을 설명한다. PC loadings: 기존 변수들과 PC사이의 correlation 값으로, 해당 PC로 기존의 변수들을 얼마나 잘 설명하는 지 percentage로 보여준다. PC score: 각각의 PC에 대해서 재 생성된 observation data들이다. (latent var..
머신러닝 알고리즘 정리 (Linear regression, Logistic regression) 0. Supervised vs Unsupervised Learning 간단히 말해 labeled data, 즉 타겟 변수(target variable)의 존재유무로 판단한다. 0-1. Supervised Learning labeled data가 존재하여, 정답을 알려주면서 training set를 이용하여 학습한 후, test set이나 inner validation을 통해 알고리즘 별 적합한 score를 계산하여 성능을 비교하는 것. ex) Linear regression, Logistic regression, Linear discriminant analysis(LDA), Decision Tree, Random Forest, K nearest neighborhood(K-NN), Supprot vecto..
Z-test, T-test, Paired T-test, ANOVA test 비교 기본 개념 정리. The Central Limit Theorem(중심 극한 정리) 만약, y1...yn이 i.i.d(independent, identically distributed), E(yi)=u, Var(yi) = sigma^(2)이고, x = y1+y2+...yn일 때, Zn = (x-n*u)/sqrt(n*sigma^(2)) = (x/n - u)/sqrt(sigma^(2)/n)은 n이 무한으로 발산할 때 정규분포를 따른다. (표본이 커질수록, 표본 평균의 분포는 모집단의 분포와는 상관없이 정규분포에 가까워진다. 이때, 표본 평균의 평균은 u이고, 분산은 모분산에 n을 나눈 것과 같다.) Chi-분포 만약, Z1...Zk가 independent random variable이며 정규분포를 따를 때, ..
MongoDB 유용한 명령어 정리. Mongo DB 설치 링크 https://www.mongodb.com/download-center/community?jmp=homepage Download Center: Community Server Download MongoDB Community Server, the most popular non-relational database built to address the needs of modern applications. www.mongodb.com 서버 실행 및 접속 mongod: mongo DB 서버 실행 mongo: 클라이언트로 서버에 접속 mongo DB 용어 정리 Document: data element {key:value} 쌍 Collections: Document의 집합 Database: ..
백준 2805번 나무자르기 _ 이분탐색 (python) 문제: https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net 이번 포스팅에서 다루게 된 2805번 나무자르기 문제는 이분탐색을 이용해야하는 전형적인 문제입니다. N은 100만 M은 20억..