여러 기업들의 코딩 테스트를 준비하다보면 완전 탐색을 해야하는 문제가 많은데, 그런 문제를 만났을때 가장 직관적이기도 하고 쉽게 생각나는 것이 주어진 조건에 맞는 순열 혹은 조합을 모두 구해서 체크하는 것이다.
하지만 생각은 빨리 나는데 구현을 처음 해보면 은근 쉽지가 않다. 그래서 구현 방법 3가지를 정리해놓으려고 한다.
- itertools 모듈
파이썬의 itertools 모듈을 이용하면 쉽게 사용할 수 있다.
다른 상세한 내용은 구글링해도 될 듯하여 간단한 코드만 보고 넘어가자.
2. 재귀 함수
itertools를 사용하면 되긴하지만, 다른 언어나 외부 모듈을 사용하지 못하는 경우 혹은 공부를 위해서 구현해보고 싶은 사람은 직접 구현해야 한다.
일단 첫 번째로 재귀 함수로 구현하는데, 한 가지 원소를 뽑고 그 원소를 제외한 리스트로 조합 혹은 순열을 구하는 것이다.
combination([1,2,3,4],2) = ([1] + combination([2,3,4],1)) and
([2] + combination([3,4],1)) and ([3] + combination([4],1))
permutation([1,2,3,4],2) = ([1] + permutation([2,3,4],1)) and
([2] + permutation([1,3,4],1)) and ([3] + permutation([1,2,4],1)) and
([4] + permutation([1,2,3],1))
와 같은 논리로 해결한다.
코드는 다음과 같다.
3. dfs / bfs
완전 탐색은 조합이나 순열을 사용하지 않고도 dfs, bfs같은 탐색 알고리즘을 통해서도 구현 가능하다.
조합, 순열도 같은 방식으로 구현할 수 있다.
코드는 dfs로 구현한 것이다.
중복 순열, 중복 조합의 경우에는 다른 구현 방법이 있겠지만, 그냥 그대로 구한 다음에 중복된 원소를 빼주는 과정만 추가하면 간단할 것 같다.
Python
파이썬 알고리즘 인터뷰 - 35. 조합
s코딩초보s 2022. 1. 30. 14:18
<--- 리트코드 77. Combinations --->
# 문제: 전체 수 n을 입력받아 k개의 조합을 리턴하라.
입력
출력
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4]
]
# 풀이
1. DFS로 k개 조합 생성
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def combine(n, k): results = [] def dfs(elements, start, k): if k == 0: results.append(elements[:]) for i in range(start, n + 1): elements.append(i) dfs(elements, i + 1, k -1) elements.pop() dfs([], 1, k) return results n = 4 k = 2 print(combine(n, k)) | cs |
2. itertools 모듈 사용
import itertools def combine(n, k): return list(itertools.combinations(range(1, n + 1), k)) n = 4 k = 2 print(combine(n, k)) | cs |
목적
알고리즘 문제 풀이 시 자주 등장하는 조건은 조합과 순열을 이용한 문제 풀이이다. 이 때 레파토리 코드를 이용하여 개념을 익히고 이를 추후 적용할 수 있도록 한다. 파이썬 기본 itertools 라이브러리에서 조합과 순열을 제공하며 여러 구현 코드 방식을 알아보자.
조합 및 순열 - itertools, for문
조합 (combinations 함수)
- from itertool, combinations(반복 가능한 객체, r)
from itertools 입력 후, itertools.combinations(iterable, r)로 함수를 사용할 수 있다. 이 때 iterable에 있는 원소가 r 개씩 조합된다.
>>> import itertools >>> number = [1,2,3,4] >>> _combo = itertools.combinations(number,3) >>> _combo <itertools.combinations object at 0x0000022BB5D48540> >>> for i in _combo: ... print(i) ... (1, 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4)예를 들면 위와 같다. number에 대한 원소를 itertools.combinations(number,3)으로 3개씩 조합한 값을 _combo에 저장하였다.
개수만 세는 경우, 아래와 같이 itertools.combinations를 통해 리턴된 iterable 값을 list로 변환한다. len() 함수를 통해 리스트 내 요소의 개수를 세면 조합의 개수를 셀 수 있다.
>>> from itertools import combinations >>> number = [1,2,3,4] >>> _combo = combinations(number,3) >>> len(list(_combo)) 4- for문 사용
for문을 사용하여 조합을 구현할 수 있다.
>>> number = [1,2,3,4] >>> for i in range(len(number)): ... for j in range(i+1,len(number)): ... for k in range(j+1,len(number)): ... print(number[i],number[j],number[k]) ... 1 2 3 1 2 4 1 3 4 2 3 4위 i,j,k를 구성하여 3개의 숫자를 조합할 수 있다.
- i는 range(len(nums))로 nums에 있는 index를 모두 탐색 될 수 있도록 한다.
- j는 range(i+1, len(nums))로 i번째에서 선택한 값 그 다음 값을 사용한다.
-k는 range(j+1, len(nums))로 j번째에서 선택한 값 그 다음 값을 사용한다.
따라서 위와 같이 조합의 결과값이 정상적으로 나타나는 것을 알 수 있다.
하나 의문이 들 수 있는 부분은 예를 들어 number = [1,2,3,4]일 때 i = 3이 되는 경우일 텐데,
이 때 for i range(len(nums)):는 모든 index를 탐색하므로 당연하게도 계산되고, for j in range(i+1,len(nums)):는 i+1 = 4부터 시작이고 이는 len(nums) = 4이므로 같아 range(4,4)는 더 이상 계산되지 않고 무효 처리된다. 따라서, 인덱스를 벗어나면 무효처리되므로 해당 값은 조합에 포함되지 않는다.
- from itertools와 for문 계산 시간 비교
0.015와 0.03251로 itertools가 for문보다 더 빠른 성능을 보여주었다.
>>> import time >>> import itertools >>> start=time.time() >>> number = [1,2,3,4,5,6,7,8,9,10,11,12] >>> for i in itertools.combinations(number,3): ... pass ... # print(i) ... >>> end=time.time() >>> print(end-start) 0.015026330947875977 >>> start_2=time.time() >>> number = [1,2,3,4,5,6,7,8,9,10,11,12] >>> for i in range(len(number)): ... for j in range(i+1,len(number)): ... for k in range(j+1,len(number)): ... pass ... # print(number[i],number[j],number[k]) ... >>> end_2=time.time() >>> print(end_2-start_2) 0.032510995864868164순열 (permutations 함수)
- from itertools, permutations(반복 가능한 객체, r)
>>> number = [1, 2, 3, 4] >>> _perm = permutations(number,3) >>> _perm <itertools.permutations object at 0x00000217F4837630> >>> for i in _perm: ... print(i, end=" ") ... (1, 2, 3) (1, 2, 4) (1, 3, 2) (1, 3, 4) (1, 4, 2) (1, 4, 3) (2, 1, 3) (2, 1, 4) (2, 3, 1) (2, 3, 4) (2, 4, 1) (2, 4, 3) (3, 1, 2) (3, 1, 4) (3, 2, 1) (3, 2, 4) (3, 4, 1) (3, 4, 2) (4, 1, 2) (4, 1, 3) (4, 2, 1) (4, 2, 3) (4, 3, 1) (4, 3, 2)가독성을 위해 결과값은 일부 줄바꿈 처리하였다. 예상한대로 조합과는 다르게 순서 상관있도록 순열 값이 출력되는 것을 알 수 있다.
중복 조합 (combinations_with_replacement 함수)
- from itertools, cobinations_with_replacement(반복 가능한 객체, r)
중복 조합은 조합과 마찬가지로 순서는 상관 없으며 조합과 다르게 하나의 원소를 여러 번 사용할 수 있다. (조합은 원소 사용은 1번이고, 순서는 상관이 없다.)
combinations_with_replacement로 구현할 수 있으며, combinations와 차이는 아래 결과로 이해할 수 있다.
#1> 조합 for i in itertools.combinations([1,2,3,4], 2): ... print(i, end=' ') ... (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) #2> 중복 조합 for i in itertools.combinations_with_replacement([1,2,3,4], 2): ... print(i, end=' ') ... (1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)위는 #1은 조합이고, 아래 #2는 중복 조합이다. 말한 바와 같이 원소를 중복하여 사용할 수 있는 지 없는 지에 대한 차이가 있으며, itertools를 통해 구현 가능하다.
중복 순열 (product 함수)
- from itertools, product(반복 가능한 객체)
중복 순열은 순열과 마찬가지로 순서를 고려한다. 반복 가능한 객체끼리 각 원소별로 곱하여 값을 도출할 수 있다.
>>> from itertools import product >>> number=[1,2,3,4] >>> product(number) <itertools.product object at 0x000001DE2EDAE5C0> >>> for i in product(number, "ab"): ... print(i, end=" ") ... (1, 'a') (1, 'b') (2, 'a') (2, 'b') (3, 'a') (3, 'b') (4, 'a') (4, 'b')repeat factor를 사용하여 원소별 곱을 쉽게 할 수 있다. 아래의 경우 number과 number끼리 곱을 만든다.
>>> from itertools import product >>> number=[1,2,3,4] >>> product(number) <itertools.product object at 0x000001E1CFDCE540> >>> for i in product(number, repeat=2): ... print(i, end=" ") ... (1, 1) (1, 2) (1, 3) (1, 4) (2, 1) (2, 2) (2, 3) (2, 4) (3, 1) (3, 2) (3, 3) (3, 4) (4, 1) (4, 2) (4, 3) (4, 4)- for문 사용
for문을 사용하여 조합을 구현할 수 있다. 조합에서의 for문과 동일하지만, i와 j와 모두 number에 대한 index를 전체 탐색한다는 것을 알 수 있다.
>>> from itertools import product >>> number=[1,2,3,4] >>> product(number) <itertools.product object at 0x000001A28751E580> >>> for i in range(len(number)): ... for j in range(len(number)): ... print((number[i],number[j]), end = " ") ... (1, 1) (1, 2) (1, 3) (1, 4) (2, 1) (2, 2) (2, 3) (2, 4) (3, 1) (3, 2) (3, 3) (3, 4) (4, 1) (4, 2) (4, 3) (4, 4)- from itertools와 for문 계산 시간 비교
0.0180666과 0.0269959로 itertools가 for문보다 더 빠른 성능을 보여주었다.
>>> import time >>> from itertools import product >>> start=time.time() >>> number=[1,2,3,4,5,6,7,8,9,10] >>> for i in product(number, repeat=2): ... pass ... # print(i, end=" ") ... >>> end=time.time() >>> print(end-start) 0.012215137481689453 >>> start_2=time.time() >>> number=[1,2,3,4,5,6,7,8,9,10] >>> for i in range(len(number)): ... for j in range(len(number)): ... pass ... # print((number[i],number[j]), end = " ") ... >>> end_2=time.time() >>> print(end_2-start_2) 0.020475149154663086조합 및 순열 - yield(generator)
<참고로, yield 방식 대비 itertools이 계산이 빠른 것을 알 수 있었다.>
yield 함수를 사용하여 조합, 반복조합, 순열, 반복순열을 구현할 수 있다. 우선 yield 함수를 이해하기 위해서는 generator를 이해할 필요가 있다.
generator는 iterator를 생성해주는 함수로, 함수 안에 yield 키워드를 사용한다.
- iterable: 리스트, 튜플 등 순회 가능한 자료구조
- iterator: 값을 차례대로 반환할 수 있는 객체
- generator: iterator를 생성 해 주는 함수, 함수 안에 yield 키워드를 사용하며, yield가 있다면 generator이다.
def my_gen(): yield 1 yield 2 yield 3위와 같은 함수는 yield를 포함하므로 generator가 된다. 이 때 yield는 기존 사용되던 return과 다르다.
해당 함수는 함수가 실행되면 yield까지 반환하고, 멈춘다. 이 후, 다시 실행되면 다음 yield까지 실행된다. generator의 다음 값으로 넘어가는 건 next 함수를 이용한다. 아래와 같다.
>>> def my_gen(): ... yield 1 ... yield 2 ... yield 3 ... >>> gen=my_gen() >>> next(gen) 1 >>> next(gen) 2 >>> next(gen) 3 >>> next(gen) Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration위와 같이 next(gen)으로 generator의 다음 값을 가져 올 수 있으며, generator가 모두 소진되면 StopIteration을 표출한다.
아래에서부터는 시각적인 이해를 위해 사이트에서 함수를 돌려보는 것을 추천한다.
Python Tutor - Visualize Python, Java, JavaScript, C, C++, Ruby code execution
조합 - yield
재귀 함수와 yield를 통해 조합을 구현할 수 있다.
>>> def combinations(arr, r): ... for i in range(len(arr)): ... if r == 1: ... yield [arr[i]] ... else: ... for j in combinations(arr[i+1:], r - 1): ... yield [arr[i]] + j ... >>> for combi in combinations([1,2,3,4],2): ... print(combi,end=" ") ... [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4]리스트 총 원소 n개 중 r개를 뽑는 것이므로, 먼저, 하나를 선택 해 보자.
for i in range(len(arr)): arr을 전체 탐색할 수 있도록 len(arr)을 사용하고, combinations 함수가 재귀 함수이기 때문에 종료 조건은 r==1이 남았을 때로 두면 마지막으로 고르는 원소가 되어 yield 함수로 [arr[i]]을 반환한다. 반환하더라도 yield 함수이기 때문에 함수는 호출될 때 다시 계산하여 리턴한다.
현재까지 이 과정으로는 1명을 뽑은 것이기 때문에, r-1명을 뽑는 과정을 재귀적으로 반복한다.
다만 r-1명을 뽑을 때는 for j in combinations(arr[i+1:],r-1):을 통해 선택 함수 우측 값 중 하나를 선택한다.
선택이 완료되면 yield [arr[i]]+j를 사용하는 데, 이는 arr에서 선택된 값 더하기 r번째 선택한 값을 더한다. 이렇게 하면 리스트가 완성된다.
순열 - yield
>>> def permutations(prefix,k): ... if len(prefix) == r: ... yield prefix ... else: ... for i in range(k,len(arr)): ... arr[i], arr[k] = arr[k], arr[i] ... for next in permutations(prefix + [arr[k]], k+1): ... yield next ... arr[i], arr[k] = arr[k], arr[i] ... >>> arr = [1,2,3,4] >>> r = 2 >>> for perm in permutations([],0): ... print(perm, end=' ') ... [1, 2] [1, 3] [1, 4] [2, 1] [2, 3] [2, 4] [3, 2] [3, 1] [3, 4] [4, 2] [4, 3] [4, 1]솔직히 이건 이해가 잘 안 돼서 외웠다. prefix라는 리스트에 개수를 추가하며, 개수가 추가 될 땐 k+1씩 더하고, k값이 r값만큼 다 차게 되면, 이를 리턴한다는 의미로 보이는 데, 구체적인 건 나중에 추가 공부를 한 후에 업데이트 하도록 해야겠다.
중복 조합 - yield
>>> def combinations_replacement(arr, r): ... for i in range(len(arr)): ... if r == 1: ... yield [arr[i]] ... else: ... for j in combinations_replacement(arr[i:], r - 1): ... yield [arr[i]] + j ... >>> for combi in combinations_replacement([1,2,3,4],2): ... print(combi,end=" ") ... [1, 1] [1, 2] [1, 3] [1, 4] [2, 2] [2, 3] [2, 4] [3, 3] [3, 4] [4, 4]중복 조합은 for j in combinations_replacement(arr[i+1:], r-1):이 아닌 for j in combinations_replacement(arr[i], r-1):이 되어 자기 자신도 선택될 수 있도록 구성된다. 따라서, 원소의 중복을 허용하므로 중복 조합이 선택된다.
중복 순열 - yield
>>> def combinations(arr, r): ... for i in range(len(arr)): ... if r == 1: ... yield [arr[i]] ... else: ... for j in combinations(arr, r - 1): ... yield [arr[i]] + j ... >>> for combi in combinations([1,2,3,4],2): ... print(combi,end=" ") ... [1, 1] [1, 2] [1, 3] [1, 4] [2, 1] [2, 2] [2, 3] [2, 4] [3, 1] [3, 2] [3, 3] [3, 4] [4, 1] [4, 2] [4, 3] [4, 4]위 조합에서 크게 달라진 것은 없고, for j in combiations(arr[i+1:],r-1):에서 for j in combiations(arr,r-1):로 변경되었다. arr에 대해서 모두 완전 탐색하겠다는 의미이다. 따라서 원소의 중복을 허용하고 각 리스트가 선택하고자 하는 요소 개수만큼 완전 탐색되므로 중복 순열이 된다.
Reference조합 / 중복조합 / 중복순열 알고리즘 - Python 매우간단!(itertools사용x) : 네이버 블로그 (naver.com)