목차
순열(Permutations)
- 순열은 주어진 원소들로 만들 수 있는 모든 가능한 순서 있는 배열입니다. (순서가 중요한 경우)
- 시간복잡도 : O(nPr)
- 예시
itertools 라이브러리 이용
- 코드
-
from itertools import permutations print(list(permutations([1, 2, 3, 4, 5], 3)))
-
직접구현
- 코드
-
def permutations(arr, r): def generate(arr, prefix=[]): if len(prefix) == r: result.append(prefix) return for i in range(len(arr)): generate(arr[:i] + arr[i + 1 :], prefix + [arr[i]]) result = [] generate(arr, []) return result print(permutations([1, 2, 3, 4, 5], 3))
-
조합(Combinations)
- 조합은 주어진 원소들로 만들 수 있는 모든 가능한 순서 없는 집합입니다. (순서가 중요하지 않은 경우)
- 시간복잡도 : O(nCr)
- 예시
itertools 라이브러리 이용
- 코드
-
from itertools import combinations print(list(combinations([1, 2, 3, 4, 5], 3)))
-
직접구현
- 코드
-
def combinations(arr, r): def generate(start, prefix=[]): if len(prefix) == r: result.append(prefix) return for i in range(start, len(arr)): generate(i + 1, prefix + [arr[i]]) result = [] generate(0) return result print(combinations([1, 2, 3, 4, 5], 3))
-
중복순열(Product)
- 중복순열은 주어진 집합에서 원소를 중복해서 선택하여 만들 수 있는 모든 가능한 순서 있는 배열입니다.
- 시간복잡도 : O(n^r)
- 예시
itertools 라이브러리 이용
- 코드
-
from itertools import product print(list(product([1, 2, 3], repeat=5)))
-
[(1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 1, 3), (1, 1, 1, 2, 1), (1, 1, 1, 2, 2), (1, 1, 1, 2, 3), (1, 1, 1, 3, 1), (1, 1, 1, 3, 2), (1, 1, 1, 3, 3), (1, 1, 2, 1, 1), (1, 1, 2, 1, 2), (1, 1, 2, 1, 3), (1, 1, 2, 2, 1), (1, 1, 2, 2, 2), (1, 1, 2, 2, 3), (1, 1, 2, 3, 1), (1, 1, 2, 3, 2), (1, 1, 2, 3, 3), (1, 1, 3, 1, 1), (1, 1, 3, 1, 2), (1, 1, 3, 1, 3), (1, 1, 3, 2, 1), (1, 1, 3, 2, 2), (1, 1, 3, 2, 3), (1, 1, 3, 3, 1), (1, 1, 3, 3, 2), (1, 1, 3, 3, 3), (1, 2, 1, 1, 1), (1, 2, 1, 1, 2), (1, 2, 1, 1, 3), ... (3, 3, 1, 1, 1), (3, 3, 1, 1, 2), (3, 3, 1, 1, 3), (3, 3, 1, 2, 1), (3, 3, 1, 2, 2), (3, 3, 1, 2, 3), (3, 3, 1, 3, 1), (3, 3, 1, 3, 2), (3, 3, 1, 3, 3), (3, 3, 2, 1, 1), (3, 3, 2, 1, 2), (3, 3, 2, 1, 3), (3, 3, 2, 2, 1), (3, 3, 2, 2, 2), (3, 3, 2, 2, 3), (3, 3, 2, 3, 1), (3, 3, 2, 3, 2), (3, 3, 2, 3, 3), (3, 3, 3, 1, 1), (3, 3, 3, 1, 2), (3, 3, 3, 1, 3), (3, 3, 3, 2, 1), (3, 3, 3, 2, 2), (3, 3, 3, 2, 3), (3, 3, 3, 3, 1), (3, 3, 3, 3, 2), (3, 3, 3, 3, 3)]
-
직접구현
- 코드
-
def product(arr, r): def generate(prefix=[]): if len(prefix) == r: result.append(prefix) return for i in range(len(arr)): generate(prefix + [arr[i]]) result = [] generate() return result print(product([1, 2, 3], 5))
-
[[1, 1, 1, 1, 1], [1, 1, 1, 1, 2], [1, 1, 1, 1, 3], [1, 1, 1, 2, 1], [1, 1, 1, 2, 2], [1, 1, 1, 2, 3], [1, 1, 1, 3, 1], [1, 1, 1, 3, 2], [1, 1, 1, 3, 3], [1, 1, 2, 1, 1], [1, 1, 2, 1, 2], [1, 1, 2, 1, 3], [1, 1, 2, 2, 1], [1, 1, 2, 2, 2], [1, 1, 2, 2, 3], [1, 1, 2, 3, 1], [1, 1, 2, 3, 2], [1, 1, 2, 3, 3], [1, 1, 3, 1, 1], [1, 1, 3, 1, 2], [1, 1, 3, 1, 3], [1, 1, 3, 2, 1], [1, 1, 3, 2, 2], [1, 1, 3, 2, 3], [1, 1, 3, 3, 1], [1, 1, 3, 3, 2], [1, 1, 3, 3, 3], [1, 2, 1, 1, 1], [1, 2, 1, 1, 2], [1, 2, 1, 1, 3], ...... [3, 2, 3, 1, 3], [3, 2, 3, 2, 1], [3, 2, 3, 2, 2], [3, 2, 3, 2, 3], [3, 2, 3, 3, 1], [3, 2, 3, 3, 2], [3, 2, 3, 3, 3], [3, 3, 1, 1, 1], [3, 3, 1, 1, 2], [3, 3, 1, 1, 3], [3, 3, 1, 2, 1], [3, 3, 1, 2, 2], [3, 3, 1, 2, 3], [3, 3, 1, 3, 1], [3, 3, 1, 3, 2], [3, 3, 1, 3, 3], [3, 3, 2, 1, 1], [3, 3, 2, 1, 2], [3, 3, 2, 1, 3], [3, 3, 2, 2, 1], [3, 3, 2, 2, 2], [3, 3, 2, 2, 3], [3, 3, 2, 3, 1], [3, 3, 2, 3, 2], [3, 3, 2, 3, 3], [3, 3, 3, 1, 1], [3, 3, 3, 1, 2], [3, 3, 3, 1, 3], [3, 3, 3, 2, 1], [3, 3, 3, 2, 2], [3, 3, 3, 2, 3], [3, 3, 3, 3, 1], [3, 3, 3, 3, 2], [3, 3, 3, 3, 3]]
-
중복조합(Combinations with Replacement)
- 중복조합은 주어진 집합에서 원소를 중복해서 선택하여 만들 수 있는 모든 가능한 순서 없는 집합입니다.
- 시간복잡도 : O(r+(n-1)Cr)
- 예시
itertools 라이브러리 이용
- 코드
-
from itertools import combinations_with_replacement print(list(combinations_with_replacement([1, 2, 3], 5)))
-
직접구현
- 코드
-
def combintations_with_replacement(arr, r): def generate(start, prefix=[]): if len(prefix) == r: result.append(prefix) return for i in range(start, len(arr)): generate(i, prefix + [arr[i]]) result = [] generate(0) return result print(combintations_with_replacement([1, 2, 3], 5))
-
'Algorithm > Tips' 카테고리의 다른 글
빅오(big-O) (시간복잡도) (1) | 2024.04.07 |
---|---|
그래프(Graph) vs 트리(Tree) (0) | 2023.10.16 |