1. 문제 구간 A를 1번부터 x번까지, 구간 B를 x+1번부터 y번까지, 구간 C를 y+1번부터 n번까지 나눈다. 각 구간의 모든 원소의 합을 각각 a,b,c라고 하자. a,b,c가 전부 같도록 x,y를 정하자. 여기서 1 그러한 방법의 수가 몇가지일까? n은 최대 50만 배열의 각 원소는 -100만부터 100만까지로 음수일수도 있다. 예를 들어 [1,2,3,0,3]이면.. A가 1번 2번 = 3 B가 3번 = 3 C가 4번 5번 = 3 --------------------------- A가 1번 2번 = 3 B가 3번 4번 = 3 C가 5번 = 3 2가지 있다. 2. 풀이 구간합이니까, prefix sum으로 누적합을 만들어야하는 것은 명확하다 [1,3,6,6,9] n = int(input())..
1. 구조 binary indexed tree는 이름에서부터 2진법 인덱스 구조를 이용해서 구간 합 문제를 효과적으로 처리하기 위한 자료구조 point update, range sum을 효과적으로 처리하기 위한 자료구조 다음 그림이 binary indexed tree의 구조를 잘 보여주고 있다. 1) zero index가 아니라 binary indexed tree에서는 편의상 one index로 바꿔서 생각함 2) 데이터가 N개면 tree의 크기도 N이다. 3) tree의 각 index에는 어떤 값들이 저장되어 있는가? 1번 index에는 0번째 원소 1이 있고, 2번 index에는 0번 + 1번째 원소의 합 1+3 = 4가 저장 마찬가지로 3번 index에는 2번째 원소 11이 저장 4번 index에는..
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. 문제 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 2. 풀이 누적합이야 prefix sum 방법으로 O(N)에 미리 구해놓고 [i,j]의 구간합은 O(1)에 구할 수 있는데 정수 M으로 나누어 떨어지는 구간합 [i,j]를 어떻게 하면 아주 빠르게 구할 수 있을까 가장 쉬운 방법은 모든 i,j에 대해 검사하는 이중 for문 방법이지만 N이 $10^{6}$이다 보니 $O(N^{2})$으로는 1초안에 통과할 수..
1. 문제 1321번: 군인 (acmicpc.net) 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 2. 풀이 문제를 잘 읽어보면 어떻게 풀어야할지 대충 보인다 군인은 군번대로 1번부대부터 차례대로 배치되고, 부대가 4, 3, 7 이렇게 있을때, 군번이 6번인 군인은 2번부대에 배치된다.. 왜냐하면 1번부대에 4번까지 배치하고 5번,6번 군인은 2번 부대에 배치되니까 그런데 부대의 인원이 줄어들거나 늘어날수 있고 그럴때 군인들이 처음부터 다시 배치한다는 것이다 이거는 이제 세그먼트 트리의 업데..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
