코딩테스트 알고리즘

크루스칼 알고리즘 (추가공부)

그래프 내 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용 (사이클이 없는, 가중치의 합 최소가 되는 상태)
최소 신장 트리를 구하기 위한 알고리즘

• 신장 트리(Spanning tree): 모든 정점을 포함, 정점간 서로 연결, 싸이클이 존재하지 않는 그래프
• 최소 신장 트리(Minimum Spanning Tree): 신장 트리 중 가중치 합이 최소인 그래프
• 싸이클 여부: 서로소 집합(Disjoint Set)의 Union & Find 활용
  크루스칼 알고리즘 블로그

소수 알고리즘

2부터 n-1까지 나누어 떨어지는 수가 없는 경우 소수 판별

def isPrime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n%i == 0:
            return False
    return True

에라토스테네스의 체

정해진 범위 내 소수를 구하는 경우 사용되는 알고리즘
범위 내 숫자들에서 합성수를 반복적으로 지우는 방식으로 소수를 찾는다.

• 지워지지 않은수 중 작은수를 소수로 채택, 해당 수의 배수를 모두 제거

import math

def prime_list(n):
    prime = [True]*(n+1)
    
    for i in range(2, math.isqrt(n)+1):
        if prime[i] == True:
            for j in range(2*i, n+1, i):
                prime[j] = False
                
    return [i for i in range(2, n+1) if prime[i] == True]

에라토스테네스의 체 블로그1
에라토스테네스의 체 블로그2