https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net map을 참신하게 활용하는 문제였습니다. 누적합은 $O(N)$에 구할 수 있습니다. 모든 부분합을 구하려고 하면 $O(N^{2})$으로 당연히 시간초과입니다. #include using namespace std; typedef long long ll; int N, K, arr[200001], curSum; ll ans; map m..
https://www.acmicpc.net/problem/30960 30960번: 조별 과제 학번이 $3, 1$인 사람을 한 조로 묶고, $4, 5, 9$인 사람을 한 조로 묶으면 각 조의 어색함은 $(3-1) = 2$와 $(9-4) = 5$이고, 합은 $7$이다. 이 방법이 각 조의 어색함의 합을 최소로 하는 방법이다. www.acmicpc.net 정해는 정렬+누적합이지만, 아이디어가 떠오르지 않아 DP로 해결했습니다. 본 글에선 두 가지 방법 모두 소개합니다. 1. 정렬+누적합 일단 입력받은 배열을 정렬한 상태라고 합시다. 앞에서부터 3명씩 묶을 사람을 정합니다. 맨 처음 3명을 묶을 경우 어색함의 총합은 $(a_{2}-a_{0}) + (a_{4}-a_{3}) + (a_{6}-a_{5})$입니다. 이..
1. 배치 정규화? 앞 절에선 가중치 초기화를 적절히 설정해서 각 층의 활성화값 분포를 적당히 퍼뜨려 원활한 학습을 유도했다. 이와 달리 배치 정규화는 각 층의 활성화값을 적당히 퍼뜨리도록 강제하는 기법이다. 배치 정규화의 장점은 아래와 같다. 학습 속도를 빠르게 한다. 가중치 초깃값에 크게 의존하지 않는다. 오버피팅을 억제한다. 2. 배치 정규화 알고리즘 배치 정규화는 그 이름과 같이, 학습 시 미니배치 단위로 정규화를 한다. 구체적으로는 한 배치안의 값의 분포를 평균이 0, 분산이 1이 되도록 정규화한다. 수식으로는 위와 같다. 이러한 변환을 활성화 함수의 앞 혹은 뒤에 삽입함으로써 데이터 분포가 덜 치우치게 강제한다. 배치 정규화를 활성화 함수의 앞과 뒤 중 어느 쪽에 삽입할 지에 대한 정답은 없다..