📌 문제 005) 나머지 합 구하기
시간 제한 1초, 골드 III, 백준 10986번
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)
둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)5 3 1 2 3 1 2
출력
첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.
7
1단계 문제 분석
• 구간 합 배열 활용
• 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.
(A + B) % C = ((A % C) + (B % C)) % C
• 구간 합 배열을 이용한 S[j] - S[i]는 원본 리스트의 i+1부터 j까지의 구간 합이다.
• S[j] % M의 값과 S[i] % M 값이 같으면, (S[j] - S[i]) % M은 0이다.
• 즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[j]와 S[i]가 같은 (i, j)쌍을 찾으면 원본 리스트에서 i+1 부터 j까지의 구간 합이 M으로 나누어떨어진다는 것을 알 수 있다.
- 리스트 A의 합 배열 S를 생성한다.
ex) A : [1, 2, 3, 1, 2] / S : [1, 3, 6, 7, 9]- 합 배열 S의 모든 값을 M(3)으로 나머지 연산을 수행해 값을 업데이트한다.
ex) S : [1, 3, 6, 7, 9]
%M 연산 -> S* : [1, 0, 0, 1, 0]- 우선 변경된 합 배열 S* 의 원소 값이 0인 개수만 세어 정답에 더한다. 원소가 0인 것은 원본 리스트 A의 0부터 i까지의 구간 합이 M으로 이미 나누어떨어진다는 뜻이다.
ex) 경우의 수 = +3- 이제 변경된 합 배열 S 에서 원소 값이 같은 인덱스의 개수, 즉, 나머지 값이 같은 합 배열의 개수를 센다. 변경된 합 배열 S 에서 원소 값이 같은 2개의 원소를 뽑는 모든 경우의 수를 구해 경우의 수에 더한다.
ex) 경우의 수 = 3C2 + 2C2
⏩ 총 경우의 수 = 3 + 3 + 1 = 7
2단계 슈도 코드
n 입력받기(수열의 개수)
m 입력받기(나누어떨어져야 하는 수)
A 입력받기(원본 수열 저장 리스트)
S 선언하기(합 배열)
C 선언하기(같은 나머지의 인덱스를 카운트하는 리스트)
answer 선언하기(정답 변수)
for i -> 1 ~ n - 1:
S[i] = S[i-1] + A[i] # 합 배열 저장
for i -> 0 ~ n - 1:
remainder = S[i] % M # 합 배열을 M으로 나눈 나머지 값
if(remainder == 0) 정답을 1 증가
C[remainder]의 값을 1 증가
for i -> 0 ~ m - 1:
C[i](i가 나머지인 인덱스의 개수)에서 2가지를 뽑는 경우의 수를 정답에 더하기
# C[i]개 중 2개를 뽑는 경우의 수 계산 공식 C[i] * (C[i] - 1) / 2
결괏값(answer) 출력3단계 코드 구현
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * n
C = [0] * m
S[0] = A[0]
answer = 0
for i in range(1, n):
S[i] = S[i-1] + A[i] # 합 배열 저장
for i in range(n):
remainder = S[i] % m # 합 배열의 모든 값에 % 연산 수행
if remainder == 0: # 0~i까지의 구간 합 자체가 0일 때 정답에 더하기
answer += 1
C[remainder] += 1 # 나머지가 같은 인덱스의 개수 값 증가시키기
for i in range(m):
# 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수를 더하기
if C[i] > 1:
answer += (C[i] * (C[i] - 1) // 2)
# "/" 연산을 하면 answer 변수가 float 형태가 되어 소수점까지 출력해 오답이 나온다. "//"을 사용해야 한다.
print(answer)03-3 투 포인터
투 포인터는 2개의 포인토로 알고리즘의 시간 복잡도를 최적화한다. 알고리즘이 간단한 편이다.
📌 문제 006) 연속된 자연수의 합 구하기
시간 제한 2초, 실버 V, 백준 2018번
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.
예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.
N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.
입력
1번째 줄에 정수 N이 주어진다.
15 # N
출력
입력된 자연수 N을 연속된 자연수의 합으로 나타내는 가짓수를 출력한다.
4
1단계 문제 분석
[시간 복잡도 분석]
이 문제는 시간 복잡도 분석으로 사용할 알고리즘 범위부터 줄여야 한다. 시간 제한은 2초이다. 그런데 N의 최댓값이 10,000,000으로 매우 크게 잡혀 있다. 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하여 O(n)의 시간 복잡도 알고리즘을 사용해야 한다. 이런 경우 자주 사용하는 방법이 "투 포인터"이다. 연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현한다. 시작과 종료 인덱스를 투 포인터로 지정한 후 문제에 접근한다.
• 입력받은 값을 N에 저장한 후 코드에서 사용할 변수를 모두 초기화한다. 결과 변수 count를 1로 초기화하는 이유는 N이 15일 때, 15만 뽑는 경우의 수를 미리 넣고 초기화했기 때문이다.
• start_index과 end_index를 1에서 시작한다. (1~15까지 이동)
• sum = 1, count = 1도 초기화한다.
• 투 포인터 이동 원칙을 활용해 끝까지 탐색하면서 합이 N이 될 경우의 수를 구한다. start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것과 효과가 같고, end_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한 칸 더 확장하는 의미이다. 같을 때는 경우의 수를 1 증가시키고, end_index를 오른쪽으로 이동시킨다.
[투 포인터 이동 원칙]
• sum > N: sum = sum - start_index; start_index++;
• sum < N: end_index++; sum = sum + end_index;
• sum == N: end_index++; sum = sum + end_index; count++;
• 2단계를 end_index가 N이 될 때까지 반복하되, 포인터가 이동할 때마다 현재의 총합과 N을 비교해 값이 같으면 count를 1만큼 증가시키면 된다.
2단계 슈도 코드
n 변수 저장
사용 변수 초기화(count = 1, start_index = 1, end_index = 1, sum = 1)
while end_index != n:
if sum == n: 경우의 수 증가, end_index 증가, sum값 변경
elif sum > n: sum값 변경, start_index 증가
else: end_index 증가, sum값 변경
경우의 수 출력3단계 코드 구현
n = int(input())
count = 1
start_index = 1
end_index = 1
sum = 1
while end_index != n:
if sum == n: # 정답 케이스
count += 1
end_index += 1
sum += end_index
elif sum > n:
sum -= start_index
start_index += 1
else: # sum < n
end_index += 1
sum += end_index
print(count)