✍조합이란?
조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미
⭐순서 상관 없이⭐
예를 들어, 4C2의 경우
{1, 2, 3, 4}의 수가 있을 때, {1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4} 총 6개의 경우의 수가 나온다.
✍itertools를 사용한 조합
from itertools import combinations
arr = [1,2,3,4,5]
for i in combinations(arr,3):
print(i, end='')✍loop를 사용한 조합
A = [1,2,3,4,5]
def func(n):
for i in range(n-2):
for j in range(i+1, n-1):
for k in range(j+1, n): # i+2부터 범위를 잡게되면, 동일한 숫자가 포함될 수 있다.
print(A[i], A[j], A[k])
func(len(A))n의 개수가 달라지는 경우 그대로 사용하지만, k의 개수가 달라지는 경우 for문을 추가/감소 등의 변경을 해야한다.
✍recursion를 사용한 조합
그림은 5개의 데이터 중, 3개를 선택할 경우의 수에 대해 보여주고 있다. (n=5, k =3)
그림 위에서부터 level = 0,1,2 단계로 나눈다. level이란 내가 몇 번째 선택을 하는 중인지 알려준다. level이 올라갈수록, 끝지점이 1씩 추가되는 것을 볼 수 있다.
또한 내가 어떠한 숫자를 선택했다면, 그 다음 level에서는 그 숫자를 제외한 다음부터 시작된다. 즉, 전 level에서 선택된 것을 기반으로 하기 때문에, 어디서 시작해야될지 알려줘야 한다.
그 다음 숫자를 하나씩 말해주는 것이 아니라, 범위를 알려줘야 하기 때문에 for문을 사용했다.
n=5
k=3
arr = [0]*k
A=[1,2,3,4,5]
def combi(level, S):
# 종료조건
if level >= k:
print(arr)
return
# S : 시작점
for i in range(S, n-k+level+1): # range를 사용하므로 +1
arr[level] = A[i]
combi(level+1, i+1)
# 다음 시작점(S)는 지금 숫자의 다음부터 진행해야 하므로 i+1이라고 알려줌
combi(0,0)for문에서는 시작점(S)와 끝나는 지점을 정해주어야 한다.
S는 combi(0,0)과 같이 level과 함께 알려주기 때문에, 끝나는 지점만 확인해봤다.
n=5, k=3, level=0 S~2 => n-k+level
n=5, k=3, level=1 S~3
n=5, k=3, level=2 S~4
위의 풀이를 보면, 끝나는 지점은 'n-k+level'로 정할 수 있다.
시작점과 끝지점이 2씩 차이나는데, S+2는 안될까?
=> 5C2를 생각해보자. [level 0]에서는 S~3, [level 1]에서는 S~4까지 쓸 수 있다. 간격이 S+3이기 때문에 시작점과의 간격으로 정하는 것은 별로다!
✍후기
처음에는 3C0=1과 같은 조합의 기본 규칙을 생각하면서 잘못된 방향으로 코드를 짰다.
그러다가 만들어진 조합의 수 구하기ㅎㅎ
def combination(n,k):
if k==0:
return 1
elif n<k:
return 0
else:
return combination(n-1,k-1)+combination(n-1,k)
print(combination(5,3))전공으로 배울 때도 느꼈지만, 재귀는 정말 어렵다.. 앞으로 더 열심히 문제를 풀어봐야지~!
코드 보러가기 👉 combination.py
피드백은 언제나 환영입니다.💛
[참고 사이트]
https://yabmoons.tistory.com/99
https://www.youtube.com/watch?v=RfqcJLE2OCE&list=PLnp1rUgG4UVYc77Ltm9Le6LtHc71jY390&index=14
