[백준/Python] DFS/BFS - 6603번 로또
👩🏻🏫 풀이
import sys
# 재귀함수를 이용한 조합 구현
def combination(arr, n):
result = []
if n == 0:
return [[]]
for i in range(len(arr)):
elem = arr[i]
for rest in combination(arr[i+1:],n-1):
result.append([elem]+rest)
return result
nums = []
while True:
lst = list(map(int,sys.stdin.readline().split()))
if lst[0] == 0:
break
del lst[0]
for i in combination(lst,6):
for j in i:
print(j, end=" ")
print()
print()
- 헷갈린 부분: 입력을 다 받고, 테스트 케이스 순서대로 출력되어야하는 줄 알았는데 그게 아니었음.
# 출력
7 1 2 3 4 5 6 7
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34
0
✏️ 수학 공식
순열(Permutation)
- 서로 다른 개에서 개를 순서대로 선택하는 경우의 수
조합(Combination)
- 서로 다른 개에서 개를 순서 상관없이 선택하는 경우의 수
중복 순열(Permutation with repetition)
- 서로 다른 개에서 개를 중복 가능하게 순서로 선택하는 경우의 수
중복 조합(Combination with repetition)
- 서로 다른 개에서 개를 중복 가능하게 순서 상관없이 선택하는 경우의 수
✏️ Python
재귀함수를 이용한 조합 구현
- 기본적인 아이디어
combination([0,1,2,3],2)
=
([0], combination([1,2,3], 1))
+
([1], combination([2,3], 1))
+
([2], combination([3], 1))
- 코드
def combination(arr,n):
result = []
if n == 0:
return [[]]
for i in range(len(arr)):
elem = arr[i]
for rest in combination(arr[i+1:],n-1):
result.append([elem] + rest)
return result
print(combination([0,1,2,3],2) # [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
재귀함수를 이용한 순열 구현
- 기본적인 아이디어
permutation([0,1,2,3],2)
=
([0], combination([1,2,3], 1))
+
([1], combination([0,2,3], 1))
+
([2], combination([0,1,3], 1))
+
([3], combination([0,1,2], 1))
- 코드
def permutaion(arr,n):
result = []
if n == 0:
return [[]]
for i in range(len(arr)):
elem = arr[i]
for rest permuation(arr[:i] + arr[i+1:], n-1):
resutl.append([elem] + rest)
return result
print(permutation([0,1,2,3],2) #[[0, 1], [0, 2], [0, 3], [1, 0], [1, 2], [1, 3], [2, 0], [2, 1], [2, 3], [3, 0], [3, 1], [3, 2]]
Author And Source
이 문제에 관하여([백준/Python] DFS/BFS - 6603번 로또), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sugenius77/백준Python-DFSBFS-6603번-로또저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)