7265번: Herbamedžiai (acmicpc.net) 배열에서 i번째 원소를 선택하면 i-1번째, i+1번째 원소는 선택할 수 없을때, 선택할 수 있는 원소의 최대 합을 구한다면 n이 최대 10만이라 O(N)에는 해결해줘야한다 $O(N^{2})$ 아니면 못할것 같지만 놀랍게도 O(N)에 되더라고 DP[i] = i번째 원소까지 봤을때 선택한 원소들의 최대합 만약 i번째 원소를 선택하지 않는다면? dp[i] = dp[i-1]로 그대로 가져오면 된다 만약 i번째 원소를 선택한다면? i-1번째 원소는 선택할 수 없으므로, dp[i-2]에다가 i번째 원소 선택 A[i]를 더해주면 된다 dp[i] = dp[i-2] + A[i] 여기서 둘 중 더 큰 값을 고르면 된다 dp[i] = max(dp[i-1], d..
19355번: A Really Odd Sequence (acmicpc.net) 주어진 배열에서 길이가 홀수인 연속 부분 배열의 원소 합 중 가장 큰 값을 구하는 문제 https://deepdata.tistory.com/390 다이나믹 프로그래밍 - Kadane algorithm1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거deepdata.tistory.com 카데인 알고리즘의 연장선상이긴 한데 문제는 홀수 길이여야한다는 것... 카데인 알고리즘은 배열의 길이를 모른다.. 길이 정보를 담자니...
D - Intersecting Intervals (atcoder.jp) D - Intersecting IntervalsAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 50만개의 구간 [l,r]이 주어질때, 이들 중 서로 겹치는 구간 쌍의 개수가 몇개인지 구하는 문제 모든 구간 쌍에 대해 서로 겹치는지 조사할려면 $O(N^{2})$인데, 당연히 N이 최대 50만이므로 시간제한에 맞지 않는다 전체 구간 쌍의 개수는 n개중 2개를 선택하는 경우의 수이므로, nC2 = n(n-1)/2 만약 서로 겹치치 않는 구간 쌍의 개수를 구..
1. 어떻게 남녀를 맺어줘야 행복하게 살수 있을까? 결혼중매업자인 대혁에게는 200명의 고객이 있다. 100명은 남자, 100명은 여자이다. 여자 고객은 각자 남자 고객 100명을 대상으로 선호도에 따라 순위를 매겨 대혁에게 제출한다. 각자 명단의 맨 위에는 완벽한 이상형이 있고, 아래로 갈수록 호감도가 떨어져 맨 아래에는 최악의 기피남이 있다. 남자 고객 100명도 마찬가지로 여자 고객 100명을 대상으로 순위를 매겨 제출한다 대혁은 이 선호도 조사 결과를 바탕으로 남녀 고객을 맺어줘야한다. 어떻게 맺어줘야 이들이 결혼에 골인하고 가정을 이루고 오래오래 행복하게 살 수 있을까? 당연한 말이지만, 일부는 자신의 제1지망과 맺어지지 못한다. 같은 남자를 여러 여자가 제1지망으로 찍었다면 누군가는 고배를 ..
E - Maximum Glutton (atcoder.jp) E - Maximum GluttonAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 단맛이 a 짠맛이 b로 주어지는 n개의 음식을 먹는데 단맛이 x를 초과하거나 짠맛이 y를 초과하는 순간 음식을 그만 먹는다면 음식을 최대한 많이 먹고자할때, 최대로 먹을 수 있는 음식의 수는? 전형적인 배낭 문제라서 dp[i][j][k] = i번째 음식까지 먹었을때 단맛의 합이 j, 짠맛의 합이 k인 경우 먹은 최대 음식의 수로 하면 될것 같다고 생각을 했는데 n이 80이고 a가 ..
28828번: Упражнения в умножении (acmicpc.net) $\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}}$과 $10^{6}$ 이하로 차이나는 정수를 구하는 문제 n,m이 $10^{5}$까지이고, $a_{i}, b_{i}$가 $10^{9}$이라 단순하게 곱하고 나누면 시간초과가 난다 v1 = 1for i in range(n): v1 *= A[i]v2 = 1for j in range(m): v2 *= B[j]print(v1//v2) 곱셈을 덧셈으로 바꾸는 대표적인 방법이 로그를 취하는 것이다 $\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}} = X$라고 하면 $$logX = log(a_{..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
