13904번: 과제 (acmicpc.net) 과제의 기간 제한이 있고 해당 과제를 수행했을 때 얻는 가치가 서로 다르다 하루에 하나씩 과제만 처리할 수 있다. 주어진 과제들을 적절히 처리해서 최대 가치를 구한다면? --------------------------------------------------------------------------------------------------------------------------- 처음에는 과제 점수가 높은 순서대로 내림차순 정렬해서 현재 날짜랑 비교해서 처리할 수 있는 과제면 일단 가져가고 날짜랑 비교했을 때 처리할 수 없는 과제면.. 지금까지 가져간 과제들 비교해서... 실제 처리할 수 있는지 체크해보는것? 4 604 401 202 503 304 1..
F - Double Sum (atcoder.jp) F - Double SumAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 문제는 매우 간단하다 A1,A2,A3,...,AN이 주어지면, $$\sum_{i = 1}^{n} \sum_{j = i+1}^{n} max(A_{j} - A_{i},0)$$을 구하는 문제 n제한이 40만이라 단순하게 풀면 당연히 시간초과... 1. max(a,b) = (|a-b| + a+b)/2 방법은 많이 있던데 아주 간단하고 경이로운 솔루션이 있어서 복기해본다 배열 A에 대한 함수 f를 다음과 같이..
1. 문제 C - Socks 2 (atcoder.jp) C - Socks 2 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 N쌍의 양말이 있는데, 이 중 지정된 K개의 양말은 각각 1개를 잃어버린 상태이다. 양말의 색을 1,2,3,...,N으로 표시할때, 현재 상태에서 적절하게 짝을 짓는다. 짝지은 양말이 i번째 색, j번째 색일때 |i-j| 의 value를 가진다. 모든 짝의 value합이 최소가 되도록 만든다면? 양말의 개수 2N-K가 짝수라면 상관없지만 홀수라면 1개를 제외하고 짝을 지어야한다. 직관적으..
1. 문제 11497번: 통나무 건너뛰기 (acmicpc.net) 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 2. 풀이 요약하자면 인접한 원소간 차이의 최댓값이 최소가 되도록 배열을 정렬할때, 그 최솟값을 구하는 문제 단순히 크기 순으로 정렬한다고 하더라도.. [a1,a2,a3,...,an]에서 인접한 원소간 차이의 최댓값은 an-a1이므로, 배열의 최댓값과 최솟값의 차이이므로 이것이 최소일리는 없다 만약 크기순으로 정렬한다면, a1 < a2 < a3 < ... < an일때, 이들이 인접했을때, 원소간 ..
1. 문제 D - Square Permutation (atcoder.jp) D - Square Permutation AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 주어진 정수 문자열의 순열이 어떤 정수의 제곱수가 될때, 그러한 순열의 개수를 구하는 문제. 길이 제한이 13이라고 해도 모든 순열을 찾고, 각 순열이 어떤 수의 제곱수인지 검사하면 매우 느리다 1) 만약 길이 N인 s의 순열이 X의 제곱수가 될려면, X는 아무리 커봐야 $\sqrt{10^{N}}$이다. 그러므로 0부터 $\sqrt{10^{N}}$까..
1. border 어떤 문자열의 prefix이면서 동시에 suffix이기도 한 부분문자열을 border라고 부른다. 이 border와 관련된 문제를 해결하는데 z function이 매우 강력하다. z function의 정의에 대해 생각해본다면.. z[i]는 s와 s[i,...,n-1]의 가장 긴 공통 접두사의 길이를 뜻한다 https://deepdata.tistory.com/1000 문자열과 접미사의 가장 긴 공통 접두사의 길이를 찾는 z 알고리즘 배우기 1. z - function 길이 n인 문자열 s에 대하여 z[i]는 s의 i번째 접미사 s[i,i+1,...]과 s와의 최대 공통 접두사의 길이를 말한다 정의에 의하면 z[0]는 s와 s의 최대 공통 접두사의 길이로 s 그 자체의 길이 n deepda..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
