문제 n개의 1차원 숫자 배열이 주어졌을 때, 연속된 부분합이 m으로 나누어 떨어지는 경우의 수를 구하는 문제이다. 풀이 부분합을 m으로 나누었을 때 나누어 떨어지는지가 문제임으로 나머지끼리의 연산을 통해 문제를 풀 수 있다. 특히 1차원 부분합은 누적합의 뺄셈을 통해 구할 수 있음으로 $ partSum = prefixSum[j] - prefixSum[i]$ $( i < j ) $ 나머지가 같은 누적합의 뺄셈 계산을 통해 m으로 나눈 나머지가 0이 되는 부분합을 구할 수 있다. 부분합을 구할 때는 항상 뒤에 위치한 j번째 누적합에 i번째 누적합을 빼야한다. (i < j) 즉, 나머지의 수가 같은 누적합의 조합을 통해 나머지가 0이 되는 부분합의 경우의 수를 구할 수 있다. $_nC_2 = \frac{n ..
문제 10000 이하의 자연수로 이루어진 n 길이의 수열에서 부분합이 s 이상이 되는 것 중 최소 길이를 구하는 문제이다. 풀이 이 문제는 1차원 배열의 부분합을 구하여 크기를 비교하고 최소 길이를 구하면 된다. 누적합을 구하면서 해당 위치 이전까지의 부분합 중 s 이상인 경우, 최소 길이를 업데이트한다. 예를 들어 4번째 칸까지 누적합을 구했을 때, s 가 7이라면 최소 길이는 3이 된다. 알고리즘 누적합을 담을 dp list를 n+1 길이로 생성한다. 최소 길이를 담을 ans 변수를 생성한다. for 문을 n 번 돌면서 누적합을 계산한다. 최소 길이에 맞춰 부분합을 계산하고 만약 부분합이 s 보다 작다면 이후에도 더 작을 것임으로 중단해준다. 만약 s보다 크다면 최소 길이를 줄일 수 있다는 의미임으로..
배열의 일부 구간에 대한 합을 빠르게 구할 수 있는 알고리즘이다. 배열의 값들이 변하지 않는다면 누적된 합 또한 변동이 없다는 점을 적용한다. 미리 구해둔 누적합을 통해 배열 중 특정 구간의 부분합을 쉽게 구할 수 있다. 값을 미리 저장해 두는 점이 DP와 유사하다. 배열의 값들이 변하지 않음 1. 1차원 누적합 알고리즘 1.1. 1차원 누적합 그림과 같이 앞에서부터 차례대로 누적된 합계를 prefixSum 배열에 저장한다. 첫 번째(0) 값은 arr 값과 prefixSum 값이 동일하다. 현재 위치(i)의 arr 값에 prefixSum 배열에 저장된 직전 위치(i-1)까지의 합을 더하여 현재 위치의 누적합을 구하여 prefixSum에 입력한다. 점화식은 다음과 같다. prefixS..
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- 분리집합
- 수학
- python
- 누적합
- COLAB
- Look-ahead Mask
- DP
- lis
- 우선순위큐
- 이분 그래프
- 파이썬
- 코딩테스트실력진단
- 구현
- 코드트리
- bipartite graph
- pytorch
- Transformer
- 알고리즘
- dfs
- Prefix sum
- 백준
- Algorithm
- 1202
- 이분탐색
- 트랜스포머
- padding mask
- boj
- 그리디
- greedy
- disjoint set