전체 글

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP 를 안다면 풀 수 있는 문제였다. DP 의 핵심은 이전에 계산했던 것을 다시 활용하는 것이다. 처음에는 DP를 생각하지 못했다. N 의 크기 때문에 N 이 주어졌을 때 가능한 모든 경우의 수를 계산 해보는 식의 방법은 안될 것 같다고 생각했고, 그러면 일종의 알고리즘을 만들어서 해결해봐야겠다고 생각했다. 문제를 보자 임의의 정수 X에 대해 X가 1이 되도록 만드는 최소 횟수를 찾는것이다. 처음에는 간단하게 생각했다. 어떤 수가 나오든 대응할 수 있는 로직을 생각해봤다. 이를 바탕으로 연산의 우선순위를 생각..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 어려웠다. 당연히 재귀함수를 이용하여 풀면 시간초과가 난다. DP 라는걸 처음 알게되었다. 동적 프로그래밍인데, 이 전의 작업을 다시 사용할 수 있을 때 생각해낼 수 있다. 예를 들어 피보나치 수열의 경우 평범한 Recursion 을 이용한다면 수가 많이 커지는 경우 스택 오버플로우가 날 수 있다. 하지만 DP 를 사용한다면 다르다. 피보나치 수열을 점화식으로 나타내면 n=0) F(x) = 0 n=1) F(x) = 1 n>1) F(x) = F(x-1) + F(x-2) 이다. 만약 아주 큰 자연..

1. 라소 (Lasso) 확장된 보스턴 주택가격 데이터셋에 라소를 적용해보겠습니다. from sklearn.linear_model import Lasso lasso = Lasso().fit(X_train, y_train) print("훈련 세트 점수 : {:.2f}".format(lasso.score(X_train, y_train))) print("테스트 세트 점수 : {:.2f}".format(lasso.score(X_test, y_test))) print("사용한 특성의 개수 : ", np.sum(lasso.coef_ != 0)) # lasso.coef_ != 0 을 하면 0이 아닌 값은 true, 0인 값은 false 인 np 1차원 배열이 생성 # bool 값의 1차원 배열의 sum 은 true ..

https://www.acmicpc.net/problem/25305 25305번: 커트라인 시험 응시자들 가운데 1등은 100점, 2등은 98점, 3등은 93점이다. 2등까지 상을 받으므로 커트라인은 98점이다. www.acmicpc.net 정렬을 하는 방법이 이 문제의 핵심이다. 내림차순으로 정렬하고, (상을 받는 사람의 수) - 1 에 해당하는 index 인 값을 출력하면 된다. 하지만 Collections.sort() 의 기본 정렬방식은 오름차순이다. 3가지 방법이 있다. Collections.reverseOrder() 사용하기 Comparator 만들어서 사용하기 람다 함수 이용하기 1. Collections.reverseOrder() 사용하기 import java.io.*; import java..

https://www.acmicpc.net/problem/2587 2587번: 대표값2 어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30의 평균은 (10 + 40 + 30 + 60 + www.acmicpc.net 평균은 값을 받을 때마다 sum 에 넣어주고 마지막에 /5 를 하면 구해진다. 중간값은 모든 값들을 list 에 담아주고 정렬을 한 다음에 index = 2 인 값을 출력하면 된다. n=5 이니 최악의 경우 O(n^2) 인 정렬 알고리즘도 상관없이 sort 하며 된다. import java.io.*; import java.util.ArrayList; impor..

https://www.acmicpc.net/problem/19532 19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net 브루트 포스를 이용하면 간단하다. n = 2000 이고 for 반복문을 두 번 돌면 O(n^2) 이니 시간초과는 걱정하지 않아도 된다. 그냥 x 와 y 를 -999 부터 999 까지 돌리자. import java.io.*; import java.util.StringTokenizer; publi..

1. 리지 회귀 (Ridge Regression) 리지 (Ridge) 도 회귀를 위한 선형 모델이므로 최소적합법에서 사용한 것과 같은 예측 함수를 사용합니다. 하지만 리지 회귀에서의 가중치 (w) 선택은 훈련 데이터를 잘 예측하기 위해서 뿐만 아니라 추가 제약 조건을 만족시키기 위한 목적도 있습니다. (* 앞서 말한 과소적합과 과대적합 사이를 세밀하게 조정할 수 있을듯) 가중치의 절댓값을 가능한 한 작게 만드는 것입니다. 다시 말해서 w의 모든 원소가 0에 가깝게 되길 원합니다. 직관적으로 생각하면 이는 모든 특성이 출력에 주는 영향을 최소한으로 만듭니다(* 기울기를 작게 만듭니다). 이런 제약을 규제(Regularization) 라고 합니다. 규제란 과대적합이 되지 않도록 모델을 강제로 제한한다는 의미..

1. K-NN Regression k-최근접 이웃 알고리즘은 회귀 분석에도 쓰입니다. mglearn.plots.plot_knn_regression(n_neighbors = 1) 을 통해 그림으로 확인 할 수 있고, n_neighbors 의 값을 바꿔서도 확인할 수 있습니다. 여러개의 최근접 이웃을 사용할 땐 이웃 간의 평균이 예측값이 됩니다. 회귀를 위한 k-최근접 이웃 알고리즘은 KNeighborsRegression 에 구현되어 있고, 사용법은 비슷합니다. from sklearn.neighbors import KNeighborsRegressor X, y = mglearn.datasets.make_wave(n_samples=40) # 데이터 받기 # wave 데이터셋을 훈련 세트와 테스트 세트로 나눕니다..