본문 바로가기
반응형

📝 알고리즘/수학5

🧮 부분 집합, 멱집합 구하기 알고리즘 직접 구현! 부분집합, 멱집합을 구하는 알고리즘을 파이썬으로 구현해보자. 부분 집합, 멱 집합이란? 부분 집합은 어떤 집합에서 몇몇 원소들만 뽑아서 만든 집합. 부분 집합은 원래 집합에 포함되는 관계이다. 멱집합은 어떤 집합의 모든 부분 집합을 모아둔 집합 원소 갯수가 n인 원래 집합에서 원소 갯수가 r인 부분집합의 갯수는 nCr(조합)과 같다. 멱집합 원소의 갯수는 2^n이다. 부분 집합, 멱집합 알고리즘 구현해보기 부분 집합 조합을 구하는 방법과 같다. 아래 글 참고. 🧮 조합 알고리즘 직접 구현! 조합과 중복조합 알고리즘을 파이썬으로 구현하기 조합이란? 원소를 순서없이 나열하는 것 n개의 원소에서 r개를 조합하면 가짓수는 n!/(n-r)!r! 중복조합은 n+r-1개의 원소에서 r개를 조합하는 것 programm.. 2023. 1. 10.
🧮 조합 알고리즘 직접 구현! 조합과 중복조합 알고리즘을 파이썬으로 구현하기 조합이란? 원소를 순서없이 나열하는 것 n개의 원소에서 r개를 조합하면 가짓수는 n!/(n-r)!r! 중복조합은 n+r-1개의 원소에서 r개를 조합하는 것과 같다. n개의 원소에서 모든 조합 가지수는 2^n - 1 여러가지 조합 알고리즘 구현해보기 기본 조합 n개의 원소가 있는 배열에서 r개를 뽑는다. 조합 점화식에 기반한 방식 def combination(arr, r): if r == 0: return [set()] elif arr == []: return [] new_arr = arr[:] item = new_arr.pop() not_item_comb = combination(new_arr, r) item_comb = [s|{item} for s in c.. 2023. 1. 10.
🧮 순열 알고리즘 직접 구현! 순열과 중복순열 알고리즘을 파이썬으로 구현하기 순열이란? 원소들을 순서에 따라 나열하는 것 n개의 원소에서 r개를 나열한다 하면 그 가짓수는 n!/(n-r)! 중복해서 원소를 뽑으면 n^r 전체 순열 가짓수의 합은 조금 복잡하다. (링크) 여러가지 순열 알고리즘 구현해보기 기본 순열 n개의 원소를 가진 배열 arr에서 r개를 뽑아 나열한다. swap을 이용한 방식 def permutations (arr, r): n = len(arr) results = [] def _perm_swap (arr, depth): if (depth == r): results.append(arr[:r]) return for i in range(depth, n): # 위치를 바꿈 arr[i], arr[depth] = arr[dep.. 2023. 1. 10.
⚡ 고속 거듭제곱 알고리즘 간단설명! 요약 지수를 2진법으로 바꿈 밑을 제곱해서 올려가며 2진법에서 1일 때만 곱해줌 그냥 n번을 곱하면 복잡도 O(n)이나 이 방식은 O(log n)임 설명 def fast_pow(a, b): ret = 1 while b: if b%2: ret *= a a *= a b >>= 1 # 혹은 b //= 2 return ret print(fast_pow(2, 10)) 파이썬 코드 밑 a와 지수 b를 입력받음 b는 계속 2로 나눠주고, a는 계속 제곱을 시킴. b를 2로 나눈 값이 1일 때(2진수에서 해당 자리수가 1일때) 결과값에 제곱한 결과를 곱해줌. 2022. 10. 6.
[알고리즘, 원리] 유클리드 호제법 정의 a = bx+r 일 때 (a,b) = (b,r) a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다. 이를 이용하여 반복하면 두 수의 최대공약수를 쉽게 구할 수 있다. 구현 파이썬 (Python) def gcd(a,b): while b != 0: a, b = b, a%b return a 두 수에서 유클리드 호제법을 반복하여 최대공약수를 구하는 함수 def gcd(a, b): r = b % a if r == 0: return a return gcd(r, a) 재귀 함수를 이용한 구현 def gcd(*num_list): if len(num_list) == 1: return num_list[0] elif len(num_list) == 2: a, b = num_list[0], num_l.. 2022. 9. 10.
반응형

티스토리툴바