1. 문제 29726번: 숏코딩의 왕 브실이 (acmicpc.net) 29726번: 숏코딩의 왕 브실이 숏코딩의 왕 브실이는 오늘도 숏코딩을 한다. 브실이가 제출한 코드 길이가 수열 $A_1, A_2, \cdots, A_N$로 주어진다. 브실이의 행복도는 자신의 코드 길이에 대한 수열에 따라 달라지는데, 현재 수열 www.acmicpc.net 2. 풀이 $$\sum_{i = 1}^{L-1} A_{i+1} - A_{i} = A_{L} - A_{1}$$을 관찰하는 것은 어렵지 않다. 주어진 합은 배열을 알면 양쪽 끝의 두 원소만을 이용해서 구할 수 있다. 이 의미는, $A_{1}, A_{2}, A_{3}, ... , A_{N}$이 주어질때, 중간의 원소 $A_{2}, A_{3}, ... ,A_{N-1}$는 ..
1. 문제 31091번: 거짓말 (acmicpc.net) 31091번: 거짓말 당신 앞에는 $N$명의 사람들이 있다. 각 사람은 자신을 포함하여 몇 명 이상이 거짓말을 하고 있다고 말하거나, 몇 명 이하의 사람이 거짓말을 하고 있다고 말한다. 예를 들어, 각 사람이 다음과 www.acmicpc.net 2. 풀이 K명이 거짓말 한다고 가정하자. K = 0,1,2,3,..,n이다. 각각의 경우에 대하여 실제로 각 사람들의 말과 비교할때 누가 거짓말을 하는지 알 수 있다. 이때, 정말로 거짓말하는 사람 수가 K명으로 일치한다면 그러한 K값은 정답에 포함될 것이다. 예를 들어 2명이 거짓말을 한다고 하면... "1명 이상이 거짓말하고 있다."는 참이다. 실제로 2명이 거짓말하고 있으니까 "1명 이하가 거짓말하고..
D - Cheating Gomoku Narabe (atcoder.jp) D - Cheating Gomoku Narabe AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp . o x로 이루어진 2차원 배열에서 .을 o로 바꿀 수 있다. 이 때 행이나 열로 연속한 o의 개수가 k개가 되도록 최소로 바꾸는 횟수 처음에 DFS로 o의 좌표에서 시작해서 .을 o로 바꿔서 해보다가 당연히 시간초과났고 그러다가 행이나 열 각각에서 모두 조사해보면 된다는 생각이 들었다 여기까지는 좋았음 행 한줄에서 어떻게 .을 o로 바꿔야 연속한 o의 ..
1. 문제 11660번: 구간 합 구하기 5 (acmicpc.net) 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 2. 풀이 좌상단이 (0,0)이고 우하단이 (x,y)인 직사각형내의 모든 원소 합을 dp[y][x]라고 정의한다. 예를 들어 다음 그림을 보면... dp[3][4]는?? dp[3][4] = 1+2+3+4+2+3+4+5+3+4+5+6을 뜻하게 된다. 어떻게 하면 이전에 구해놓은 합을 이용해서 쉽게 구할 수 있을까? 다음과 같이 x = 0 ~ n, y = ..
1. 문제 C - Consecutive (atcoder.jp) C - Consecutive AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 매번 부분 문자열을 찾고, 거기서 연속해서 발생하는 문자의 수를 찾으면 당연히 시간초과가 날 것인데, 주어진 문자열에서 0번부터 어떤 위치 i까지 나타나는 연속해서 발생하는 문자의 개수를 누적합 배열로 미리 구해놓는다 예를 들어 mississippi라고 한다면, count = [0]*(n+1), before = ''으로 초기화해두고, i = 1부터 n까지 순회해서, s[i-..
1. 연속된 자연수의 합 2개의 연속된 자연수를 합해보면.. 1+2 = 3 2+3 = 5 3+4 = 7 4+5 = 9 ... 소수가 나올 수 있는데 3개 이상의 연속된 자연수를 합해보면.. 1+2+3 = 6 2+3+4 = 9 3+4+5 = 12 4+5+6 = 15 ... 일단 소수가 보이질 않는다.. 이게 우연일까? 자연수 x에 대하여 n개의 연속된 자연수의 합은 다음과 같이 나타난다. $$S = x + (x+1) + (x+2) + ... + (x+n-1) = nx + \frac{(n-1)n}{2}$$ 여기서 n이 3이상의 자연수일때, S가 반드시 합성수임을 보이고자 한다. 1) 만약 n이 짝수라면 $n = 2k$ 여기서 k는 2이상의 자연수이다. $$S = 2kx + k(2k-1) = k(2x + 2k..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
