[Python]기타 알고리즘

1. 소수 판별 알고리즘

(1) 제곱근 이용한 소수판별

: 하나의 수에 대해 소수인지 아닌지 판별
: O(N^1/2) 

import math

def Is_Prime(num):
    sqrt_num = int(math.sqrt(num))
    
    for i in range(2,sqrt_num+1):
        if(num%i==0):    
            return False        
        
    return True

def main():
    num = int(input("소수판별한 숫자를 입력하시오 "))
    
    if(Is_Prime(num)):
         print("소수입니다")
    else:
         print("소수가 아닙니다")
         
if __name__=="__main__":
    main()

(2) 에라토스테네스의 체

: 특정한 수의 범위 안에 존재하는 모든 소수를 찾는 경우 이용
: O(NloglogN)
 

1) 동작법

: N보다 작거나 같은 모든 소수를 찾는 경우

• 2부터 N까지의 모든 자연수 나열
• 남은 수 중에서 아직 처리하지않은 가장 작은 수 i를 찾는다
• 남은 수 중에서 i의 배수를 모두 제거(이때, i는 제거하지않음)
• 더이상 반복할 수 없을 때까지 위 과정 반복

=> 이때, 제곱근까지 수행해도 결과는 동일함

import math


def main():
    num = int(input("소수를 구할 범위를 입력하시오"))

    num_sqrt =int(math.sqrt(num))
    done=[True]*(num+1) #소수인 경우 True, 소수가 아닌 경우 False

    for i in range(2, num_sqrt+1):
        j=2
        while(i*j<=num):
            done[i*j]=False
            j+=1
    
    for i in range(2, num+1):
        if(done[i]==True):
            print(i, end=" ")

    


if __name__=="__main__":
    main()

2. 투 포인터

: 리스트에 순차적으로 접근해야할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
ex) 2,3,4,5,6,7번 학생 지목하는 경우 '2번부터 7번까지의 학생'이라고도 할 수 있음
=> 리스트에 담긴 데이터에 순차적으로 접근해야할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위 표현
 

(1) 특정한 합을 가지는 부분 연속 수열 찾는 경우

: N개의 자연수로 구성된 수열있을 때, 합이 M인 부분 연속 수열의 갯수 구하라
 

1) 동작법

1. 시작점(start)와 끝점(end)이 첫 번째 원소의 인덱스(0) 가리키도록 함
2. 현재 부분 합이 M과 같다면 count++
3. 현재 부분 합이 M보다 작다면 end++ => 구간 늘리기
4. 현재 부분 합이 M보다 크거나 같다면 start++ => 구간 줄이기
5. 모든 경우 확인할 때까지 2~4) 과정 반복

import time

def main():
    arr= [1,2,3,2,5]
    M=5

    start=0
    end=0
    res=0

    sum=arr[0]
    while(start<=len(arr)-1 and end<=len(arr)-1):
        if(sum<M):
            end+=1
            sum+=arr[end]
        elif(sum>M):
            start+=1
            sum-=arr[start-1]
        else:
            res+=1
            start+=1
            sum-=arr[start-1]

    print(res)

if __name__=="__main__":
 
    main()

3. 구간 합

: 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수 합한 값 계산하는 문제
: 접두사 합(prefix sum) 이용 
=> 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해놓은 것

def main():
    arr=[10,20,30,40,50]

    prefix_sum=[0]
    sum=0

    for i in arr:
        sum+=i
        prefix_sum.append(sum)



    start,end = map(int, input("몇번부터 몇번까지의 숫자들의 합을 구할지 정하시오 : ").split())

    print(prefix_sum[end]-prefix_sum[start-1])


if __name__=="__main__":
    main()