기타 알고리즘

소수 판별

import math

# 소수 판별 함수
def is_prime_number(x):
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

특정 범위안에 존재하는 모든 소수 찾기

에라토스테네스의 체

• 특정 범위 내의 자연수가 소수인지 아닌지를 판별하는 알고리즘

• 동작 원리

  • 2부터 N까지 나열
  • 남은 수 중에서 처리하지 않은 작은 수 i 설정
  • 남은 수 중에서 i의 배수를 모두 제거 (i는 제외)
  • 2,3 번 반복

import math

n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별
array = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화

# 에라토스테네스의 체 알고리즘 
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        j = 2 
        while i * j <= n:
            array[i * j] = False
            j += 1

# 모든 소수 출력
for i in range(2, n + 1):
    if array[i]:
        print(i, end=' ')

투 포인터 ( 부분 연속 수열 )

• 합이 M인 부분 연속 수열의 개수 or 가장 큰 값을 지니는 부분 연속 수열의 값...

• 특정 합을 가지는 부분 연속 수열

n = 5 # 데이터의 개수 N
m = 5 # 찾고자 하는 부분합 M
data = [1, 2, 3, 2, 5] # 전체 수열

count = 0
interval_sum = 0
end = 0

# start를 차례대로 증가시키며 반복
for start in range(n):
    # end를 가능한 만큼 이동시키기
    while interval_sum < m and end < n:
        interval_sum += data[end]
        end += 1
    # 부분합이 m일 때 카운트 증가
    if interval_sum == m:
        count += 1
    interval_sum -= data[start]

print(count)

• 구간 합 문제

arr = list(map(int,input().split()))
n = len(arr)
dp = [i for i in arr]

def get_max ():
  temp = 0
  maxx = 0
  for i in range(n):
    temp += dp[i]
    if temp > maxx:
      maxx = temp
    elif temp < 0:
      temp = 0

  return maxx 

def get_max_minus():
  maxx = int(-1e9)
  for i in range (n):
    if maxx < dp[i]:
      maxx = dp[i]
      
  return maxx

res = get_max()

if res != 0:
  print(res)
else:
  print(get_max_minus())