구간합 다른 문제 구간합1 구간합2 10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 🐲접근 (A+B) % C = ((A%C)+(B%C))%C 해당 구간 합의 나머지 연산 값 = 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값 합 배열 S 가 있다고 할 때, S[i] % M == S[j]%M 이면 (S[i] + S[j])%M == 0 : 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[i] 와 S[j] 가 같은 (i,j) 쌍을 찾으..
🏷️CS
구간 합 첫 게시글로 이동하기 11660 👻접근 질의 개수 (M) 이 최대 100,000 이기 때문에 질의마다 합을 구하면 시간 복잡도가 올라가므로 구간 합 배열을 이용해야함. 2차원 구간 합 배열 D[X][Y] 정의 D[X][Y] = 원본 배열의 (0,0) 부터 (X,Y) 까지의 사각형 영역 안에 있는 수의 합 풀이 질의 X1,Y1, X2,Y2 에 대한 답을 구간 합으로 구하는 방법 D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1] 코드 import sys input = sys.stdin.readline N,M = map(int,input().split()) A = [[0] * (N+1)] # 2차원 원본 배열 D = [[0] * (N+1) for _ in..
구간 합 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 합 배열을 구하는 것이 중요 리스트 A 가 있을 때 합 배열 S S[ i ] = A[ 0 ] + A[ 1 ] + A[ 2 ] + ··· + A[ i-1 ] + A[ i ] # A[0] 부터 A[i] 까지의 합 합 배열을 미리 구해 놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1) 로 감소 A[i] 부터 A[j] 까지 리스트 합을 합 배열 없이 구할 경우 최악의 시간 복잡도는 O(N) 이 된다. 합 배열 공식 S[ i ] = S[ i-1 ] + A[ i ] 구간 합 구하는 공식 S[ j ] - S[ i-1 ] # i에서 j까지 구간 합 11659 11659번: 구간 합 구하기 4 첫째..
13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net import sys import math input = sys.stdin.readline test = int(input()) apply = map(int,input().split()) superv, sub_superv = map(int,input().split()) super = 0 for i in apply: i -= superv super += 1 if i > 0 : super += math...
모델링을 하다보며는 다양한 에러사항이 생기는데 그 중 하나가 버전 충돌이었다. 모델별로 요구하는 라이브러리 및 파이썬 버전이 다르기 때문이다. 버전이 다르다고 해서 매번 모델을 돌릴 때마다 버전을 바꿔서 설치하는 것은 매우 비효율적이니 격리된 실행환경, 즉 가상환경을 사용하여 프로젝트를 관리하는 것이 매우 중요하다. 파이썬 가상환경 실행 과정 설명 1. 아나콘다 프롬프트 실행 가상환경 생성하기 conda create -n '가상환경이름' python=3.8 conda prompt 입력 예시 review라는 이름의 가상환경을 파이썬 3.8버전으로 설치 설치가 완료되면 다음과 같이 완료 화면이 뜬다. 가상환경을 활성화 시키고 비활성화시키는 방법이 적혀 있다. conda activate review -> 가상..
