반응형 dfs3 🧮 부분 집합, 멱집합 구하기 알고리즘 직접 구현! 부분집합, 멱집합을 구하는 알고리즘을 파이썬으로 구현해보자. 부분 집합, 멱 집합이란? 부분 집합은 어떤 집합에서 몇몇 원소들만 뽑아서 만든 집합. 부분 집합은 원래 집합에 포함되는 관계이다. 멱집합은 어떤 집합의 모든 부분 집합을 모아둔 집합 원소 갯수가 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. 이전 1 다음 반응형
