03-2. 구간 합

문제 3

구간 합 구하기 1 ( 백준 실버 3 / 11659번 )

일반적으로 input()으로 입력 받으면 가끔 시간 초과가 나는 경우가 있다. 이 둘은 기능상으로는 큰 차이가 없지만, 속도 차이가 크다.
그래서 input으로 작업한 코드가 시간 초과가 났을 때, sys 입력으로 변경해주면 정답처리가 될 확률이 있다.

import sys
input = sys.stdin.readline

이렇게 맨위에 input을 sys.stdin.readline 으로 받아주면 좋다.

import sys
input = sys.stdin.readline

suNo, quizNo = map(int, input().split())
numbers = list(map(int, input().split()))
prefix_sum = [0]
temp = 0

for i in numbers:
    temp += i
    prefix_sum.append(temp)         # 합 배열 만들기
    
for i in range(quizNo):
    s, e = map(int, input().split())
    print(prefix_sum[e] - prefix_sum[s-1])

이 문제는 0번째 인덱스 값은 0으로 시작하여 총 6개의 인덱스의 구간 합을 구하는 문제다. 궁금한 점은 처음 0번째 리스트 값은 신경을 안쓰고 "append()"하게 되면 0번째는 신경을 안 쓰는데 이렇게 해도 상관은 없겠지만 다른 방법으로 할 수 있지 않을까 의문이 든다.

문제 4

구간 합 구하기 2 ( 백준 실버 1 / 11660번 )

import sys
input = sys.stdin.readline

n, m = map(int, input().split())             # n: 리스트 크기, m: 질문 수
A = [[0] * (n+1)]                            # 원본 리스트
D = [[0] * (n+1) for _ in range(n+1)]        # 합 배열

for i in range(n):
    A_row = [0] + [int(x) for x in input().split()]
    A.append(A_row)

for i in range(1, n+1):
    for j in range(1, n+1):
        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
        
for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
    print(result)

답은 위와 같고 내가 새롭게 알게된 내용과 중요하다고 느낀 것을 정리하면 다음과 같다.

for _ in range(x)

위와 같은 _ (언더스코어, underscore)를 사용하는 이유는 아래와 같다.

1. 인터프리터(Interpreter)에서 마지막 값을 저장할 때
2. 값을 무시하고 싶을 때 (흔히 “I don’t care”라고 부른다.
3. 변수나 함수명에 특별한 의미 또는 기능을 부여하고자 할 때
4. 국제화(Internationalization, i18n)/지역화(Localization, l10n) 함수로써 사용할 때
5. 숫자 리터럴값의 자릿수 구분을 위한 구분자로써 사용할 때

A_row = [0] + [int(x) for x in input().split()]
    A.append(A_row)
# 입력받은 행 값을 띄어쓰기로 나누어 int형으로 변환 후 A_row = [0,-,-,...]에 추가 함
# A_row값을 A에 추가하여 N차원 원본 배열을 만듬

구간 배열의 합 공식은 아래와 같다.

for i in range(1, n+1):
    for j in range(1, n+1):
        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
# 배열의 합 계산 식

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
    print(result)
# 질문에 대한 계산 식

문제 5

나머지 합 구하기 ( 백준 골드 3 / 10986번 )

1. 먼저 리스트 array의 합 배열 sum_array을 생성한다.
2. 합 배열 sum_array를 각각 m으로 나눈 후 나머지가 0이면 처음부터 더했을 때 m으로 나누어 떨어지는 것이니 정답 개수에 더해준다.
3. 만약 나머지가 0이 아닌 다른 수 들은 몇개 인지 세어서 count변수에 나머지가 같은 인덱스의 개수를 센다. ( count[remainder] +=1 )
4. 나머지가 같은 인덱스 중에 2개를 뽑아야 하니 nC_2 콤비네이션 공식을 사용하여 정답 개수를 구한다.

여기서 핵심 아이디어는 나머지가 같은 수 들의 구간 합들은 (sum_array[i] -sum_array[j]) % m 을 해도 나머지는 같다는 사실이다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())             # n: 수열 개수, m: 나누는 수
array = list(map(int, input().split()))      # A: 원본 수열 리스트 저장
sum_array = [0] * n
count = [0] * m                              # 같은 나머지의 인덱스를 카운트하는 리스트
sum_array[0] = array[0]         
answer = 0

for i in range(1, n):
    sum_array[i] = sum_array[i-1] + array[i]

for i in range(n):
    remainder = sum_array[i] % m
    if remainder == 0:
        answer += 1
    count[remainder] +=1 

for i in range(m):
    if count[i] > 1:
        answer += (count[i] * (count[i] - 1) // 2)

print(answer)

03-3장. 투 포인터

문제 6

연속된 자연수의 합 구하기 ( 백준 실버5 / 2018번 )

start_index와 end_index 두 개의 포인터를 이용해서 구하는 문제이다.

• 먼저 count = 1로 주고 시작하는데 이유로는 N이 15일 때 숫자 15만 뽑는 경우의 수를 미리 넣고 초기화 해주는 것이다

start와 end 포인터 이동 규칙은 다음과 같다.

• 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++;

n = int(input())

count = 1                     # 기본적인 최종 값 하나는 포함되기 때문에 1부터 시작
start_index = 1
end_index = 1   
sum = 1                       # 인덱스 처음은 1부터 시작

while end_index != n:
    if sum == n:              # 합이 n과 같은 경우
        end_index += 1
        sum += end_index
        count += 1
    elif sum > n:             # 합이 n보다 큰 경우
        sum -= start_index
        start_index += 1
    else:                     # 합이 n보다 작은 경우
        end_index += 1
        sum += end_index

print(count)

문제 7

주몽의 명령 ( 백준 실버 4 / 1940번 )

마찬가지로 두개의 포인터를 가지고 푸는 문제이다. 여기서는 먼저 인덱스를 정렬해주기 위해 python에 내장되어 있는 sort() 함수를 사용한다.
또한 포인터 i와 j를 양쪽 끝부터 시작하여 포인터 이동 규칙을 따른다.

투 포인터 이동 규칙은 다음과 같다.

• A[i] + A[j] < M: i++;
• A[i] + A[j] > M: j--;
• A[i] + A[j] > M: i++; j--; count++;

N = int(input())
M = int(input())
A = list(map(int, input().split()))

i = 0                               # 시작 인덱스
j = N - 1                           # 마지막 인덱스
count = 0                           # 정답 개수

A.sort()                            # 리스트 자동 정렬

while i<j:
    if A[i] + A[j] < M:
        i += 1
    elif A[i] + A[j] > M:
        j -= 1
    else:
        i += 1
        j -= 1
        count += 1

print(count)

문제 8

'좋은 수' 구하기 ( 골드 5 / 1253번 )

이 문제도 마찬가지로 리스트를 입력받고 sort()함수로 자동정렬을 시킨다.
두개의 포인터 i, j도 배열의 양 끝에 위치 시킨 후 이동 규칙을 따른다. i, j가 우리가 구할 수인 인덱스 k의 result값과 같으면 안된다.

이동 규칙은 다음과 같다.

- arr[i] + arr[j] == result:
	 if i와 j가 k와 모두 다름:
     	count++;
        반복문 종료
     if i == k: i++;
     if j == k: j--;
- arr[i] + arr[j] < result:
	i++;
- arr[i] + arr[j] > result:
	j--;

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
arr.sort()

count = 0

for k in range(N):
    result = arr[k]
    i = 0
    j = N - 1
    while i < j:
        if arr[i] + arr[j] == result:       
            if i != k and j != k:               # i, j가 모두 k가 아닐 때 count 증가 및 while문 종료
                count += 1
                break
            elif i == k:                        # i가 k랑 같은 경우 i 값 증가
                i += 1
            elif j == k:                        # j가 k랑 같은 경우 j 값 감소
                j -= 1
        elif arr[i] + arr[j] < result:
            i += 1
        else:
            j -= 1

print(count)