에라토스테네스의 체(소수 판정)

• 주의점
  : 특정 수가 소수인지 판별하는 문제가 아닌, 특정 범위의 소수를 판별할 때 사용한다.

• 장점
  : 일일이 모든 수에 대해 소수 판별을 하는 방법(O(n^2))에 비해 시간 복잡도를 O(n)으로 크게 줄일 수 있다.

• 주로 사용하는 문제
  : 특정 범위 내의 모든 소수를 구해야 하는 문제

Idea

1. 1~N까지의 소수판별을 위한 배열 생성

2. 2부터 N까지 훑으며 아직 판별을 하지 않은 곳에 대해 그 배수들을 판별함

(백준1664 (소수의 연속합) 주요코드)

prime_find = [True] * (N + 1)
prime_find[0] = False
prime_find[1] = False

for i in range(2, N):
  if prime_find[i] == True:
  	# j=1인 부분은 소수이므로 제외한다
    j = 2
    while(i * j) <= N:
      prime_find[i * j] = False
      j += 1

슬라이딩 윈도우(투 포인터)

• 주의점
  : 사용 가능한 문제가 한정적임

• 장점
  : 사용 조건에 맞을 때 시간 복잡도 단축에 효과적임

• 주로 사용하는 문제
  : 어떤 배열의 특정 구간을 지속적으로 관측하는 문제

Idea

1. 구간의 정보를 함축하는 변수(혹은 hash map) 생성

2. 관측 구간을 바꿔가며 해당 변수(hash map)의 정보를 변경

(백준15961번 (회전 초밥) 주요코드)

suisi_num = Counter(suisi[:k])

for start in range(N):
  suisi_num[suisi[start]] -= 1
  if suisi_num[suisi[start]] == 0:
    cnt -= 1

  suisi_num[suisi[start + k]] += 1
  if suisi_num[suisi[start + k]] == 1:
    cnt += 1

누적합 알고리즘

• 주의점
  : 메모리를 많이 사용함 (좌표압축을 통해 극복가능)

• 장점
  : O(N)으로 시간복잡도를 단축할 수 있음

• 주로 사용하는 문제
  : 구간 사이의 장애물 수 구하기 문제

Idea

1. 장애물이 존재할 수 있는 구간 만큼의 메모리를 선언.

2. 하나의 장애물이 존재하는 구간에 모두 +1을 하는 것이 아닌, 장애물이 존재하는 구간의 처음에 +1을 해줌

3. 장애물이 존재하는 구간의 끝 바로 뒤에 -1을 해줌
   (4번을 위한 과정)

4. 실제 구간의 누적합을 구하기 위해서는 구간의 값을 더하거나 빼서 결정

(백준3020번 (개똥벌레) 주요코드)

for i in range(N):
  temp = int(input())
  if i % 2 == 0:
    Obstacle[1] += 1
    Obstacle[temp + 1] -= 1
  else:
    Obstacle[H - temp + 1] += 1

# 이 과정을 통해 장애물의 위치 한번에 계산 가능
for i in range(1, H):
  Obstacle[i + 1] += Obstacle[i]

좌표압축 알고리즘

• 주의점
  : 원래 배열과 똑같은 임시 배열이 필요하다

• 장점
  : 메모리의 효율성을 높일 수 있다.

• 주로 사용하는 문제
  : 누적합 알고리즘과 같이 사용할 수 있다(?)

Idea

1. 원래배열 arr과 이를 복사한 temp배열을 선언한다.

2. temp배열을 정렬한다.

3. arr[i]를 temp배열에서 이분탐색으로 찾은 뒤 그 index를 다시 저장한다.

(백준19584번 (난개발) 일부코드)

MAP_INDEX = [ ... ]
temp = sorted(MAP_INDEX)
for i in range(N):
  MAP_INDEX[i] = bisect_left(temp, MAP_INDEX[i])

이분탐색

• 주의점:
  : 정렬되어 있는 배열에 사용 가능
  : lower_bound, upper_bound의 활용 주의

• 장점
  : 정렬시간 포함 O(N log N)시간에 탐색 가능

• 주로 사용하는 문제
  : 어떤 기준에 따라 데이터를 정렬할 수 있고, 이 기준과 목표값이 비례하는 성질을 가질 때