[파이썬 알고리즘 인터뷰][그래프] 조합

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

조합 구현

 

책에서 구현된 코드

# 재귀
def combine(self, n: int, k: int) -> list[list[int]]:
    results = []
    
    def dfs(elements, start: int, k: int):
        if k == 0:
            results.append(elements[:])
            return
        
        for i in range(start, n+1):
            elements.append(i)
            dfs(elements, i + 1, k - 1)
            elements.pop()
    
    dfs([], 1, k)
    return results
    
    
# itertools
def combine(self, n: int, k: int) -> list[list[int]]:
    return list(itertools.combinations(range(1, n + 1), k))

 

기억해야할 기법

• itertools
  
  • itertools의 permutations / combinations의 결과를 list로 만들면 list[tuple]
• 효과적인 combination 구현
  • k개가 채워지지 않는 재귀가 존재
  • 정답을 구하지 않는 재귀를 생략(pruning)

 

내가 구현한 코드

# 재귀
def combine(n: int, k: int) -> list[list[int]]:
    result = []
    tmp_res = []

    def comb(s: int, d: int):
        if d == k:
            result.append(tmp_res[:])
            return
        for i in range(s, n):
            tmp_res.append(i+1)
            comb(i+1,d+1)
            tmp_res.pop()

    comb(0, 0)
    return result
    
# itertools
from itertools import combinations

def combine(n: int, k: int) -> list[list[int]]:
    return list(map(list, combinations(list(range(1, n+1)), k)))

# Pruning한 방법
def combine(n: int, k: int) -> list[list[int]]:
    result = []
    tmp_res = []

    def comb(s: int, k: int):
        if s+k <= n:
            if k == 0:
                result.append(tmp_res[:])
                return
            for i in range(s, n):
                tmp_res.append(i+1)
                comb(i+1,k-1)
                tmp_res.pop()

    comb(0, k)
    return result

• 책에서 속도를 높일 방법의 힌트를 줘서 고민해봤는데, itertools만큼 효율이 나오진 못함
• 실행 결과