전체 글

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 이 문제를 풀기 전에 DFS 와 BFS 가 뭔지 몰랐기 때문에 이에 대해 검색먼저 했습니다. 0. 그래프 그래프는 간선과 노드로 이루어진 관계도라고 볼 수 있습니다. DFS 와 BFS 는 이 그래프에서 어떤 노드를 찾는 방법들입니다. 1. DFS DFS, 깊이 우선 탐색은 최대한 깊게 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동하며 노드를 찾습니..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제를 보자 사람의 수가 주어지고 각 사람이 인출하는데 걸리는 시간을 다음 줄에 준다. 이때 사람의 순서를 잘 배치하여 각 사람이 돈을 인출하는데 걸리는 시간이 최소가 되는 시간을 계산하면 된다. 각 사람이 인출하는데에 걸리는 시간이 최소가 되려면 어떻게 해야할까? 문제에 주어진 예시를 보자 P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 일 때 최소 시간이 소요되는 순서는 [2, 5, 1, 4, 3] 이..

0. 오버피팅 문제 모델을 한정된 데이터로 학습시키다 보면 모델이 학습 데이터셋에 대한 손실함수가 과하게 작아지는 경우가 생길 수 있습니다. 이런 경우 우리는 모델이 과적합되었다고 합니다. 과적합된 모델은 평가 데이터셋이나 실제 데이터셋에 대해 점수가 낮을 수 있습니다. 과적합 문제를 해결하기 위한 방법으로는 아래의 방법들이 있습니다. 학습 데이터 양을 늘리기 배치 정규화(* Batch Normalization) 모델의 복잡도 줄이기 드롭아웃(* Drop-Out) 가중치 규제(* Weight Regularization) 이들 중 가중치 규제란 모델의 손실 함수값이 너무 작아지지 않도록 특정한 값을 추가하는 방법인데 오늘은 이에 대해 설명하겠습니다. 1. 규제 Regularization 가중치 규제는 모델..

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..