#3. 구간 합 구하기 1

문제 분석

• 수의 개수: 최대 100000 x 합을 구하는 개수: 최대 100000
  • 구간마다 합을 구하는 경우 최악의 경우 $10^5$번의 연산을 필요로 함 → 시간 초과!

⇒ 구간 합 개념을 활용해 보자!

손으로 풀기

Pseudo code

Input> n(데이터 개수), m(질의 수)
Input> numbers에 숫자 저장

S[0] = 0 # prefix 지정

# 합 배열 만들어주기
for 1 이상 (n+1) 미만:
	S[i] = S[i-1] + numbers[i-1] 
	
m번 반복:
	Input> i(시작), j(끝)
	print(S[j] - S[i-1]) # 구간 합 출력

Implementation

## 입력
n, m = map(int, input().split()) # 데이터의 개수, 질의 개수
numbers = list(map(int, input().split())) # 숫자 저장

## 처리
S = [0] # 리스트 선언 및 prefix 선언

# 합 배열 만들어주기
for i in range(1, n+1):
    num_total = S[i-1] + numbers[i-1]
    S.append(num_total)

## 출력
# m번 반복
for k in range(m):
    i,j = map(int, input().split()) # 시작, 끝
    print(S[j] - S[i-1])

(채점 시 Pypy3로 언어 설정해야 채점됨,,)

#8. 투 포인터 - ‘좋은 수’ 구하기

문제 분석

• 시간 복잡도: 2초

  • 1초에 2000만 번 계산한다 가정 → 최대 4000만번 계산

  • 1 ≤ N ≤ 2000 → 최악의 경우 좋은 수 하나를 찾는 데 $2000^3$의 시간 복잡도

    • 두 수의 합 구하기: $N \times (N-1)$ → $O(N^2)$
    • 리스트 내에 두 수의 합과 일치하는 수가 있는지 탐색: $(N-2)$

    ⇒ 전체: $O(N^3)$, 시간 초과!

  • 따라서, 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 $O(n\log n)$을 넘어가서는 안됨

• 방법: 투 포인터 활용
  • 이때, 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 x
    • 좋은 수: 다른 두 수의 합으로 표현

손으로 풀기

1. 입력된 수 정렬
2. 투 포인터 이동 원칙
   • 투 포인터를 배열 양끝에 위치시킨 후 탐색 수행
   • 판별의 대상이 되는 수: K