목록CS (18)

하루살이 개발자

[알고리즘] union-find 알고리즘

* 수학에서 서로소 집합 - 공통 원소가 없는 두 집합 * 서로소 집합 자료구조 - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 - 연산: union + find 1) union - 2개의 원소로 이루어진 집합을 하나의 집합으로 합치기(합집합) 2) find - 특정 원소가 속한 집합이 뭔지 알려주는 연산 - 서로소 집합 자료구조는 union + find 연산으로 구성되어 union-find 자료구조라 불린다. * 서로소 집합 계산 알고리즘 1) 동작 방법 (1) union 연산 확인 - 서로 연결된 두 노드 확인 -> A의 루트노드 A'와 B의 루트노드 B'찾기(find) -> A'를 B'의 부모 노드로 설정하기(A' < B') (2) 모든 union 연산을 처리할 때까지 (..
CS/알고리즘 2022. 2. 20. 11:15
[알고리즘] 소수찾기 - 에라토스테네스의 체

def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n m = int(n ** 0.5) for i in range(2, m + 1): if sieve[i] == True: # i가 소수인 경우 for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정 sieve[j] = False # 소수 목록 산출 return [i for i in range(2, n) if sieve[i] == True] 임의의 자연수 n이 있으면 그 이하의 소수들을 전부 찾아내는 데 있어서 최적화된 알고리즘! * 관련 문제 https://thrainer.tistory.com/62?category=1007146 [Bae..
CS/알고리즘 2022. 2. 16. 15:44
이전 Prev 1 ··· 4 5 6 7 8 9 Next 다음