알고리즘 정리

itertools 라이브러리

• 효율적인 루핑을 위한 이터레이터를 만드는 함수

combinations

• combinations(iterable, r) : iterable에서 원소 개수가 r개인 조합 뽑기
• 시간복잡도 : n! / r! / (n - r)!

from itertools import combinations

l = ['A', 'B', 'C']

for i in combinations(l, 2):
    print(i)

'''
('A', 'B')
('A', 'C')
('B', 'C')
'''

combinations_with_replacement

• combinations_with_replacement(iterable,r) : iterable에서 원소 개수가 r개인 중복 조합 뽑기
• 시간복잡도 : n! / r! / (n - r)!

from itertools import combinations_with_replacement

l = ['A', 'B', 'C']

for i in combinations_with_replacement(l, 2):
    print(i)

'''
('A', 'A')
('A', 'B')
('A', 'C')
('B', 'B')
('B', 'C')
('C', 'C')
'''

permutations

• permutations(iterable,r = None) : iterable에서 원소 개수가 r개인 순열 뽑기
• 시간 복잡도 : n! / r!

from itertools import permutations

l = ['A', 'B', 'C']

for i in permutations(l):
    print(i)

'''
('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')
'''

from itertools import permutations

l = ['A', 'B', 'C']

for i in permutations(l, 2):
    print(i)

'''
('A', 'B')
('A', 'C')
('B', 'A')
('B', 'C')
('C', 'A')
('C', 'B')
'''

product

• product(*iterables, repeat = 1) : 여러 iterable의 데카르트곱 리턴
• 시간 복잡도 : n^k

from itertools import product

l = ['A', 'B', 'C']

for i in product(l, repeat = 2):
	print(i)

'''
('A', 'A')
('A', 'B')
('A', 'C')
('B', 'A')
('B', 'B')
('B', 'C')
('C', 'A')
('C', 'B')
('C', 'C')
'''

from itertools import product

l1 = ['A', 'B']
l2 = ['1', '2']

for i in product(l1, l2, repeat = 1):
    print(i)

'''
('A', '1')
('A', '2')
('B', '1')
('B', '2')
'''

소수 판별하기

• 소수 : 1과 자기 자신만을 약수로 가지는 수

기본

def solution(n):
    for i in range(2, a):
        if n % i == 0:
            return False

    return True

약수의 성질

def solution(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False

    return True

에라테스토스트의 체

def solution(n, k):
    answer = 0
    visited = [False] * (n + 1)

    for i in range(2, n + 1):
        if not visited[i]:
            for j in range(i, n + 1, i):
                if not visited[j]:
                    visited[j] = True
                    answer += 1
        
                    if answer == k:
                        return j

골드바흐의 추측

def solution(n):
    MAX = 1000001
    visited = [False] * MAX
    
    # 에라테스토스트의 체 1
    for i in range(2, int(MAX ** 0.5)):
        if arr[i]:
            for j in range(i + i, MAX, i):
                visited[j] = True
    
    return True if not visited[i] else False

def solution(n):
    MAX = 1000001
    visited = [False] * MAX
    
    # 에라테스토스트의 체 2
    for i in range(2, int(MAX ** 0.5)):
        if arr[i]:
            j = 2
            while i * j < MAX:
                visited[i * j] = True
                j += i
    
    return True if not visited[i] else False